it-swarm-ru.tech

Как реализовать очередь, используя два стека?

Предположим, у нас есть два стека и нет другой временной переменной.

Можно ли «построить» структуру данных очереди, используя только два стека?

362
Nitin

Держите 2 стека, давайте назовем их inbox и outbox.

Enqueue :

  • Вставьте новый элемент в inbox

Dequeue :

  • Если outbox пуст, пополняйте его, выталкивая каждый элемент из inbox и помещая его в outbox

  • Взять и вернуть верхний элемент из outbox

Используя этот метод, каждый элемент будет в каждом стеке ровно один раз - это означает, что каждый элемент будет помещен дважды и вытолкнут дважды, что приведет к амортизации операций с постоянным временем.

Вот реализация в 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 - Как перевернуть стек

Чтобы понять, как построить очередь с использованием двух стеков, вы должны понимать, как полностью изменить стековую последовательность. Помните, как работает стек, это очень похоже на стек блюдо на вашей кухне. Последнее вымытое блюдо будет на вершине чистой стопки, которая называется L ast I n F irst O ut (LIFO) в области компьютерных наук.

Давайте представим наш стек как бутылку, как показано ниже;

 enter image description here

Если мы вставим целые числа 1,2,3 соответственно, то 3 будет на вершине стека. Поскольку 1 будет помещен первым, затем 2 будет помещен на вершину 1. Наконец, 3 будет помещен на вершину стека, и последнее состояние нашего стека, представленное в виде бутылки, будет таким, как показано ниже;

 enter image description here

Теперь наш стек представлен как бутылка, заполненная значениями 3,2,1. И мы хотим перевернуть стек так, чтобы верхний элемент стека был 1, а нижний элемент стека был 3. Что мы можем сделать? Мы можем взять бутылку и держать ее вверх дном, чтобы все значения перевернулись по порядку?

 enter image description here

Да, мы можем сделать это, но это бутылка. Чтобы сделать тот же процесс, нам нужен второй стек, который будет хранить первые элементы стека в обратном порядке. Давайте поместим наш заполненный стек слева, а наш новый пустой стек - справа. Чтобы изменить порядок элементов, мы собираемся вытолкнуть каждый элемент из левого стека и перенести их в правый стек. Вы можете видеть, что происходит, как мы делаем, на изображении ниже;

 enter image description here

Итак, мы знаем, как перевернуть стек.

B - Использование двух стеков в качестве очереди

В предыдущей части я объяснил, как мы можем изменить порядок элементов стека. Это было важно, потому что если мы помещаем элементы в стек и помещаем их в стек, выходные данные будут точно в обратном порядке очереди. Думая на примере, давайте перенесем массив целых чисел {1, 2, 3, 4, 5} в стек. Если мы вытолкнем элементы и напечатаем их до тех пор, пока стек не станет пустым, мы получим массив в порядке, обратном порядку проталкивания, который будет {5, 4, 3, 2, 1}. Помните, что для того же ввода, если мы снимаем очередь с очереди до тех пор, пока очередь не станет пустой, вывод будет {1, 2, 3, 4, 5}. Таким образом, очевидно, что для одного и того же порядка ввода элементов вывод очереди в точности противоположен выводу стека. Поскольку мы знаем, как перевернуть стек, используя дополнительный стек, мы можем построить очередь, используя два стека.

Наша модель очереди будет состоять из двух стеков. Один стек будет использоваться для операции enqueue (стек # 1 слева, будет называться стеком ввода), другой стек будет использоваться для операции dequeue (стек № 2 справа будет называться стеком вывода). Проверьте изображение ниже;

 enter image description here

Наш псевдокод, как показано ниже;


Операция постановки в очередь

Push every input element to the Input Stack

Операция 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

Давайте поставим в очередь целые числа {1, 2, 3} соответственно. Целые числа будут помещены в Input Stack (Stack # 1), который расположен слева;

 enter image description here

Что произойдет, если мы выполним операцию удаления очереди? Всякий раз, когда выполняется операция удаления очереди, очередь будет проверять, является ли стек вывода пустым или нет (см. Псевдокод выше). Если стек вывода пуст, то стек вывода будет извлечен на выходе, чтобы элементы стека ввода будет полностью изменен. Перед возвратом значения состояние очереди будет таким, как показано ниже;

 enter image description here

Проверьте порядок элементов в стеке вывода (стек № 2). Очевидно, что мы можем вытолкнуть элементы из стека вывода, чтобы вывод был таким же, как если бы мы вышли из очереди. Таким образом, если мы выполним две операции удаления очереди, сначала мы получим {1, 2} соответственно. Тогда элемент 3 будет единственным элементом выходного стека, а входной стек будет пустым. Если мы поставим в очередь элементы 4 и 5, то состояние очереди будет следующим;

 enter image description here

Теперь выходной стек не пуст, и если мы выполним операцию удаления очереди, из выходного стека будет выведено только 3. Тогда состояние будет видно как показано ниже;

 enter image description here

Опять же, если мы выполним еще две операции удаления очереди, при первой операции удаления очереди очередь проверит, пуст ли стек вывода, что является истиной. Затем выньте элементы стека ввода и вставьте их в стек вывода, пока стек ввода не будет пуст, тогда состояние очереди будет таким, как показано ниже;

 enter image description here

Легко увидеть, что результат двух операций удаления из очереди будет {4, 5}

C - Реализация очереди, построенной с двумя стеками

Вот реализация в Java. Я не собираюсь использовать существующую реализацию стека, поэтому пример здесь будет изобретать колесо;

C - 1) Класс MyStack: реализация простого стека

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: реализация очереди с использованием двух стеков

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) Демо-код

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) Пример вывода

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

Вы даже можете смоделировать очередь, используя только один стек. Второй (временный) стек может быть смоделирован стеком рекурсивных вызовов метода вставки. 

Принцип остается неизменным при вставке нового элемента в очередь: 

  • Вам необходимо перенести элементы из одного стека в другой временный стек, чтобы изменить их порядок. 
  • Затем вставьте новый элемент для вставки во временный стек
  • Затем перенесите элементы обратно в исходный стек
  • Новый элемент будет в нижней части стека, а самый старый элемент - в верхней части (сначала выскочить)

Класс Queue, использующий только один стек, будет выглядеть следующим образом:

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

Однако временные сложности были бы еще хуже. Хорошая реализация очереди делает все в постоянное время.

Правка

Не уверен, почему мой ответ был опущен здесь. Если мы программируем, мы заботимся о сложности времени, и использование двух стандартных стеков для создания очереди неэффективно. Это очень актуальный и актуальный момент. Если кто-то еще чувствует необходимость понизить это, мне было бы интересно узнать, почему.

Немного подробнее: почему использование двух стеков хуже, чем просто очереди: если вы используете два стека, и кто-то вызывает dequeue, когда исходящий ящик пуст, вам нужно линейное время, чтобы добраться до дна входящего почтового ящика ( как вы можете видеть в коде Дэйва).

Вы можете реализовать очередь в виде односвязного списка (каждый элемент указывает на следующий вставленный элемент), сохраняя дополнительный указатель на последний вставленный элемент для толчков (или делая его циклическим списком). Реализация очереди и очереди для этой структуры данных очень проста в постоянном времени. Это наихудшее постоянное время, не амортизируется. И, как кажется, в комментариях просят дать такое пояснение, постоянное время в худшем случае строго лучше, чем амортизированное постоянное время.

11
Tyler

Пусть реализуемая очередь будет q, а стеки, используемые для реализации q, будут stack1 и stack2. 

q может быть реализовано two способами:

Метод 1 (сделав операцию enQueue дорогостоящей)

Этот метод гарантирует, что вновь введенный элемент всегда находится на вершине стека 1, так что операция deQueue просто появляется из stack1. Чтобы поместить элемент на вершину стека 1, используется стек 2.

enQueue(q, x)
1) While stack1 is not empty, Push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

Метод 2 (Делая операцию deQueue дорогостоящей)

В этом методе при работе в очереди новый элемент вводится в верхней части stack1. В операции удаления из очереди, если стек2 пуст, тогда все элементы перемещаются в стек2 и, наконец, возвращается вершина стека2.

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, Push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

Метод 2 определенно лучше, чем метод 1. Метод 1 перемещает все элементы дважды в операции enQueue, в то время как метод 2 (в операции deQueue) перемещает элементы один раз и перемещает элементы, только если stack2 пуст.

7
Rahul Gandhi

Решение в 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

Вы должны вытолкнуть все из первого стека, чтобы получить нижний элемент. Затем поместите их все обратно во второй стек для каждой операции «удаления очереди».

2
user11055

для разработчика c # вот полная программа:

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

Два стека в очереди определяются как stack1 а также stack2,.

Enqueue: Элементы euqueued всегда помещаются в stack1

Dequeue: Верх stack2 может быть выдан, так как это первый элемент, вставленный в очередь, когда stack2 не пусто когда stack2 пусто, мы выталкиваем все элементы из stack1 и толкнуть их в stack2 по одному. Первый элемент в очереди помещается в нижнюю часть stack1, Это может быть выдвинуто непосредственно после операций выталкивания и нажатия, так как оно находится на вершине stack2,.

Ниже приведен тот же пример кода 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;
}

Это решение заимствовано из моего блога . Более подробный анализ с пошаговым моделированием работы доступен на моей странице в блоге.

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:

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

Пока вы получите много сообщений, связанных с реализацией очереди с двумя стеками: 1. Либо сделав процесс enQueue намного более дорогостоящим 2. Или сделав процесс deQueue намного более дорогостоящим

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

Один важный способ, который я узнал из вышеприведенного поста, заключался в создании очереди только со структурой данных стека и стеком рекурсивных вызовов.

Хотя можно утверждать, что буквально это все еще использует два стека, но в идеале это использует только одну структуру данных стека.

Ниже приводится объяснение проблемы:

  1. Объявите один стек для постановки и обработки данных и поместите данные в стек.

  2. в то время как у deQueueing есть базовое условие, когда элемент стека выскакивает, когда размер стека равен 1. Это обеспечит отсутствие переполнения стека во время рекурсии deQueue.

  3. При удалении очереди сначала вытолкните данные из верхней части стека. В идеале этот элемент будет элементом, который присутствует на вершине стека. Теперь, как только это будет сделано, рекурсивно вызовите функцию deQueue, а затем вставьте вставленный выше элемент обратно в стек.

Код будет выглядеть так:

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;

Таким образом, вы можете создать очередь, используя единую структуру данных стека и стек вызовов рекурсии.

1
Radioactive

вот мое решение в Java с использованием связного списка.

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

}

Примечание: В этом случае операция pop занимает очень много времени. Поэтому я не буду предлагать создавать очереди, используя два стека. 

0
Irshad ck

Я отвечу на этот вопрос в Go, потому что в стандартной библиотеке Go нет большого количества коллекций.

Так как стек очень прост в реализации, я решил попробовать использовать два стека для создания двусторонней очереди. Чтобы лучше понять, как я пришел к своему ответу, я разделил реализацию на две части. Надеемся, что первую часть легче понять, но она неполна.

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

В основном это два стека, где мы позволяем друг другу манипулировать основанием стеков. Я также использовал соглашения об именах STL, где традиционные операции Push, Pop, Peek в стеке имеют префикс перед/назад, независимо от того, ссылаются они на начало или конец очереди.

Проблема с приведенным выше кодом заключается в том, что он не очень эффективно использует память. На самом деле, он растет бесконечно, пока вы не исчерпаете пространство. Это действительно плохо. Решением этой проблемы является простое повторное использование нижней части пространства стека, когда это возможно. Мы должны ввести смещение для отслеживания этого, так как срез в Go не может расти в передней части после сокращения.

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

Это много маленьких функций, но из 6 функций три из них являются просто зеркалами другой.

0
John Leidegren

Ниже приведено решение на языке JavaScript с использованием синтаксиса 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 };

Ниже использование:

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


}

Для каждой операции добавления в очередь мы добавляем в начало стека 1. Для каждой очереди мы сбрасываем содержимое стека 1 в стек 2 и удаляем элемент в верхней части стека. Сложность времени равна O(n) для очереди, так как мы должны скопировать стек 1 в стек 2. временная сложность enqueue такая же, как и у обычного стека

0
PradGar

С O(1)dequeue(), которая такая же, как у pythonquick's answer :

// 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)enqueue() (это не упомянуто в этом посте, так что этот ответ), который также использует возврат, чтобы всплыть и вернуть самый нижний элемент.

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

Очевидно, это хорошее упражнение по кодированию, так как оно неэффективно, но, тем не менее, элегантно.

0
hIpPy