Kako implementirati red pomoću dva hrpe?

Pretpostavimo da imamo dvije hrpe i neku drugu privremenu varijablu.

Je li moguće "izgraditi" strukturu podataka o redovima koristeći samo dva hrpe?

359
16 сент. postavio korisnik Nitin 16. rujna 2008-09-16 06:37 '08 u 6:37 AM 2008-09-16 06:37
@ 19 odgovora

Držite 2 hrpe, nazovite ih inbox i outbox inbox .

Staviti

  • Kliknite novu stavku u inbox

Dequeue

  • Ako je outbox prazna, nadopunite je tako da svaki element postavite iz inbox i kliknete na outbox

  • Otvorite i vratite gornju stavku iz outbox

Koristeći ovu metodu, svaki element će biti u svakom stogu točno jednom - svaki element će se dvaput gurnuti i dvaput gurnuti, čime se dobivaju amortizirane operacije s konstantnim vremenom.

Evo implementacije u Javi:

661
16 сент. Odgovor daje Dave L. 16. rujna. 2008-09-16 07:42 '08 u 7:42 2008-09-16 07:42

A - Kako okrenuti stog

Da biste razumjeli kako izgraditi red pomoću dva hrpe, morate razumjeti kako možete napraviti kristalno jasan obrnuti stog. Zapamtite kako stog radi, vrlo je sličan hrpi posuđa u vašoj kuhinji. Posljednja oprana posuda bit će na vrhu čistih hrpa, koja se zove L ast I n F O O O (LIFO) u računalnoj znanosti.

Predstavimo naš stack kao bocu, kao što je prikazano u nastavku:

2019

23 авг. Odgovorio Levent Divilioglu 23. kolovoza 2016-08-23 02:01 '16 u 2:01 am 2016-08-23 02:01

Možete čak i simulirati red koristeći samo jedan stack. Drugi (privremeni) stog može se modelirati rekurzivnim stogom poziva metode umetanja.

Princip ostaje isti pri umetanju nove stavke u red:

  • Morate premjestiti stavke iz jednog hrpe u drugi privremeni stog da biste poništili njihovu narudžbu.
  • Zatim umetnite novu stavku za umetanje u privremeni stog.
  • Zatim premjestite stavke natrag u izvorni snop.
  • Nova će stavka biti na dnu hrpe, a najstarija stavka bit će na vrhu (prvo morate iskočiti)

Klasa Queue koja koristi samo jedan stog bit će kako slijedi:

 public class SimulatedQueue<E> { private java.util.Stack<E> stack = new java.util.Stack<E>(); public void insert(E elem) { if (!stack.empty()) { E topElem = stack.pop(); insert(elem); stack.push(topElem); } else stack.push(elem); } public E remove() { return stack.pop(); } } 
79
16 сент. odgovor je dao pythonquick Sep 16 2008-09-16 23:58 '08 u 23:58 2008-09-16 23:58

Brianov odgovor je klasično ispravan. U stvari, ovo je jedan od najboljih načina za implementaciju upornih redova funkcija s amortiziranim fiksnim vremenom. To je zbog činjenice da u funkcionalnom programiranju imamo vrlo dobar stalni stog (povezani popis). Koristeći dva popisa na način na koji ga Brian opisuje, možete implementirati brz red bez potrebe za nepristojnim kopiranjem.

Kao sporedna linija, možete dokazati da sve možete učiniti s dva hrpe. To je zbog činjenice da rad s dvostrukim snopom u potpunosti ispunjava definiciju univerzalnog Turingovog stroja. Međutim, kao što Fort pokazuje, nije uvijek lako: -)

14
16 сент. Odgovor dao Daniel Spiewak 16. rujna. 2008-09-16 06:50 '08 u 6:50 am 2008-09-16 06:50

Privremene poteškoće će biti još gore. Dobra implementacija reda čini sve u stalnom vremenu.

Uređivanje

Ne znam zašto je moj odgovor ovdje izostavljen. Ako programiramo, brinemo o vremenskoj složenosti, a korištenje dva standardna stacka za stvaranje reda je neučinkovito. To je vrlo važno i relevantno pitanje. Ako netko drugi osjeća potrebu da to smanji, bilo bi me zanimalo zašto.

Još malo: zašto je korištenje dva hrpe gore nego samo red: ako koristite dva hrpe, a netko uzrokuje odjavu kad je izvorni okvir prazan, potrebno je linearno vrijeme da biste došli do dna ulazne pošte (kao što je možete vidjeti u Daveovom kodu).

Red možete implementirati kao jednu povezanu listu (svaka stavka upućuje na sljedeću umetnutu stavku), zadržavajući dodatni pokazivač na zadnju umetnutu stavku za push (ili čineći je kružnim popisom). Implementacija reda i uklanjanje iz ove strukture podataka je vrlo lako za napraviti u stalnom vremenu. Ovo je najgore fiksno vrijeme, a ne amortizacija. A kako se čini da komentari zahtijevaju takvo pojašnjenje, najgore stalno vrijeme je strogo bolje od amortiziranog konstantnog vremena.

11
16 сент. Odgovor dao Tyler 16. rujna. 2008-09-16 06:40 '08 u 6:40 2008-09-16 06:40

Neka red bude q, a stackovi se koriste za implementaciju q - stack1 i stack2.

q se može implementirati na dva načina:

Metoda 1 (izrada postupka enQueue skupim)

Ova metoda osigurava da je novo uneseni element uvijek na vrhu stog 1, tako da deQueue operacija jednostavno dolazi iz stack1. Za stavljanje elementa na vrh stack1, koristi se stack2.

 enQueue(q, x) 1) While stack1 is not empty, push everything from stack1 to stack2. 2) Push x to stack1 (assuming size of stacks is unlimited). 3) Push everything back to stack1. deQueue(q) 1) If stack1 is empty then error 2) Pop an item from stack1 and return it. 

Metoda 2 (što čini postupak deQueue skupim)

U ovoj metodi, u operaciji en-queue, novi element se unosi na vrhu stack1. U stanju čekanja, ako je stack2 prazan, svi elementi se premještaju u stack2 i na kraju se vraća gornji dio stack2.

 enQueue(q, x) 1) Push x to stack1 (assuming size of stacks is unlimited). deQueue(q) 1) If both stacks are empty then error. 2) If stack2 is empty While stack1 is not empty, push everything from stack1 to stack2. 3) Pop the element from stack2 and return it. 

Metoda 2 je definitivno bolja od metode 1. Metoda 1 pomiče sve elemente dvaput u enQueue operaciji, a metoda 2 (u deQueue operaciji) pomiče elemente jednom i samo pomiče elemente ako je stack2 prazan.

7
31 марта '14 в 1:34 2014-03-31 01:34 odgovor je dao gandhi_rahul 31. ožujka 2014. u 1:34 2014-03-31 01:34

Rješenje u C #

  public class Queue<T> where T : class { private Stack<T> input = new Stack<T>(); private Stack<T> output = new Stack<T>(); public void Enqueue(T t) { input.Push(t); } public T Dequeue() { if (output.Count == 0) { while (input.Count != 0) { output.Push(input.Pop()); } } return output.Pop(); } } 
3
31 мая '17 в 3:08 2017-05-31 03:08 odgovor je dao Santhosh 31. svibnja 2006. u 3:08 2017-05-33 03:08

Morat ćete povući sve iz prvog stog da biste dobili donji element. Zatim ih vratite u drugi stack za svaku "dequeue" operaciju.

2
16 сент. odgovor daje korisnik11055 16. rujna 2008-09-16 07:26 '08 u 7:26 am 2008-09-16 07:26

za razvojnog C # je cjelovit program:

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace QueueImplimentationUsingStack { class Program { public class Stack<T> { public int size; public Node<T> head; public void Push(T data) { Node<T> node = new Node<T>(); node.data = data; if (head == null) head = node; else { node.link = head; head = node; } size++; Display(); } public Node<T> Pop() { if (head == null) return null; else { Node<T> temp = head; //temp.link = null; head = head.link; size--; Display(); return temp; } } public void Display() { if (size == 0) Console.WriteLine("Empty"); else { Console.Clear(); Node<T> temp = head; while (temp!= null) { Console.WriteLine(temp.data); temp = temp.link; } } } } public class Queue<T> { public int size; public Stack<T> inbox; public Stack<T> outbox; public Queue() { inbox = new Stack<T>(); outbox = new Stack<T>(); } public void EnQueue(T data) { inbox.Push(data); size++; } public Node<T> DeQueue() { if (outbox.size == 0) { while (inbox.size != 0) { outbox.Push(inbox.Pop().data); } } Node<T> temp = new Node<T>(); if (outbox.size != 0) { temp = outbox.Pop(); size--; } return temp; } } public class Node<T> { public T data; public Node<T> link; } static void Main(string[] args) { Queue<int> q = new Queue<int>(); for (int i = 1; i <= 3; i++) q.EnQueue(i); // q.Display(); for (int i = 1; i < 3; i++) q.DeQueue(); //q.Display(); Console.ReadKey(); } } } 
2
15 нояб. Odgovor daje Jaydeep Shil 15 Nov. 2016-11-15 08:55 '16 u 8:55 2016-11-15 08:55

Dva hrpe u redu su definirani kao stack1 i stack2 .

Set: Elementi euqueued-a uvijek se stavljaju u stack1

Dequeue: Vrh stack2 može skliznuti jer je prva stavka umetnuta u red kad stack2 nije prazan. Kada je stack2 prazan, izlažemo sve elemente iz stack1 i sekvencijalno ih stavljamo u stack2 . Prvi element u redu čekanja nalazi se na dnu stog 1 . Može se izvući odmah nakon iskakanja i pritiskanja operacija, budući da je na vrhu stack2 .

Slijedi primjer C ++ koda:

 template <typename T> class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; }; template<typename T> void CQueue<T>::appendTail(const T element) { stack1.push(element); } template<typename T> T CQueue<T>::deleteHead() { if(stack2.size()<= 0) { while(stack1.size()>0) { T data = stack1.top(); stack1.pop(); stack2.push(data); } } if(stack2.size() == 0) throw new exception("queue is empty"); T head = stack2.top(); stack2.pop(); return head; } 

Ovo rješenje posuđeno je iz mog bloga . Detaljnija analiza s postupnom simulacijom operacija dostupna je na mojoj web stranici.

2
29 дек. odgovor dan Harryju 29. prosinca. 2012-12-29 05:02 '12 u 5:02 2012-12-29 05:02
 // Two stacks s1 Original and s2 as Temp one private Stack<Integer> s1 = new Stack<Integer>(); private Stack<Integer> s2 = new Stack<Integer>();  public void insert( int data ) { if( s1.size() == 0 ) { s1.push( data ); } else { while( !s1.isEmpty() ) { s2.push( s1.pop() ); } s1.push( data ); while( !s2.isEmpty() ) { s1.push( s2.pop() ); } } } public void remove() { if( s1.isEmpty() ) { System.out.println( "Empty" ); } else { s1.pop(); } } 
1
13 окт. odgovor je dat imvp 13 okt. 2015-10-13 09:49 '15 u 9:49 2015-10-13 09:49

Implementacija reda pomoću dva hrpe u Swiftu:

1
17 окт. odgovor dao davejlin 17. lis. 2017-10-17 20:41 '17 u 20:41 2017-10-17 20:41

Iako ćete primiti mnogo poruka koje se odnose na implementaciju reda s dva stupa: 1. Ili će enQueue proces biti puno skuplji 2. Ili će deQueue proces biti puno skuplji.

https://www.geeksforgeeks.org/queue-using-stacks/

Jedna važna metoda koju sam naučio iz gore navedenog posta bio je stvoriti red samo s strukturom podataka o stogu i rekurzivnim stogom poziva.

Iako se može tvrditi da doslovno još uvijek koristi dva hrpe, ali u idealnom slučaju koristi samo jednu strukturu podataka o stogu.

Slijedi objašnjenje problema:

  1. Objavite jedan stog za obradu i brisanje podataka i gurnite ga u snop.

  2. dok deQueueing ima osnovni uvjet u kojem element stog iskače kada je veličina slaganja 1. To će osigurati da deQueue nije prisutan tijekom rekurzije.

  3. Prilikom brisanja reda, prvo ispišite podatke s vrha hrpe. Idealno, ovaj element će biti element koji je prisutan na vrhu stog. Sada kada je to učinjeno, rekurzivno pozovite funkciju deQueue, a zatim umetnite element iznad njega natrag u stog.

Kôd će izgledati u nastavku:

 if (s1.isEmpty()) System.out.println("The Queue is empty"); else if (s1.size() == 1) return s1.pop(); else { int x = s1.pop(); int result = deQueue(); s1.push(x); return result; 

Na taj način možete stvoriti red pomoću jedne podatkovne strukture stogova i skupa rekurzivnih poziva.

1
27 мая '18 в 6:02 2018-05-27 06:02 odgovor daje Radioaktivni 27. svibnja u 6:02 sati. 2018-05-27 06:02

ovdje je moje rješenje u javi pomoću povezanog popisa.

 class queue<T>{ static class Node<T>{ private T data; private Node<T> next; Node(T data){ this.data = data; next = null; } } Node firstTop; Node secondTop; void push(T data){ Node temp = new Node(data); temp.next = firstTop; firstTop = temp; } void pop(){ if(firstTop == null){ return; } Node temp = firstTop; while(temp != null){ Node temp1 = new Node(temp.data); temp1.next = secondTop; secondTop = temp1; temp = temp.next; } secondTop = secondTop.next; firstTop = null; while(secondTop != null){ Node temp3 = new Node(secondTop.data); temp3.next = firstTop; firstTop = temp3; secondTop = secondTop.next; } } 

}

Napomena: U ovom slučaju, operacija popa je vrlo dugotrajna. Stoga, neću predložiti stvaranje reda pomoću dva hrpe.

0
24 сент. Odgovor dao Irshad ck 24. rujna. 2017-09-24 16:32 '17 u 16:32 2017-09-24 16:32

Ispod je javascript rješenje pomoću ES6 sintaksu.

Stack.js

 //stack using array class Stack { constructor() { this.data = []; } push(data) { this.data.push(data); } pop() { return this.data.pop(); } peek() { return this.data[this.data.length - 1]; } size(){ return this.data.length; } } export { Stack }; 

QueueUsingTwoStacks.js

 import { Stack } from "./Stack"; class QueueUsingTwoStacks { constructor() { this.stack1 = new Stack(); this.stack2 = new Stack(); } enqueue(data) { this.stack1.push(data); } dequeue() { //if both stacks are empty, return undefined if (this.stack1.size() === 0  this.stack2.size() === 0) return undefined; //if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty if (this.stack2.size() === 0) { while (this.stack1.size() !== 0) { this.stack2.push(this.stack1.pop()); } } //pop and return the element from stack 2 return this.stack2.pop(); } } export { QueueUsingTwoStacks }; 

Slijedi uporaba:

index.js

 import { StackUsingTwoQueues } from './StackUsingTwoQueues'; let que = new QueueUsingTwoStacks(); que.enqueue("A"); que.enqueue("B"); que.enqueue("C"); console.log(que.dequeue()); //output: "A" 
0
20 янв. Odgovor Jyoti Prasad Pal 20. siječnja 2019-01-20 11:09 '19 u 23:09 sati 2019-01-20 11:09

Odgovorit ću na ovo pitanje u Go, jer Go nema bogate zbirke u svojoj standardnoj knjižnici.

Budući da je stack vrlo jednostavan za implementaciju, mislio sam da ću pokušati koristiti dva hrpe za izvršavanje reda dvostrukog završetka. Da bih bolje razumio kako sam došao do odgovora, podijelio sam provedbu na dva dijela, prvi dio, nadam se, bit će lakše razumjeti, ali je nepotpun.

 type IntQueue struct { front []int back []int } func (q *IntQueue) PushFront(v int) { q.front = append(q.front, v) } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[0] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { q.back = q.back[1:] } } func (q *IntQueue) PushBack(v int) { q.back = append(q.back, v) } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[0] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { q.front = q.front[1:] } } 

To su u osnovi dvije hrpe, gdje dopuštamo da se donji dio hrpe manipulira jedni s drugima. Također sam koristio STL pravila imenovanja, u kojima tradicionalne push, pop, peek stack operacije imaju prednji / stražnji prefiks, bilo da se odnose na prednji ili stražnji red.

Problem s gornjim kodom je u tome što memorija ne koristi učinkovito. Zapravo, ona raste beskrajno dok ne završite prostor. Ovo je jako loše. Popravak za ovo je jednostavno ponovno korištenje dna prostora za skladištenje kada je to moguće. Moramo uvesti offset kako bismo to pratili, budući da Go slice ne može rasti naprijed jer se smanjuje.

 type IntQueue struct { front []int frontOffset int back []int backOffset int } func (q *IntQueue) PushFront(v int) { if q.backOffset > 0 { i := q.backOffset - 1 q.back[i] = v q.backOffset = i } else { q.front = append(q.front, v) } } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[q.backOffset] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { if len(q.back) > 0 { q.backOffset++ } else { panic("Cannot pop front of empty queue.") } } } func (q *IntQueue) PushBack(v int) { if q.frontOffset > 0 { i := q.frontOffset - 1 q.front[i] = v q.frontOffset = i } else { q.back = append(q.back, v) } } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[q.frontOffset] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { if len(q.front) > 0 { q.frontOffset++ } else { panic("Cannot pop back of empty queue.") } } }