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

Редактировать

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

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

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

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

Оставьте 2 стека, назовем их inbox и outbox.

Поставить в очередь:

• Вставьте новый элемент в 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();
    }

}

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

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

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

Класс 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();
    }
}

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. временная сложность постановки в очередь такая же, как у обычного стека

Два стека в очереди определены как стек1 и стек2.

Поставить в очередь: Элементы из очереди всегда помещаются в стек1

Удалить из очереди: Верхняя часть стек2 может быть выдвинута, поскольку это первый элемент, вставленный в очередь, когда стек2 не пуст. Когда стек2 пусто, мы извлекаем все элементы из стек1 и помещаем их в стек2 один за другим. Первый элемент в очереди помещается в конец стек1. Его можно вынуть сразу после операций выталкивания и нажатия, поскольку он находится в верхней части стек2.

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

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

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

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

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

Этот метод гарантирует, что вновь введенный элемент всегда находится наверху стека 1, так что операция deQueue просто появляется из стека 1. Чтобы поместить элемент вверху stack1, используется 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.

Метод 2 (сделав операцию deQueue затратной)

В этом методе при операции en-queue новый элемент вводится наверху stack1. В операции удаления из очереди, если stack2 пуст, все элементы перемещаются в stack2 и, наконец, возвращается вершина 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.

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

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

        }
    }

Я отвечу на этот вопрос в 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 в стеке имеют префикс front / back независимо от того, относятся ли они к передней или задней части очереди.

Проблема с приведенным выше кодом заключается в том, что он не очень эффективно использует память. На самом деле он бесконечно растет, пока у вас не закончится место. Это действительно плохо. Чтобы исправить это, просто повторно используйте нижнюю часть пространства стека, когда это возможно. Мы должны ввести смещение, чтобы отслеживать это, поскольку срез в 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 функций 3 являются просто зеркалами другой.

Реализация очереди с использованием двух объектов java.util.Stack:

public final class QueueUsingStacks<E> {

        private final Stack<E> iStack = new Stack<>();
        private final Stack<E> oStack = new Stack<>();

        public void enqueue(E e) {
            iStack.push(e);
        }

        public E dequeue() {
            if (oStack.isEmpty()) {
                if (iStack.isEmpty()) {
                    throw new NoSuchElementException("No elements present in Queue");
                }
                while (!iStack.isEmpty()) {
                    oStack.push(iStack.pop());
                }
            }
            return oStack.pop();
        }

        public boolean isEmpty() {
            if (oStack.isEmpty() && iStack.isEmpty()) {
                return true;
            }
            return false;
        }

        public int size() {
            return iStack.size() + oStack.size();
        }

}

A - Как перевернуть стек

Чтобы понять, как построить очередь с использованием двух стеков, вы должны понимать, как полностью перевернуть стек. Помните, как работает стопка, она очень похожа на стопку посуды на вашей кухне. Последняя вымытая тарелка будет наверху чистой стопки, которая в информатике называется Last яn First Оut (LIFO).

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

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

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

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

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

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

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

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

Наш псевдокод выглядит следующим образом:

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

Push every input element to the Input Stack

Операция удаления из очереди

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} соответственно. Целые числа будут помещены в Входной стек (Стек # 1), который расположен слева;

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

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

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

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

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

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

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

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

для разработчика 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();
        }
    }
}

Решение на 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();
    }
}

вот мое решение в 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 занимает очень много времени. Поэтому я не буду предлагать создавать очередь из двух стеков.

С O(1)dequeue(), который совпадает с отвечать в 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()

С 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

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

Реализация очереди с использованием двух стеков в 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. Либо сделав процесс enQueue намного более дорогостоящим. 2. Или сделав процесс deQueue намного более дорогостоящим.

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

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

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

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

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

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

3. Во время deQueueing сначала извлекайте данные из вершины стека. В идеале этот элемент должен быть элементом, который находится наверху стека. Теперь, когда это будет сделано, рекурсивно вызовите функцию 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;

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

Ниже приведено решение на языке 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.info(que.dequeue());  //output: "A"

Реализуйте следующие операции очереди, используя стеки.

push (x) - переместить элемент x в конец очереди.

pop () - удаляет элемент из очереди.

peek () - Получить передний элемент.

empty () - Вернуть, пуста ли очередь.

class MyQueue {

  Stack<Integer> input;
  Stack<Integer> output;

  /** Initialize your data structure here. */
  public MyQueue() {
    input = new Stack<Integer>();
    output = new Stack<Integer>();
  }

  /** Push element x to the back of queue. */
  public void push(int x) {
    input.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
    peek();
    return output.pop();
  }

  /** Get the front element. */
  public int peek() {
    if (output.isEmpty()) {
        while(!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
  }

  /** Returns whether the queue is empty. */
  public boolean empty() {
    return input.isEmpty() && output.isEmpty();
  }
}

** Решение Easy JS **

• Примечание. Я взял идеи из комментариев других людей.

/*

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.

*/
class myQueue {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    push(item) {
        this.stack1.push(item)
    }

    remove() {
        if (this.stack1.length == 0 && this.stack2.length == 0) {
            return "Stack are empty"
        }

        if (this.stack2.length == 0) {

            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }
        return this.stack2.pop()
    }


    peek() {
        if (this.stack2.length == 0 && this.stack1.length == 0) {
            return 'Empty list'
        }

        if (this.stack2.length == 0) {
            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }

        return this.stack2[0]
    }

    isEmpty() {
        return this.stack2.length === 0 && this.stack1.length === 0;
    }

}

const q = new myQueue();
q.push(1);
q.push(2);
q.push(3);
q.remove()

console.info(q)