it-swarm-id.com

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?

362
Nitin

Simpan 2 tumpukan, sebut saja mereka inbox dan outbox.

Enqueue :

  • Dorong elemen baru ke inbox

Dequeue :

  • Jika outbox kosong, isi ulang dengan memunculkan setiap elemen dari inbox dan mendorongnya ke outbox

  • Pop dan kembalikan elemen teratas dari outbox

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

Berikut ini adalah implementasi di Jawa:

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.Push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.Push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}
665
Dave L.

A - Cara Membalik Stack

Untuk memahami cara membuat antrian menggunakan dua tumpukan, Anda harus memahami cara membalikkan tumpukan sebening kristal. Ingat bagaimana tumpukan bekerja, ini sangat mirip dengan tumpukan piring di dapur Anda. Piringan yang terakhir kali dicuci akan berada di atas tumpukan bersih, yang disebut sebagai L ast I n F irst O ut (LIFO) dalam ilmu komputer.

Mari kita bayangkan tumpukan kita seperti botol seperti di bawah ini;

 enter image description here

Jika kita mendorong bilangan bulat 1,2,3 masing-masing, maka 3 akan berada di atas tumpukan. Karena 1 akan didorong pertama, maka 2 akan diletakkan di atas 1. Terakhir, 3 akan diletakkan di atas tumpukan dan status terbaru tumpukan kami direpresentasikan sebagai botol akan seperti di bawah ini;

 enter image description here

Sekarang tumpukan kami telah diwakili karena botol diisi dengan nilai 3,2,1. Dan kami ingin membalikkan tumpukan sehingga elemen atas tumpukan menjadi 1 dan elemen dasar tumpukan akan menjadi 3. Apa yang bisa kita lakukan? Kita dapat mengambil botol dan memegangnya terbalik sehingga semua nilai harus terbalik agar?

 enter image description here

Ya kita bisa melakukan itu, tapi itu sebotol. Untuk melakukan proses yang sama, kita perlu memiliki tumpukan kedua yang akan menyimpan elemen tumpukan pertama dalam urutan terbalik. Mari kita letakkan tumpukan terisi ke kiri dan tumpukan kosong baru di sebelah kanan. Untuk membalik urutan elemen, kita akan pop setiap elemen dari tumpukan kiri, dan Dorong mereka ke tumpukan kanan. Anda dapat melihat apa yang terjadi saat kami melakukannya pada gambar di bawah ini;

 enter image description here

Jadi kita tahu cara membalikkan tumpukan.

B - Menggunakan Dua Tumpukan Sebagai Antrian

Pada bagian sebelumnya, saya telah menjelaskan bagaimana cara membalik urutan elemen tumpukan. Ini penting, karena jika kita Push dan pop elemen ke stack, output akan tepat dalam urutan antrian. Berpikir pada contoh, mari Dorong array bilangan bulat {1, 2, 3, 4, 5} ke tumpukan. Jika kita pop elemen dan mencetaknya sampai tumpukan kosong, kita akan mendapatkan array dalam urutan terbalik dari urutan dorong, yang akan menjadi {5, 4, 3, 2, 1} Ingat bahwa untuk input yang sama, jika kita mengantri antrian sampai antrian kosong, output akan menjadi {1, 2, 3, 4, 5}. Jadi jelas bahwa untuk urutan input elemen yang sama, output antrian persis kebalikan dari output stack. Seperti yang kita tahu cara membalikkan tumpukan menggunakan tumpukan tambahan, kita dapat membangun antrian menggunakan dua tumpukan.

Model antrian kami akan terdiri dari dua tumpukan. Satu tumpukan akan digunakan untuk operasi enqueue (tumpukan # 1 di sebelah kiri, akan disebut sebagai Input Stack), tumpukan lain akan digunakan untuk operasi dequeue (tumpukan # 2 di sebelah kanan, akan disebut sebagai Output Stack). Lihat gambar di bawah ini;

 enter image description here

Kode semu kami adalah seperti di bawah ini;


Operasi Enqueue

Push every input element to the Input Stack

Operasi Dequeue

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and Push them to the Output Stack until Input Stack is Empty

pop from Output Stack

Mari kita masing-masing mendefinisikan bilangan bulat {1, 2, 3}. Integer akan didorong pada Input Stack (Stack # 1) yang terletak di sebelah kiri;

 enter image description here

Lalu apa yang akan terjadi jika kita menjalankan operasi dequeue? Setiap kali operasi dequeue dijalankan, antrian akan memeriksa apakah Output Stack kosong atau tidak (lihat kode semu di atas) Jika Output Stack kosong, maka Stack Input akan diekstraksi pada output sehingga elemen-elemen Input Stack akan dibalik. Sebelum mengembalikan nilai, keadaan antrian akan seperti di bawah ini;

 enter image description here

Lihat urutan elemen dalam Output Stack (Stack # 2). Sudah jelas bahwa kita dapat memunculkan elemen dari Output Stack sehingga hasilnya akan sama seperti jika kita keluar dari antrian. Jadi, jika kita menjalankan dua operasi dequeue, pertama kita akan mendapatkan {1, 2} masing-masing. Kemudian elemen 3 akan menjadi satu-satunya elemen dari Stack Output, dan Stack Input akan kosong. Jika kita memberikan elemen 4 dan 5, maka status antrian adalah sebagai berikut;

 enter image description here

Sekarang Output Stack tidak kosong, dan jika kita menjalankan operasi dequeue, hanya 3 yang akan muncul dari Output Stack. Maka negara akan terlihat seperti di bawah ini;

 enter image description here

Sekali lagi, jika kita menjalankan dua operasi dequeue lagi, pada operasi dequeue pertama, antrian akan memeriksa apakah Output Stack kosong, yang benar. Kemudian keluarkan elemen dari Stack Input dan Dorong mereka ke Stack Output hingga Stack Input kosong, maka status Antrian akan seperti di bawah ini;

 enter image description here

Mudah dilihat, output dari dua operasi dequeue adalah {4, 5}

C - Implementasi Antrian Dibangun dengan Dua Tumpukan

Berikut ini adalah implementasi di Jawa. Saya tidak akan menggunakan implementasi Stack yang ada jadi contoh di sini akan menemukan kembali roda;

C - 1) Kelas MyStack: Implementasi Simple Stack

public class MyStack<T> {

    // inner generic Node class
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head;
    private int size;

    public void Push(T e) {
        Node<T> newElem = new Node(e);

        if(head == null) {
            head = newElem;
        } else {
            newElem.next = head;
            head = newElem;     // new elem on the top of the stack
        }

        size++;
    }

    public T pop() {
        if(head == null)
            return null;

        T elem = head.data;
        head = head.next;   // top of the stack is head.next

        size--;

        return elem;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printStack() {
        System.out.print("Stack: ");

        if(size == 0)
            System.out.print("Empty !");
        else
            for(Node<T> temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

        System.out.printf("\n");
    }
}

C - 2) Kelas MyQueue: Implementasi Antrian Menggunakan Two Stacks

public class MyQueue<T> {

    private MyStack<T> inputStack;      // for enqueue
    private MyStack<T> outputStack;     // for dequeue
    private int size;

    public MyQueue() {
        inputStack = new MyStack<>();
        outputStack = new MyStack<>();
    }

    public void enqueue(T e) {
        inputStack.Push(e);
        size++;
    }

    public T dequeue() {
        // fill out all the Input if output stack is empty
        if(outputStack.isEmpty())
            while(!inputStack.isEmpty())
                outputStack.Push(inputStack.pop());

        T temp = null;
        if(!outputStack.isEmpty()) {
            temp = outputStack.pop();
            size--;
        }

        return temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

}

C - 3) Kode Demo

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();

        // enqueue integers 1..3
        for(int i = 1; i <= 3; i++)
            queue.enqueue(i);

        // execute 2 dequeue operations 
        for(int i = 0; i < 2; i++)
            System.out.println("Dequeued: " + queue.dequeue());

        // enqueue integers 4..5
        for(int i = 4; i <= 5; i++)
            queue.enqueue(i);

        // dequeue the rest
        while(!queue.isEmpty())
            System.out.println("Dequeued: " + queue.dequeue());
    }

}

C - 4) Contoh Output

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
185

Anda bahkan dapat mensimulasikan antrian menggunakan hanya satu tumpukan. Tumpukan kedua (sementara) dapat disimulasikan oleh tumpukan panggilan panggilan rekursif ke metode insert. 

Prinsipnya tetap sama ketika memasukkan elemen baru ke dalam antrian: 

  • Anda perlu mentransfer elemen dari satu tumpukan ke tumpukan sementara lain, untuk membalikkan urutannya. 
  • Kemudian Dorong elemen baru yang akan dimasukkan, ke tumpukan sementara
  • Kemudian pindahkan elemen kembali ke tumpukan asli
  • Elemen baru akan berada di bagian bawah tumpukan, dan elemen tertua ada di atas (pertama kali muncul)

Kelas antrian hanya menggunakan 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
pythonquick

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

Edit

Tidak yakin mengapa jawaban saya dibatalkan di sini. Jika kami memprogram, kami peduli dengan kompleksitas waktu, dan menggunakan dua tumpukan standar untuk membuat antrian tidak efisien. Ini poin yang sangat valid dan relevan. Jika ada orang lain yang merasa perlu untuk lebih banyak mengurungkan hal ini, saya akan tertarik untuk mengetahui alasannya.

Sedikit lebih detail: tentang mengapa menggunakan dua tumpukan lebih buruk daripada hanya antrian: jika Anda menggunakan dua tumpukan, dan seseorang memanggil dequeue saat kotak keluar kosong, Anda perlu waktu linier untuk sampai ke bagian bawah kotak masuk ( seperti yang Anda lihat dalam kode Dave).

Anda dapat menerapkan antrian sebagai daftar yang terhubung sendiri-sendiri (setiap elemen menunjuk ke elemen yang disisipkan berikutnya), menyimpan penunjuk tambahan ke elemen yang dimasukkan terakhir untuk mendorong (atau menjadikannya daftar siklik). Menerapkan antrian dan dequeue pada struktur data ini sangat mudah dilakukan dalam waktu yang konstan. Itu waktu terburuk terburuk, tidak diamortisasi. Dan, seperti komentar tampaknya meminta klarifikasi ini, waktu konstan terburuk terburuk lebih baik daripada waktu konstan diamortisasi.

11
Tyler

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

q dapat diimplementasikan dalam dua cara:

Metode 1 (Dengan membuat operasi enQueue mahal)

Metode ini memastikan bahwa elemen yang baru dimasukkan selalu di atas tumpukan 1, sehingga operasi deQueue hanya muncul dari stack1. Untuk meletakkan 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 (Dengan membuat operasi deQueue mahal)

Dalam metode ini, dalam operasi en-antrian, elemen baru dimasukkan di bagian atas stack1. Dalam operasi de-antrian, jika stack2 kosong maka semua elemen dipindahkan ke stack2 dan akhirnya 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, sedangkan metode 2 (dalam operasi deQueue) memindahkan elemen sekali dan hanya memindahkan elemen jika stack2 kosong.

7
Rahul Gandhi

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
Santhosh

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

2
user11055

untuk pengembang c # di sini 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
Jaydeep Shil

Dua tumpukan dalam antrian didefinisikan sebagai tumpukan1 dan stack2.

Enqueue: Elemen euqueued selalu didorong ke dalam tumpukan1

Dequeue: Bagian atas stack2 dapat muncul karena itu adalah elemen pertama yang dimasukkan ke dalam antrian ketika stack2 tidak kosong. Kapan stack2 kosong, kami memunculkan semua elemen dari tumpukan1 dan Dorong mereka ke dalam stack2 satu per satu. Elemen pertama dalam antrian didorong ke bagian bawah tumpukan1. Itu dapat muncul keluar langsung setelah muncul dan mendorong operasi karena berada di atas stack2.

Berikut ini adalah kode sampel C++ yang sama:

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 lebih rinci dengan simulasi operasi langkah demi langkah tersedia di halaman web blog saya.

2
Harry He
// Two stacks s1 Original and s2 as Temp one
    private Stack<Integer> s1 = new Stack<Integer>();
    private Stack<Integer> s2 = new Stack<Integer>();

    /*
     * Here we insert the data into the stack and if data all ready exist on
     * stack than we copy the entire stack s1 to s2 recursively and Push the new
     * element data onto s1 and than again recursively call the s2 to pop on s1.
     * 
     * Note here we can use either way ie We can keep pushing on s1 and than
     * while popping we can remove the first element from s2 by copying
     * recursively the data and removing the first index element.
     */
    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
imvp

Implementasi antrian menggunakan dua tumpukan di Swift:

struct Stack<Element> {
    var items = [Element]()

    var count : Int {
        return items.count
    }

    mutating func Push(_ item: Element) {
        items.append(item)
    }

    mutating func pop() -> Element? {
        return items.removeLast()
    }

    func peek() -> Element? {
        return items.last
    }
}

struct Queue<Element> {
    var inStack = Stack<Element>()
    var outStack = Stack<Element>()

    mutating func enqueue(_ item: Element) {
        inStack.Push(item)
    }

    mutating func dequeue() -> Element? {
        fillOutStack() 
        return outStack.pop()
    }

    mutating func peek() -> Element? {
        fillOutStack()
        return outStack.peek()
    }

    private mutating func fillOutStack() {
        if outStack.count == 0 {
            while inStack.count != 0 {
                outStack.Push(inStack.pop()!)
            }
        }
    }
}
1
davejlin

Meskipun Anda akan mendapatkan banyak posting terkait dengan mengimplementasikan antrian dengan dua tumpukan: 1. Baik dengan membuat proses enQueue jauh lebih mahal 2. Atau dengan membuat proses deQueue jauh lebih mahal

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

Salah satu cara penting yang saya temukan dari posting di atas adalah membangun antrian dengan hanya struktur data stack dan stack panggilan rekursi.

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

Di bawah ini adalah penjelasan masalahnya:

  1. Deklarasikan tumpukan tunggal untuk enQueuing dan deQueing data dan Dorong data ke dalam stack.

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

  3. Saat deQueueing 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 Dorong elemen yang muncul di atas kembali ke dalam tumpukan.

Kode akan terlihat seperti di bawah ini:

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
Radioactive

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

Karena tumpukan sangat mudah diimplementasikan, saya pikir saya akan mencoba dan menggunakan dua tumpukan untuk mencapai antrian ujung ganda. Untuk lebih memahami bagaimana saya sampai pada jawaban saya, saya telah membagi implementasi menjadi dua bagian, bagian pertama mudah-mudahan lebih mudah dimengerti 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:]
    }
}

Pada dasarnya ada dua tumpukan di mana kami membiarkan bagian bawah tumpukan dimanipulasi oleh satu sama lain. Saya juga telah menggunakan konvensi penamaan STL, di mana operasi Push, pop, peek tradisional stack memiliki awalan depan/belakang apakah mereka merujuk ke depan atau belakang antrian.

Masalah dengan kode di atas adalah tidak menggunakan memori dengan sangat efisien. Sebenarnya, ia tumbuh tanpa henti hingga Anda kehabisan ruang. Itu sangat buruk. Cara mengatasinya adalah dengan menggunakan kembali bagian bawah ruang stack jika memungkinkan. Kami harus memperkenalkan offset untuk melacak ini karena sepotong di Go tidak dapat tumbuh di depan setelah menyusut.

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

Ada banyak fungsi kecil tapi dari 6 fungsi 3 di antaranya hanya cermin dari yang lain.

0
John Leidegren

Di bawah ini adalah solusi dalam bahasa 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 };

Di bawah 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
Jyoti Prasad Pal
public class QueueUsingStacks<T>
{
    private LinkedListStack<T> stack1;
    private LinkedListStack<T> stack2;

    public QueueUsingStacks()
    {
        stack1=new LinkedListStack<T>();
        stack2 = new LinkedListStack<T>();

    }
    public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
    {
        while(source.Head!=null)
        {
            dest.Push(source.Head.Data);
            source.Head = source.Head.Next;
        }
    }
    public void Enqueue(T entry)
    {

       stack1.Push(entry);
    }
    public T Dequeue()
    {
        T obj;
        if (stack2 != null)
        {
            Copy(stack1, stack2);
             obj = stack2.Pop();
            Copy(stack2, stack1);
        }
        else
        {
            throw new Exception("Stack is empty");
        }
        return obj;
    }

    public void Display()
    {
        stack1.Display();
    }


}

Untuk setiap operasi enqueue, kami menambahkan ke bagian atas stack1. Untuk setiap dequeue, kami mengosongkan konten stack1 ke stack2, dan menghapus elemen di atas stack. Kompleksitas waktu adalah O(n) untuk dequeue, karena kami harus menyalin stack1 ke stack2. kompleksitas waktu enqueue sama dengan tumpukan biasa

0
PradGar

Dengan O(1)dequeue(), yang sama dengan answer pythonquick :

// time: O(n), space: O(n)
enqueue(x):
    if stack.isEmpty():
        stack.Push(x)
        return
    temp = stack.pop()
    enqueue(x)
    stack.Push(temp)

// time: O(1)
x dequeue():
    return stack.pop()

Dengan O(1)enqueue() (ini tidak disebutkan dalam posting ini jadi jawaban ini), yang juga menggunakan backtracking untuk menggembung dan mengembalikan item paling bawah.

// O(1)
enqueue(x):
    stack.Push(x)

// time: O(n), space: O(n)
x dequeue():
    temp = stack.pop()
    if stack.isEmpty():
        x = temp
    else:
        x = dequeue()
        stack.Push(temp)
    return x

Jelas, ini merupakan latihan pengkodean yang bagus karena tidak efisien namun elegan.

0
hIpPy