Bagaimana cara mengimplementasikan antrian menggunakan dua tumpukan?

Misalkan kita memiliki dua tumpukan dan tidak ada variabel sementara lainnya.

Apakah mungkin untuk "membangun" struktur data antrian hanya menggunakan dua tumpukan?

359
16 сент. diatur oleh Nitin 16 Sep 2008-09-16 06:37 '08 pada 6:37 AM 2008-09-16 06:37
@ 19 balasan

Pegang 2 tumpukan, panggil mereka inbox dan outbox .

Untuk dimasukkan

  • Klik item baru di inbox

Dequeue

  • Jika outbox kosong, isi kembali dengan menempatkan setiap elemen dari inbox dan mengkliknya pada outbox

  • Pop dan kembalikan item teratas dari outbox

Dengan menggunakan metode ini, setiap elemen akan berada di setiap tumpukan tepat sekali - setiap elemen akan didorong keluar dua kali dan didorong keluar dua kali, memberikan operasi diamortisasi dengan waktu yang konstan.

Berikut ini implementasinya di Jawa:

661
16 сент. Jawabannya diberikan Dave L. 2008-09-16 07:42 '08 pada 7:42 2008-09-16 07:42

A - Cara membalik tumpukan

Untuk memahami cara membuat antrian menggunakan dua tumpukan, Anda perlu memahami cara membuat tumpukan terbalik menjadi jernih. Ingat bagaimana tumpukan bekerja, ini sangat mirip dengan tumpukan piring di dapur Anda. Piringan terakhir yang dicuci akan berada di atas tumpukan bersih, yang disebut L ast I n F O ut pertama (LIFO) dalam ilmu komputer.

Mari sajikan tumpukan kami sebagai botol, seperti yang ditunjukkan di bawah ini:

2019

23 авг. Dijawab oleh Levent Divilioglu pada 23 Agustus 2016-08-23 02:01 '16 pada pukul 2:01 am 2016-08-23 02:01

Anda bahkan dapat mensimulasikan antrian menggunakan hanya satu tumpukan. Stack (sementara) kedua dapat dimodelkan dengan stack panggilan rekursif dari metode insert.

Prinsipnya tetap sama saat memasukkan item baru ke dalam antrian:

  • Anda perlu memindahkan item dari satu tumpukan ke tumpukan sementara lainnya untuk membatalkan pesanan mereka.
  • Kemudian masukkan item baru untuk dimasukkan ke dalam tumpukan sementara.
  • Kemudian pindahkan item kembali ke tumpukan asli.
  • Item baru akan berada di bagian bawah tumpukan, dan item tertua akan berada di atas (pertama-tama Anda harus keluar)

Kelas antrian menggunakan hanya satu tumpukan akan menjadi sebagai berikut:

 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 сент. jawabannya diberikan oleh pythonquick 16 Sep 2008-09-16 23:58 '08 pada jam 11:58 2008-09-16 23:58

Jawaban Brian benar secara klasik. Bahkan, ini adalah salah satu cara terbaik untuk mengimplementasikan antrian fungsi persisten dengan waktu tetap yang didepresiasi. Hal ini disebabkan oleh fakta bahwa dalam pemrograman fungsional kami memiliki tumpukan permanen yang sangat baik (daftar tertaut). Dengan menggunakan dua daftar seperti yang dijelaskan Brian, Anda dapat menerapkan antrian cepat tanpa perlu menyalin tidak senonoh.

Sebagai usaha sampingan, Anda dapat membuktikan bahwa Anda dapat melakukan segalanya dengan dua tumpukan. Hal ini disebabkan oleh fakta bahwa operasi dual-stack sepenuhnya memenuhi definisi dari mesin Turing universal. Namun, seperti yang ditunjukkan Fort, itu tidak selalu mudah .: -)

14
16 сент. Balas diberikan oleh Daniel Spiewak pada 16 Sep 2008-09-16 06:50 '08 pada 6:50 pagi 2008-09-16 06:50

Kesulitan sementara akan lebih buruk. Implementasi antrian yang baik melakukan semuanya dalam waktu yang konstan.

Edit

Saya tidak tahu mengapa jawaban saya dihi>

Sedikit lagi: mengapa menggunakan dua tumpukan lebih buruk daripada hanya antrian: jika Anda menggunakan dua tumpukan dan seseorang menyebabkan dequeue ketika kotak sumber kosong, Anda perlu waktu linier untuk sampai ke bagian bawah kotak masuk Anda (seperti Anda dapat melihat dalam kode Dave).

Anda dapat menerapkan antrian sebagai daftar yang ditautkan tunggal (setiap item menunjuk ke item yang dimasukkan berikutnya), menyimpan pointer tambahan ke item yang dimasukkan terakhir untuk push (atau menjadikannya daftar bundar). Mengantri dan menghapus data dari struktur ini sangat mudah dilakukan dalam waktu yang konstan. Ini adalah waktu yang paling buruk, bukan depresiasi. Dan karena komentar tampaknya memerlukan klarifikasi seperti itu, waktu permanen terburuk benar-benar lebih baik daripada waktu konstan diamortisasi.

11
16 сент. Balas diberikan oleh Tyler pada 16 Sep. 2008-09-16 06:40 '08 pada 6:40 2008-09-16 06:40

Biarkan antrian menjadi q dan tumpukan digunakan untuk mengimplementasikan q - stack1 dan stack2.

q dapat diimplementasikan dalam dua cara:

Metode 1 (membuat operasi enQueue mahal)

Metode ini memastikan bahwa elemen yang baru dimasukkan selalu di atas tumpukan 1, sehingga operasi deQueue hanya berasal dari stack1. Untuk menempatkan elemen di atas stack1, stack2 digunakan.

 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. 

Metode 2 (membuat operasi membutuhkan biaya tinggi)

Dalam metode ini, dalam operasi en-antrian, elemen baru dimasukkan di bagian atas stack1. Dalam antrian siaga, jika stack2 kosong, semua elemen dipindahkan ke stack2 dan, akhirnya, bagian atas stack2 dikembalikan.

 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. 

Metode 2 jelas lebih baik daripada metode 1. Metode 1 memindahkan semua elemen dua kali dalam operasi enQueue, dan metode 2 (dalam operasi deQueue) memindahkan elemen satu kali dan hanya memindahkan elemen jika stack2 kosong.

7
31 марта '14 в 1:34 2014-03-31 01:34 jawabannya diberikan oleh gandhi_rahul 31 Maret '14 pada 1:34 2014-03-31 01:34

Solusi dalam 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 jawabannya diberikan oleh Santhosh pada tanggal 31 Mei 17 jam 3:08 2017-05-33 03:08

Anda harus menarik semuanya dari tumpukan pertama untuk mendapatkan elemen bawah. Kemudian kembalikan ke tumpukan kedua untuk setiap operasi "dequeue".

2
16 сент. jawabannya diberikan oleh user11055 16 September 2008-09-16 07:26 '08 pada 7:26 pagi 2008-09-16 07:26

untuk pengembang C # adalah program lengkap:

 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 нояб. Jawaban diberikan oleh Jaydeep Shil 15 Nov. 2016-11-15 08:55 '16 pada 8:55 2016-11-15 08:55

Dua tumpukan dalam antrian didefinisikan sebagai stack1 dan stack2 .

Set: Elemen euqueued selalu ditempatkan di stack1

Dequeue: Bagian atas stack2 dapat tergelincir karena ini adalah item pertama yang dimasukkan dalam antrian ketika stack2 tidak kosong. Ketika stack2 kosong, kami mengekspos semua elemen dari stack1 dan secara berurutan memasukkannya ke stack2 . Elemen pertama dalam antrian ditempatkan di bagian bawah stack1 . Itu dapat ditarik segera setelah operasi popping dan mendorong, karena itu di atas stack2 .

Berikut ini adalah contoh kode C ++:

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

Solusi ini dipinjam dari blog saya . Analisis yang lebih terperinci dengan simulasi operasi tahap demi tahap tersedia di halaman web blog saya.

2
29 дек. balasan yang diberikan kepada Harry He pada tanggal 29 Desember. 2012-12-29 05:02 '12 pada 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 окт. jawabannya diberikan imvp 13 oktober. 2015-10-13 09:49 '15 pada 9:49 2015-10-13 09:49

Implementasi antrian menggunakan dua tumpukan di Swift:

1
17 окт. jawab diberikan davejlin 17 Okt 2017-10-17 20:41 '17 jam 8:41 malam 2017-10-17 20:41

Meskipun Anda akan menerima banyak pesan terkait dengan penerapan antrian dua-tumpukan: 1. Entah membuat proses enQueue jauh lebih mahal 2. Atau membuat proses deQueue jauh lebih mahal

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

Salah satu metode penting yang saya pelajari dari posting di atas adalah membuat antrian hanya dengan struktur data stack dan panggilan stack rekursif.

Meskipun dapat diperdebatkan bahwa secara harfiah masih menggunakan dua tumpukan, tetapi idealnya hanya menggunakan satu tumpukan data struktur.

Berikut ini adalah penjelasan dari masalahnya:

  1. Menyatakan satu tumpukan untuk memproses dan menghapus data dan mendorongnya ke tumpukan.

  2. sementara deQueueing memiliki kondisi dasar di mana elemen stack muncul ketika ukuran stack adalah 1. Ini akan memastikan bahwa deQueue tidak ada selama rekursi.

  3. Saat menghapus antrian, pertama-tama munculkan data dari atas tumpukan. Idealnya, elemen ini akan menjadi elemen yang ada di bagian atas tumpukan. Sekarang setelah ini selesai, panggil fungsi deQueue secara rekursif, dan kemudian masukkan elemen di atasnya kembali ke stack.

Kode akan terlihat di bawah:

 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; 

Dengan cara ini, Anda dapat membuat antrian menggunakan struktur data tumpukan tunggal dan tumpukan panggilan rekursi.

1
27 мая '18 в 6:02 2018-05-27 06:02 jawabannya diberikan oleh Radioaktif pada 27 Mei '18 di 6:02 2018-05-27 06:02

di sini adalah solusi saya di java menggunakan daftar tertaut.

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

}

Catatan: Dalam hal ini, operasi pop sangat memakan waktu. Oleh karena itu, saya tidak akan mengusulkan untuk membuat antrian menggunakan dua tumpukan.

0
24 сент. Balas diberikan oleh Irshad ck 24 Sep. 2017-09-24 16:32 '17 pada 16:32 2017-09-24 16:32

Di bawah ini adalah solusi javascript menggunakan sintaks ES6.

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

Berikut ini adalah penggunaannya:

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 янв. Jawaban yang diberikan oleh Jyoti Prasad Pal 20 Jan 2019-01-20 11:09 '19 jam 11:09 malam 2019-01-20 11:09

Saya akan menjawab pertanyaan ini di Go, karena Go tidak memiliki koleksi kaya di perpustakaan standarnya.

Karena stack sangat sederhana untuk diimplementasikan, saya pikir saya akan mencoba menggunakan dua tumpukan untuk menjalankan antrian penyelesaian ganda. Untuk lebih memahami bagaimana saya sampai pada jawaban saya, saya membagi implementasi menjadi dua bagian, bagian pertama, saya harap, akan lebih mudah dipahami, tetapi tidak lengkap.

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

Ini pada dasarnya adalah dua tumpukan, di mana kami membiarkan bagian bawah tumpukan dimanipulasi satu sama lain. Saya juga menggunakan konvensi penamaan STL, di mana operasi push, pop, peek stack tradisional memiliki awalan depan / belakang, apakah mereka berhubungan dengan depan atau belakang antrian.

Masalah dengan kode di atas adalah tidak menggunakan memori dengan sangat efisien. Bahkan, itu tumbuh tanpa henti sampai Anda menyelesaikan ruang. Ini sangat buruk. Cara mengatasinya adalah dengan menggunakan kembali bagian bawah ruang stack jika memungkinkan. Kami harus memperkenalkan offset untuk melacak ini, karena slice Go tidak dapat tumbuh di depan karena berkurang.

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