Kaip įdiegti eilę naudodami du kaminus?

Tarkime, mes turime du stelažus ir kitus laikinus kintamuosius.

Ar galima „statyti“ eilės duomenų struktūrą, naudojant tik du stelažus?

359
16 сент. nustatė Nitin, rugsėjo 16 d 2008-09-16 06:37 '08 at 6:37 AM 2008-09-16 06:37
@ 19 atsakymų

Laikykite 2 kaminus, iškvieskite juos į inbox ir outbox .

Įdėti

  • Spustelėkite naują inbox elementą

Dequeue

  • Jei outbox tuščia, papildykite ją, įdėdami kiekvieną elementą iš inbox ir spustelėdami jį outbox

  • Pop ir grįžkite viršutinį elementą iš outbox

Naudojant šį metodą, kiekvienas elementas bus kiekviename kamino tiksliai vieną kartą - kiekvienas elementas bus išstumiamas du kartus ir du kartus išstumiamas, suteikiant amortizuotą operaciją pastoviu laiku.

Čia yra įdiegimas „Java“:

661
16 сент. Atsakymą pateikė Dave L. 16 rugsėjo. 2008-09-16 07:42 '08 at 7:42 2008-09-16 07:42

A - Kaip apversti krūvą

Norėdami suprasti, kaip sukurti eilę, naudodami du kaminus, turite suprasti, kaip galite padaryti atvirkštinį steką aišku. Prisiminkite, kaip veikia kamino darbai, jis labai panašus į jūsų virtuvės patiekalų krūvą. Paskutinis išplautas indas bus ant švarių kaminų, vadinamų „ L ast I n F “. Pirmasis kompiuterinis mokslas.

Pateikiame savo steką kaip butelį, kaip parodyta žemiau:

2019

23 авг. Atsakė Levent Divilioglu , rugpjūčio 23 d 2016-08-23 02:01 '16 at 2:01 am 2016-08-23 02:01

Galite netgi imituoti eilę naudodami tik vieną steką. Antrąjį (laikiną) kaminą galima modeliuoti įterpimo metodo rekursinio skambučio kamino.

Įrašant naują elementą į eilę, šis principas išlieka toks pats:

  • Jei norite atšaukti užsakymą, elementus reikia perkelti į kitą laikiną kaminą.
  • Tada įterpkite naują elementą įterpti į laikiną kaminą.
  • Tada perkelkite elementus atgal į originalų kaminą.
  • Naujas elementas bus viršuje, o seniausias elementas bus rodomas viršuje (pirmiausia reikia išjungti)

„Queue“ klasė, naudojant tik vieną krūvą, bus tokia:

 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 сент. atsakymą pateikė pythonquick rugsėjo 16 d 2008-09-16 23:58 '08 at 23:58 pm 2008-09-16 23:58

Briano atsakymas yra klasikinis. Tiesą sakant, tai yra vienas iš geriausių būdų, kaip įgyvendinti nuolatines funkcijų eiles su nusidėvėjimu. Taip yra dėl to, kad funkciniame programavime turime labai gerą nuolatinį krūvą (susietas sąrašas). Naudodami du sąrašus, kaip tai aprašo Brianas, galite įdiegti greitą eilę nereikalaujant nepriekaištingo kopijavimo.

Kaip šalutinį elementą, galite įrodyti, kad galite padaryti viską su dviem kaminėliais. Taip yra dėl to, kad dvejopo kamino operacija visiškai atitinka universalios Turingo mašinos apibrėžimą. Tačiau, kaip rodo Fortas, ne visada lengva: -)

14
16 сент. Daniel Spiewak atsakymas, pateiktas rugsėjo 16 d. 2008-09-16 06:50 '08 at 6:50 am 2008-09-16 06:50

Laikini sunkumai bus dar blogesni. Geras eilės įgyvendinimas daro viską pastoviu laiku.

Redaguoti

Nežinau, kodėl mano atsakymas buvo praleistas. Jei programuojame, mes rūpinamės laiko sudėtingumu, o dviejų standartinių kaminų naudojimas eilės sukūrimui yra neveiksmingas. Tai labai svarbus ir svarbus klausimas. Jei kas nors jaučia poreikį tai sumažinti, norėčiau sužinoti, kodėl.

Šiek tiek daugiau: kodėl naudojant du kaminus yra blogiau nei tik eilė: jei naudojate du kaminus ir kažkas sukelia deformaciją, kai šaltinio dėžutė yra tuščia, jums reikia linijinio laiko, kad pasiektumėte savo pašto dėžutės apačią (pvz. galite matyti Dave kode).

Galite įgyvendinti eilę kaip vieną susietą sąrašą (kiekvienas elementas nukreipia į kitą įterptą elementą), išlaikydamas papildomą rodiklį į paskutinį įtrauktą elementą stumti (arba padaryti jį apvaliuoju sąrašu). Įgyvendinant eilę ir pašalinant iš šios duomenų struktūros, labai lengva atlikti pastoviu laiku. Tai yra blogiausias nustatytas laikas, o ne nusidėvėjimas. Ir kadangi komentarai, atrodo, reikalauja tokio paaiškinimo, blogiausias nuolatinis laikas yra griežtai geresnis nei amortizuotas pastovus laikas.

11
16 сент. Tylerio atsakymas, pateiktas rugsėjo 16 d. 2008-09-16 06:40 '08 6:40 2008-09-16 06:40

Tegul eilė turi būti q ir kaminai, naudojami q - stack1 ir stack2.

q gali būti įgyvendintas dviem būdais:

1 metodas (kad „enQueue“ operacija būtų brangi)

Šis metodas užtikrina, kad naujai įvestas elementas visada būtų 1 viršuje, taigi deQueue operacija paprasčiausiai atsiranda iš kamino1. Norėdami įdėti elementą į viršų1, naudojamas 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. 

2 metodas (operacijos deQueue brangumas)

Šiuo metodu operacijų eilėje operacijos viršuje įvedamas naujas elementas1. Budėjimo eilėje, jei stack2 yra tuščias, visi elementai perkeliami į stack2 ir, galiausiai, grąžinama viršutinė stack2 dalis.

 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. 

2 metodas neabejotinai yra geresnis už 1 metodą. 1 metodas perkelia visus elementus du kartus į „enQueue“ operaciją, o 2 metodas (deQueue operacijoje) elementus vieną kartą perkelia ir elementus perkelia tik tada, kai stack2 yra tuščias.

7
31 марта '14 в 1:34 2014-03-31 01:34 atsakymas pateikiamas gandhi_rahul kovo 31 d. 14 d. 1:34 2014-03-31 01:34

Sprendimas 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 atsakymą pateikė Santhosh gegužės 31 d. 17 d

Jums reikės ištraukti viską nuo pirmojo steko, kad gautumėte apatinį elementą. Tada grąžinkite juos į antrą kaminą kiekvienai „dequeue“ operacijai.

2
16 сент. atsakymą pateikė user11055 September 16 2008-09-16 07:26 '08, 07:26, 2008-09-16 07:26

kūrėjui C # yra išsami programa:

 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 нояб. Atsakymą pateikė Jaydeep Shil . 2016-11-15 08:55 '16 at 8:55 2016-11-15 08:55

Dvi eilės eilės yra apibrėžtos kaip stack1 ir stack2 .

Komplektas: Elemento elementai visuomet dedami į steką1

Dequeue: stack2 viršus gali paslysti, nes jis yra pirmasis elementas, įterptas į eilę, kai stack2 nėra tuščias. Kai stack2 yra tuščias, mes atskleidžiame visus elementus iš kamino1 ir nuosekliai juos įkeliame į steką2 . Pirmasis eilėje esantis elementas yra dedamas į kamino apačią1 . Jis gali būti ištrauktas iš karto po popping ir stumimo operacijų, nes jis yra ant stekų2 .

Toliau pateikiamas C + + kodo pavyzdys:

 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; } 

Šis sprendimas yra pasiskolintas iš mano dienoraščio . Mano dienoraščio tinklalapyje galima rasti išsamesnę operacijų simuliaciją.

2
29 дек. Harryui jis atsakė gruodžio 29 d. 2012-12-29 05:02 '12 at 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 окт. atsakymas pateikiamas imvp 13 okt. 2015-10-13 09:49 '15 ne 9:49 2015-10-13 09:49

Eilės įgyvendinimas naudojant du „Swift“ kaminus:

1
17 окт. atsakymas davejlin 17 spalis. 2017-10-17 20:41 '17 at 8:41 pm 2017-10-17 20:41

Nors gausite daug pranešimų, susijusių su dviejų stekų eilės įgyvendinimu: 1. Padarykite „enQueue“ procesą daug brangesnę 2. Arba deQueue procesas tampa daug brangesnis

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

Vienas svarbus būdas, kurį sužinojau iš pirmiau minėto pranešimo, buvo sukurti eilę tik su kamino duomenų struktūra ir rekursiniu skambučių kaminu.

Nors galima teigti, kad pažodžiui jis vis dar naudoja du stelius, tačiau idealiai jis naudoja tik vieną kamino duomenų struktūrą.

Toliau pateikiamas problemos paaiškinimas:

  1. Atskirkite vieną steką, kad apdorotumėte ir ištrintumėte duomenis, ir stumkite jį į kamino.

  2. o deQueueing turi pagrindinę būseną, kai kamino elementas išskleidžiamas, kai kamino dydis yra 1. Tai užtikrins, kad deQueue nėra rekursijos metu.

  3. Ištrindami eilę, pirmiausia užverkite duomenis iš kamino viršaus. Idealiu atveju šis elementas bus elementas, esantis kamino viršuje. Dabar, kai tai daroma, rekursyviai skambinkite deQueue funkcijai ir po to įdėkite elementą virš jo atgal į kaminą.

Kodas bus rodomas toliau:

 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; 

Tokiu būdu galite sukurti eilę, naudodami vieną stekų duomenų struktūrą ir rekursinio skambučio steką.

1
27 мая '18 в 6:02 2018-05-27 06:02 „ Radioactive“ atsakymą pateikė gegužės 27 d. 18 val. 6:02 2018-05-27 06:02

čia yra mano sprendimas java naudojant susietą sąrašą.

 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; } } 

}

Pastaba: šiuo atveju „pop“ operacija yra labai daug laiko. Todėl aš neketinsiu sukurti eilės naudodamasis dviem kaminėliais.

0
24 сент. Atsakymas, kurį pateikė Irshad ck 24 Sep. 2017-09-24 16:32 '17 at 16:32 2017-09-24 16:32

Žemiau pateikiamas javascript sprendimas, naudojant ES6 sintaksę.

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 }; 

Naudojama:

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 янв. Jyoti Prasad Pal atsakymas, sausio 20 d 2019-01-20 11:09 „19, 11:09 val. 2019-01-20 11:09

Atsakysiu į šį klausimą „Go“, nes „Go“ standartinėje bibliotekoje nėra turtingų kolekcijų.

Kadangi kamino yra labai paprasta įdiegti, aš maniau, kad bandysiu naudoti du kaminus dvigubo užbaigimo eilėje. Siekiant geriau suprasti, kaip aš atėjau į mano atsakymą, aš padalijau įgyvendinimą į dvi dalis, pirmoji dalis, tikiuosi, bus lengviau suprantama, tačiau ji yra neišsami.

 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:] } } 

Tai iš esmės yra du kaminai, kur leidžiame manipuliuoti viena su kita apatinės kamino dalies. Aš taip pat naudojosi STL pavadinimų konvencijomis, kuriose tradiciniai stumti, pop, žvilgtelėję kamino operacijos turi priekinį / galinį prefiksą, nesvarbu, ar jie susiję su eilės priekiniu ar galiniu.

Problema, susijusi su minėtu kodu, yra ta, kad ji nėra labai efektyvi atminties. Tiesą sakant, jis auga be galo, kol baigsite erdvę. Tai labai blogai. Tikslas yra paprasčiausiai pakartotinai panaudoti kamino vietos apačią, kai įmanoma. Turime įvesti kompensaciją, kad tai būtų galima stebėti, nes „Go“ gabalas negali augti priekyje, nes jis mažėja.

 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.") } } }