it-swarm-tr.com

İki yığın kullanarak bir sıra nasıl uygulanır?

İki yığınının olduğunu ve başka bir geçici değişkenin olmadığını varsayalım.

Yalnızca iki yığını kullanarak bir sıra veri yapısını "oluşturmak" mümkün mü?

362
Nitin

2 yığın tutun, onlara inbox ve outbox diyelim.

Enqueue :

  • Yeni elemanı inbox üzerine itin

Ayrılma :

  • outbox boşsa, her öğeyi inbox öğesinden çıkartarak ve outbox öğesinin üzerine iterek doldurun.

  • Pop ve outbox öğesinden üst öğeyi döndür

Bu metodu kullanarak, her eleman tam olarak bir kez her istifte olacaktır - yani her eleman iki kez itilecek ve iki kez patlatılarak itfa edilmiş sabit zaman işlemleri gerçekleştirilecektir.

İşte Java'da bir uygulama:

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 - Bir Yığın Nasıl Tersine Dönülür

İki yığın kullanarak bir kuyruğun nasıl oluşturulacağını anlamak için, yığın kristal berraklığını tersine çevirmeyi anlamanız gerekir. Yığının nasıl çalıştığını unutmayın, mutfağınızdaki bulaşık yığınına çok benzer. Son yıkanmış bulaşık, temiz yığının tepesinde olacak ve buna L ast _ n F ilk O ut (LIFO) bilgisayar bilimlerinde.

Yığımızı aşağıdaki gibi bir şişe gibi düşünelim;

 enter image description here

Sırasıyla 1,2,3 tamsayısına basarsak, 3 yığının tepesinde olur. Çünkü önce 1 itilir, sonra 2 1'in üstüne konur. Son olarak, yığının üstüne 3 yerleştirilir ve bir şişe olarak temsil edilen yığının en son hali aşağıdaki gibidir;

 enter image description here

Şimdi bir şişe olarak temsil edilen yığınımız 3,2,1 değerleriyle doldurulur. Ve yığını tersine çevirmek istiyoruz, böylece yığının üst elemanı 1 olur ve yığının alt elemanı 3 olur. Ne yapabiliriz? Şişeyi alıp baş aşağı tutarak tüm değerlerin tersine dönmesi için başarabilir miyiz?

 enter image description here

Evet bunu yapabiliriz, ama bu bir şişe. Aynı işlemi yapmak için, ilk yığın öğelerini ters sırada saklayacak olan ikinci bir yığına sahip olmamız gerekir. Doldurulmuş yığımızı sola ve yeni boş yığımızı sağa koyalım. Öğelerin sırasını tersine çevirmek için her öğeyi sol yığından açacağız ve sağ yığına iteceğiz. Aşağıdaki resimde yaptığımız gibi ne olduğunu görebilirsiniz;

 enter image description here

Yani bir yığını nasıl tersine çevireceğimizi biliyoruz.

B - İki Yığını Sıra Olarak Kullanma

Önceki bölümde, yığın öğelerinin sırasını nasıl tersine çevirebileceğimizi açıkladım. Bu önemliydi, çünkü elemanları istifle ittirir ve patlatırsak, çıktı tam olarak bir sıranın sırasına göre olacaktır. Bir örnek üzerinde düşünelim, hadi tamsayı dizisini {1, 2, 3, 4, 5} yığınına dizelim. Elemanları çıkarırsak ve yığın boş olana kadar yazdırırsak, diziyi tersten itme sırasına göre alırız, bu, {5, 4, 3, 2, 1} olacaktır. Aynı giriş için, sıra boş olana kadar sıraları silersek çıktı {1, 2, 3, 4, 5} olacaktır. Dolayısıyla, elemanların aynı giriş sırası için, sıranın çıktısının bir yığının çıktısının tam tersi olduğu açıktır. Bir yığının ekstra bir yığın kullanarak nasıl ters çevrileceğini bildiğimiz için, iki yığın kullanarak bir kuyruk oluşturabiliriz.

Sıra modelimiz iki istiflemeden oluşacak. enqueue işlemi için bir yığın kullanılacak (solda # 1 numaralı yığın, Giriş Yığını olarak adlandırılacak), dequeue işlemi için başka bir yığın kullanılacak (sağdaki 2 numaralı yığın, Çıkış Yığını olarak adlandırılacak). Aşağıdaki görüntüye göz atın;

 enter image description here

Sözde kodumuz aşağıdaki gibidir;


İşlem operasyonu

Push every input element to the Input Stack

Tahliye İşlemi

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

Sırasıyla {1, 2, 3} tam sayılarını çıkaralım. Tamsayılar solda bulunan Giriş Yığını (Yığın # 1) üzerine itilecektir;

 enter image description here

Öyleyse bir serbest bırakma işlemi yaparsak ne olacak? Ne zaman bir dekontasyon işlemi gerçekleştirilirse, sıra, Çıkış Yığının boş olup olmadığını kontrol eder (yukarıdaki sözde koda bakın) Çıkış Yığını boşsa, Giriş Yığın çıkışta çıkacak, böylece elemanlar çıkacak. Giriş Yığının ters çevrilecektir. Bir değer döndürmeden önce, sıranın durumu aşağıdaki gibi olacaktır;

 enter image description here

Çıkış Yığındaki öğelerin sırasını kontrol edin (Yığın # 2). Elemanları Çıkış Yığından çıkarabiliriz ki çıkış bir kuyruktan çıkarılmış gibi olacak şekilde aynı olacaktır. Böylece, iki dequeue işlemi yaparsak, önce sırasıyla {1, 2} alırız. Daha sonra eleman 3, Çıkış Yığının tek elemanı olacak ve Giriş Yığını boş olacaktır. Elementleri 4 ve 5'i sıkarsak, sıranın durumu aşağıdaki gibi olacaktır;

 enter image description here

Şimdi Çıkış Yığını boş değildir ve bir temizleme işlemi gerçekleştirirsek, Çıkış Yığından yalnızca 3 tanesi çıkarılır. Sonra devlet aşağıdaki gibi görülecektir;

 enter image description here

Yine, iki tane daha boşaltma işlemi yaparsak, ilk boşaltma işleminde sıra, Çıktı Yığının boş olup olmadığını kontrol eder, ki bu doğru. Sonra Giriş Yığını öğelerini açın ve bunları Giriş Yığını boşalıncaya kadar Çıkış Yığına itin, ardından Sıra durumu aşağıdaki gibi olacaktır;

 enter image description here

Görmesi kolay, iki dequeue işleminin çıktısı {4, 5} olacak

C - İki Yığınla Oluşturulan Sıranın Uygulanması

İşte Java'da bir uygulama. Mevcut Stack uygulamasını kullanmayacağım, buradaki örnek tekerleği yeniden icat edecek;

C - 1) MyStack sınıfı: Basit Bir Yığın Uygulaması

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) MyQueue sınıfı: İki Yığın Kullanarak Sıra Uygulaması

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) Demo Kodu

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) Numune Çıkışı

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

Yalnızca bir yığını kullanarak bir sırayı bile simüle edebilirsiniz. İkinci (geçici) yığın, özyinelemeli çağrıların çağrı yöntemi ile insert metoduna simüle edilebilir. 

Sıraya yeni bir öğe eklerken ilke aynı kalır: 

  • Öğelerini sıralarını tersine çevirmek için bir yığından başka bir geçici yığına aktarmanız gerekir. 
  • Ardından eklenecek yeni elemanı geçici istifin üzerine itin
  • Ardından elemanları tekrar orijinal istifine aktarın
  • Yeni eleman yığının altında olacak ve en eski eleman üstte olacak (ilk önce açılacak)

Yalnızca bir Yığın kullanan bir Queue sınıfı şu şekilde olur:

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

Zaman karmaşıklıkları olsa daha kötü olurdu. İyi bir sıra uygulaması, her şeyi sabit zamanda yapar.

Düzenle

Cevabımın neden burada reddedildiğinden emin değilim. Programlarsak zamanın karmaşıklığına önem veririz ve bir sıra yapmak için iki standart yığın kullanmak yetersizdir. Çok geçerli ve alakalı bir nokta. Başka birisi bunu daha fazla oy kullanma gereği duyuyorsa, nedenini bilmek isterim.

Biraz daha fazla ayrıntı: neden iki yığın kullanmanın sadece bir kuyruktan daha kötü olduğu hakkında: eğer iki yığın kullanırsanız ve giden kutusu boşken biri dequeue çağırırsa, gelen kutunun altına ulaşmak için doğrusal zamana ihtiyacınız vardır Dave'in kodunda gördüğünüz gibi).

Bir kuyruğu tek bağlantılı bir liste olarak uygulayabilirsiniz (her eleman sonraki eklenen öğeye işaret eder), itme için son eklenen öğeye fazladan bir işaretçi ekler (veya döngüsel bir liste yapar). Bu veri yapısına kuyruk ve dequeue uygulamak, sabit sürede yapılması çok kolaydır. Bu en kötü durum sabit zamandır, itfa edilmez. Ve yorumlar bu açıklamayı ister gibi göründüğü için, en kötü durumdaki sabit zaman, itfa edilen sabit zamandan kesinlikle daha iyidir.

11
Tyler

Uygulanacak kuyruğun q olması ve q'yu uygulamak için kullanılan yığınların stack1 ve stack2 olması gerekir. 

q two yolla uygulanabilir:

Yöntem 1 (EnQueue işlemini pahalı hale getirerek)

Bu yöntem, yeni girilen öğenin her zaman yığın 1'in üstünde olmasını sağlar, böylece deQueue işlemi sadece yığın1'den çıkar. Öğeyi stack1'in üstüne koymak için stack2 kullanılır.

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.

Yöntem 2 (deQueue işlemini pahalı yaparak)

Bu yöntemde, sıra işleminde, yeni eleman yığın1'in tepesine girilir. Kuyruktan çıkarma işleminde, yığın2 boşsa, tüm öğeler yığın2'ye taşınır ve son olarak yığın2'nin üst kısmı döndürülür.

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.

Yöntem 2, yöntem 1'den kesinlikle daha iyidir. Yöntem 1, tüm işlemleri sıra işlemi sırasında iki kez hareket ettirirken, yöntem 2 (sıra çalışması) öğeleri bir kez hareket ettirir ve yalnızca yığın2 boşsa öğeleri taşır.

7
Rahul Gandhi

C # ile bir çözüm

 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

Alttaki öğeyi elde etmek için her şeyi ilk yığından çıkarmanız gerekir. Daha sonra her "dequeue" işlemi için hepsini tekrar ikinci yığına koyun.

2
user11055

c # geliştirici için burada tam 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
Jaydeep Shil

Kuyruktaki iki yığın, stack1 ve stack2.

Enqueue: Boşaltılan öğeler her zaman içine itilir stack1

Dequeue: stack2 ne zaman kuyruğa sokulan ilk eleman olduğundan çıkarılabilir stack2 boş değil. Ne zaman stack2 boş, biz bütün elemanları açtık stack1 ve onları içine itin stack2 birer birer Kuyruktaki ilk eleman, dibine itilir. stack1. En üstte olduğundan operasyonları patlattıktan ve ittikten sonra doğrudan çıkarılabilir stack2.

Aşağıdaki aynı C++ örnek kodudur:

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

Bu çözüm blogum 'dan ödünç alınmıştır. Adım adım işlem simülasyonları ile daha ayrıntılı analiz blog sayfamda mevcut.

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

Swift'de iki yığın kullanarak bir kuyruğun uygulanması:

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

Sırasıyla iki sıralı bir sıra uygulamakla ilgili birçok mesaj alırken: 1. EnQueue sürecini çok daha pahalı hale getirerek. Veya deQueue işlemini çok daha pahalı hale getirerek

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

Yukarıdaki yazıdan öğrendiğim önemli bir yol, yalnızca yığın veri yapısı ve özyineleme çağrısı yığını ile kuyruk oluşturmaktı.

Biri kelimenin tam anlamıyla bu hala iki yığın kullanıyor olduğunu iddia edebilir, ancak daha sonra ideal olarak bu sadece bir yığın veri yapısı kullanıyor.

Sorunun açıklaması aşağıdadır:

  1. Verileri sıraya almak ve sıraya koymak için tek bir yığın tanımlayın ve verileri yığına itin.

  2. deQueueing, yığın boyutu 1 olduğunda yığının elemanının çıkarıldığı bir temel koşulu varken deQueue özyinelemesi sırasında yığın taşması olmamasını sağlayacaktır.

  3. DeQueueing ilk önce veriyi yığının en üstünden açın. İdeal olarak, bu eleman yığının tepesinde bulunan eleman olacaktır. Şimdi bu yapıldıktan sonra, tekrar tekrar deQueue işlevini çağırın ve sonra yukarıda atılan öğeyi yığının içine geri itin.

Kod aşağıdaki gibi görünecek:

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;

Bu şekilde, tek bir yığın veri yapısını ve özyinelemeli çağrı yığınını kullanarak bir kuyruk oluşturabilirsiniz.

1
Radioactive

java'daki çözümüm, linklist kullanarak.

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

}

Not: Bu durumda, pop işlemi çok zaman alıyor. Bu yüzden iki yığını kullanarak bir kuyruk oluşturmayı önermeyeceğim. 

0
Irshad ck

Go'da bu soruyu cevaplayacağım çünkü Go standart kütüphanesinde zengin bir koleksiyona sahip değil.

Bir yığının uygulanması gerçekten kolay olduğundan, çift uçlu bir kuyruğu gerçekleştirmek için iki yığını kullanmaya çalışacağımı düşündüm. Cevabımı nasıl elde ettiğimi daha iyi anlamak için, uygulamayı iki bölüme ayırdım, ilk bölümün anlaşılması umarım daha kolaydır ancak eksiktir.

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

Temel olarak, yığınların tabanının birbirleri tarafından manipüle edilmesine izin verdiğimiz iki yığın. Ayrıca, bir yığının geleneksel Push, pop, peek işlemlerinin kuyruğun önüne veya arkasına bakıp bakmadıklarına bir ön/arka önekine sahip olduğu STL adlandırma kurallarını kullandım.

Yukarıdaki kodun sorunu hafızayı çok verimli kullanmamasıdır. Aslında, siz boşalıncaya kadar sonsuz bir şekilde büyür. Bu gerçekten kötü. Bunun için düzeltme, mümkün olduğunda yığın boşluğunun altını tekrar kullanmaktır. Go'da bir dilim küçüldükten sonra önlerde büyüyemediğinden, bunu takip etmek için bir denge sağlamalıyız.

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

Çok küçük fonksiyonlar var ama 6 fonksiyondan 3 tanesi diğerinin aynası.

0
John Leidegren

Aşağıda javascript dilinde ES6 sözdizimini kullanan çözüm bulunmaktadır.

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

Aşağıda kullanım:

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


}

Her enqueue işlemi için, stack1'in üstüne ekleriz. Her ayrıştırma için, yığın1'in içeriğini yığın2'ye boşaltırız ve öğeyi yığının üstünden kaldırırız. Zaman karmaşıklığı, yığın1'i yığın2'ye kopyalamamız gerektiği için O(n) olur. Enqueue zaman karmaşıklığı normal bir yığınla aynıdır

0
PradGar

O(1) ile dequeue(), pythonquick'in answer ile aynıdır:

// 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()

O(1) ile enqueue() (bu yazıda bundan bahsedilmez, bu cevap budur).

// 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

Açıkçası, yine de verimsiz fakat zarif olduğu için iyi bir kodlama egzersizi.

0
hIpPy