it-swarm-eu.dev

Jak implementovat frontu pomocí dvou zásobníků?

Předpokládejme, že máme dva zásobníky a žádnou jinou dočasnou proměnnou.

Je možné "konstruovat" datovou strukturu fronty pouze pomocí dvou zásobníků?

362
Nitin

Udržujte 2 zásobníky, pojmenujme je inbox a outbox.

Enqueue :

  • Zatlačte nový prvek na inbox

Dequeue :

  • Je-li outbox prázdné, doplňte jej vyskočením každého prvku z inbox a posunutím na outbox

  • Pop a vrátit horní prvek z outbox

Pomocí této metody bude každý prvek v každém zásobníku přesně jednou - což znamená, že každý prvek bude dvakrát zatlačen a dvakrát vyskočen, což umožní amortizované operace s konstantním časem.

Zde je implementace v jazyce Java:

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 - Jak zvrátit zásobník

Chcete-li pochopit, jak vytvořit frontu pomocí dvou svazků, měli byste pochopit, jak převrátit zásobník křišťálově čistě. Pamatujte si, jak zásobník funguje, je to velmi podobné zásobníku nádobí v kuchyni. Poslední umytý pokrm bude nahoře v čistém zásobníku, který se nazývá L ast I n F irst O ut (LIFO) v informatice.

Představme si náš zásobník jako láhev níže;

 enter image description here

Pokud stiskneme celá čísla 1,2,3, pak 3 budou na vrcholu zásobníku. Protože první bude poslán jako první, pak se 2 umístí na vrchol 1. Nakonec budou 3 umístěny na vrchol zásobníku a poslední stav našeho zásobníku reprezentovaný jako láhev bude stejný jako níže;

 enter image description here

Nyní máme náš zásobník reprezentovaný jako láhev naplněná hodnotami 3,2,1. A chceme převrátit zásobník tak, že horní prvek zásobníku bude 1 a dolní prvek zásobníku bude 3. Co můžeme udělat? Můžeme vzít láhev a držet ji vzhůru nohama tak, aby všechny hodnoty měly být v pořádku?

 enter image description here

Ano, můžeme to udělat, ale to je láhev. Pro provedení stejného procesu musíme mít druhý zásobník, který bude ukládat první prvky zásobníku v opačném pořadí. Pojďme dát náš zaplněný zásobník doleva a náš nový prázdný zásobník vpravo. Chcete-li změnit pořadí prvků, pop-up každý prvek z levého zásobníku, a Push je do pravého zásobníku. Můžete vidět, co se stane, jak to děláme na obrázku níže;

 enter image description here

Takže víme, jak převrátit zásobník.

B - Použití dvou hromádek jako fronty

V předchozí části jsem vysvětlil, jak můžeme změnit pořadí prvků zásobníku. To bylo důležité, protože pokud Push a pop prvky do zásobníku, bude výstup přesně v opačném pořadí fronty. Přemýšlím o příkladu, pojďme tlačit pole celých čísel {1, 2, 3, 4, 5} do zásobníku. Pokud vyskočíme elementy a vytiskneme je, dokud není zásobník prázdný, dostaneme pole v opačném pořadí, v jakém je pořadí {5, 4, 3, 2, 1}. výstup bude {1, 2, 3, 4, 5}. Je tedy zřejmé, že pro stejné pořadí vstupů prvků je výstup fronty přesně opačný než výstup zásobníku. Jak víme, jak převrátit zásobník pomocí extra zásobníku, můžeme vytvořit frontu pomocí dvou zásobníků.

Náš model fronty se bude skládat ze dvou zásobníků. Jeden zásobník bude použit pro operaci enqueue (zásobník č. 1 vlevo, bude označován jako vstupní zásobník), další zásobník bude použit pro operaci dequeue (zásobník č. 2 vpravo bude nazýván výstupním zásobníkem). Podívejte se na níže uvedený obrázek;

 enter image description here

Náš pseudo-kód je jak je uvedeno níže;


Operace Enqueue

Push every input element to the Input Stack

Operace 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

Pojďme se naučit celá čísla {1, 2, 3} resp. Celá čísla budou tlačena na vstupní zásobník (zásobník # 1), který se nachází vlevo;

 enter image description here

Co se pak stane, když provedeme operaci dequeue? Kdykoliv je prováděna operace dequeue, fronta zkontroluje, zda je výstupní zásobník prázdný nebo ne (viz výše pseudo-kód) Pokud je výstupní zásobník prázdný, pak bude vstupní zásobník extrahován na výstup, takže prvky vstupního zásobníku bude obrácen. Před vrácením hodnoty bude stav fronty stejný jako níže;

 enter image description here

Zkontrolujte pořadí prvků ve výstupním zásobníku (zásobník č. 2). Je zřejmé, že můžeme vyskakovat prvky z výstupního zásobníku, takže výstup bude stejný, jako kdybychom z fronty odstranili. Pokud tedy provedeme dvě operace, nejprve dostaneme {1, 2}. Pak bude prvek 3 jediným prvkem výstupního zásobníku a vstupní zásobník bude prázdný. Pokud spojíme prvky 4 a 5, pak bude stav fronty následující;

 enter image description here

Výstupní zásobník není prázdný a pokud provedeme operaci dequeue, z výstupního zásobníku budou vyskočeny pouze 3. Pak bude stav viděn níže;

 enter image description here

Opět platí, že pokud provedeme dvě další operace, v první operaci, fronta zkontroluje, zda je výstupní zásobník prázdný, což je pravda. Pak vyskočte prvky vstupního zásobníku a posuňte je do výstupního zásobníku, dokud není vstupní zásobník prázdný, pak bude stav fronty stejný jako níže;

 enter image description here

Výstup dvou operací dequeue bude snadno viditelný {4, 5}

C - Implementace fronty vytvořené se dvěma komíny

Zde je implementace v jazyce Java. Nebudu používat stávající implementaci Stacku, takže příklad zde bude objevovat kolo;

C - 1) Třída MyStack: Implementace jednoduchého zásobníku

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) Třída MyQueue: Implementace fronty pomocí dvou zásobníků

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 kód

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) Výstup vzorku

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

Frontu můžete dokonce simulovat pouze pomocí jednoho zásobníku. Druhý (dočasný) zásobník může být simulován zásobníkem volání rekurzivních volání metody insert. 

Princip zůstává stejný při vkládání nového prvku do fronty: 

  • Je třeba přenést prvky z jednoho zásobníku do jiného dočasného zásobníku, aby bylo možné změnit jejich pořadí. 
  • Poté zatlačte nový prvek, který má být vložen, do dočasného zásobníku
  • Poté přeneste prvky zpět do původního zásobníku
  • Nový prvek bude v dolní části zásobníku a nejstarší prvek bude nahoře (nejprve bude zobrazen)

Třída fronty používající pouze jeden zásobník by byla následující:

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

Časová složitost by však byla horší. Dobrá implementace fronty dělá vše ve stálém čase.

Upravit

Nejste si jisti, proč zde byla moje odpověď snížena. Pokud programujeme, staráme se o časovou složitost a použití dvou standardních zásobníků k vytvoření fronty je neefektivní. Je to velmi platný a relevantní bod. Pokud se někdo jiný domnívá, že je to nutné, měl bych zájem vědět proč.

Více podrobností: o tom, proč je použití dvou zásobníků horší než jen fronta: pokud používáte dva zásobníky a někdo volá dequeue, když je zpráva k odeslání prázdná, budete potřebovat lineární čas, abyste se dostali do dolní části doručené pošty ( jak vidíte v Daveově kódu).

Frontu můžete implementovat jako jednotlivě propojený seznam (každý prvek ukazuje na další vložený prvek), přičemž přidává další ukazatel k naposledy vloženému prvku pro posuny (nebo vytvoření cyklického seznamu). Implementace fronty a dequeue na této datové struktuře je velmi snadná. To je nejhorší případ konstantní, ne amortizovaný. A jak se zdá, komentáře k tomuto objasnění vyžadují, nejhorší konstantní doba je striktně lepší než amortizovaná konstantní doba.

11
Tyler

Nechte implementovat frontu q a zásobníky použité pro implementaci q jsou stack1 a stack2. 

q lze implementovat v dvou způsobech:

Metoda 1 (Tím, že bude operace enqueue nákladná)

Tato metoda zajišťuje, že nově zadaný prvek je vždy v horní části zásobníku 1, takže operace deQueue právě vyskočí ze zásobníku1. Pro vložení prvku do horní části stack1 se použije 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 (Operace deQueue je nákladná)

V této metodě, v en-queue operaci, je nový prvek zadán v horní části stack1. Pokud je operace de-queue prázdná, pak jsou všechny prvky přesunuty do stack2 a nakonec je vrácena horní část 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 rozhodně lepší než metoda 1. Metoda 1 přesune všechny elementy dvakrát do operace enQueue, zatímco metoda 2 (v operaci deQueue) přemístí prvky jednou a přesune prvky pouze v případě, že stack2 je prázdný.

7
Rahul Gandhi

Řešení v 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

Budete muset vypnout vše z prvního zásobníku, abyste dostali dolní prvek. Poté je umístěte zpět do druhého zásobníku pro každou operaci „dequeue“.

2
user11055

pro c # developer zde je kompletní 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

Dvě sady ve frontě jsou definovány jako stack1stack2.

Enqueue: Euqueued elementy jsou vždy tlačeny do stack1

Dequeue: Nahoru stack2 lze vyskakovat, protože se jedná o první prvek vložený do fronty stack2 není prázdný. Když stack2 je prázdná, vycházíme ze všech stack1 a zatlačte je do stack2 jeden za druhým. První prvek ve frontě je zatlačen do dolní části stack1. To může být vyskočil přímo po popping a tlačí operace, protože je na vrcholu stack2.

Následující ukázkový kód C++ je stejný:

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

Toto řešení je zapůjčeno z mého blogu . Podrobnější analýza s podrobnými operativními simulacemi je k dispozici na webových stránkách mého blogu.

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

Implementace fronty pomocí dvou zásobníků v aplikaci 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

Zatímco získáte spoustu příspěvků souvisejících s implementací fronty se dvěma komíny: 1. Buď tím, že proces enQueue bude mnohem dražší 2. Nebo tím, že proces deQueue bude mnohem nákladnější

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

Jedním z důležitých způsobů, jak jsem zjistil z výše uvedeného příspěvku, bylo sestavení fronty s pouze datovou strukturou zásobníku a sestavou rekurzního volání.

Zatímco jeden může argumentovat, že doslovně toto je ještě používat dva zásobníky, ale pak ideálně toto je používat jen jednu datovou strukturu zásobníku.

Níže je vysvětlen problém:

  1. Deklarovat jeden zásobník pro enQueuing a deQueing dat a Push data do zásobníku.

  2. zatímco deQueueing má základní podmínku, kde je prvek zásobníku vyskakován, když je velikost zásobníku 1. To zajistí, že během rekurze deQueue nedojde k přetečení zásobníku.

  3. Zatímco deQueueing nejprve pop data z horní části zásobníku. V ideálním případě bude tento prvek prvkem, který je v horní části stohu. Poté, co je toto provedeno, rekurzivně volání funkce deQueue a pak Push prvek vyskočil nad zpět do zásobníku.

Kód bude vypadat takto:

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;

Tímto způsobem můžete vytvořit frontu pomocí struktury dat jednoho zásobníku a zásobníku volání rekurze.

1
Radioactive

zde je moje řešení v Javě pomocí propojeného seznamu.

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

}

Poznámka: V tomto případě je operace pop velmi časově náročná. Takže nebudu navrhovat vytvořit frontu pomocí dvou zásobníků. 

0
Irshad ck

Odpovím na tuto otázku v Go, protože Go nemá bohatou sbírku ve své standardní knihovně.

Vzhledem k tomu, zásobník je opravdu snadné provést jsem si myslel, že bych se pokusit použít dva zásobníky k dosažení dvojité skončil fronty. Abych lépe pochopil, jak jsem dospěl k mé odpovědi, implementaci jsem rozdělil na dvě části, první část se snad snadněji pochopí, ale je neúplná.

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

Je to v podstatě dva komíny, kde je možné manipulovat s dolní částí komínů. Také jsem použil konvence pro pojmenování STL, kde tradiční Push, pop, peek operace zásobníku mají předponu front/back, ať se vztahují k přední nebo zadní frontě fronty.

Problém s výše uvedeným kódem je, že nepoužívá paměť velmi efektivně. Vlastně to roste donekonečna, dokud vám nedojde prostor. To je opravdu špatné. Oprava tohoto je jednoduše opakované použití dolní části prostoru zásobníku, kdykoli je to možné. Musíme zavést posun, abychom to mohli sledovat, protože plátek v Go nemůže růst na frontě, jakmile se zmenší.

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

Je to spousta malých funkcí, ale ze 6 funkcí 3 z nich jsou jen zrcadla druhého.

0
John Leidegren

Níže je uvedeno řešení v jazyce JavaScript pomocí syntaxe 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 };

Níže je uvedeno použití:

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


}

Pro každou operaci enqueue přidáme na vrchol zásobníku1. Pro každý dequeue vyprázdníme obsah stack1 do stack2 a odstraníme element v horní části stack.Time složitosti je O(n) pro dequeue, protože musíme kopírovat stack1 do stack2. časová složitost enqueue je stejná jako pravidelný stack

0
PradGar

S O(1)dequeue(), který je stejný jako odpověď :

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

S O(1)enqueue() (toto není zmíněno v tomto příspěvku, takže tato odpověď), která také používá backtracking k probuzení a návratu nejspodnější položky.

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

Je to samozřejmě dobré kódování, protože je neefektivní, ale přesto elegantní.

0
hIpPy