A - Как перевернуть стек
Чтобы понять, как построить очередь с использованием двух стеков, вы должны понимать, как полностью изменить стековую последовательность. Помните, как работает стек, это очень похоже на стек блюдо на вашей кухне. Последнее вымытое блюдо будет на вершине чистой стопки, которая называется L ast I n F irst O 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 слева, будет называться Input Stack), другой стек будет использоваться для операции dequeue (стек # 2 справа, будет называться Output Стек). Проверьте изображение ниже;
Наш псевдокод, как показано ниже;
Операция постановки в очередь
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} соответственно. Целые числа будут помещены во входной стек ( Stack # 1 ), расположенный слева;
Тогда что будет, если мы выполним операцию удаления очереди? Всякий раз, когда выполняется операция удаления очереди, очередь будет проверять, является ли стек вывода пустым или нет (см. Псевдокод выше). Если стек вывода пуст, то стек вывода будет извлечен на выходе, чтобы элементы стека ввода будет полностью изменен. Перед возвратом значения состояние очереди будет таким, как показано ниже;
Проверьте порядок элементов в стеке вывода (стек № 2). Очевидно, что мы можем вытолкнуть элементы из стека вывода, чтобы вывод был таким же, как если бы мы вышли из очереди. Таким образом, если мы выполним две операции удаления очереди, сначала мы получим {1, 2} соответственно. Тогда элемент 3 будет единственным элементом выходного стека, а входной стек будет пустым. Если мы поставим в очередь элементы 4 и 5, то состояние очереди будет следующим:
Теперь выходной стек не пуст, и если мы выполним операцию удаления очереди, из выходного стека будет выведено только 3. Тогда состояние будет выглядеть так:
Опять же, если мы выполним еще две операции удаления очереди, при первой операции удаления очереди очередь проверит, пуст ли стек вывода, что является истиной. Затем вытащите элементы стека ввода и вставьте их в стек вывода, пока стек ввода не будет пуст, тогда состояние очереди будет таким, как показано ниже;
Легко увидеть, результат двух операций удаления из очереди будет {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