Эта статья была включена в серию Github «Алгоритм обучения Xiaobai»:GitHub.com/VIP камень/Али…
мы говорили об этом раньше«Реализация очереди с двумя стеками», а сегодня мы поговорим о "реализации стеков с помощью очередей", это все общие вопросы на собеседовании, и сегодня мы будем использовать различные методы для реализации "перехода" от очередей к стекам.
Старые правила, давайте рассмотрим характеристики и общие методы стека и очереди.
Стек представляет собой структуру данных по принципу «последний пришел – первый ушел» (LIFO). Распространенными методами являются следующие:
- push(): метод push, добавление элементов на вершину стека;
- pop(): метод pop, удаляет элемент из вершины стека и возвращает элемент;
- peek(): Запрашивает верхний элемент стека и не удаляет этот элемент.
Очередь – это структура данных по принципу "первым поступил – первым обслужен" (FIFO). Распространенными методами являются следующие:
- offer(): метод Enqueue, добавление элементов в конец очереди;
- poll(): метод удаления из очереди, удаление и возврат элементов из головы очереди;
- peek(): Запрашивает головной элемент очереди и не удаляет этот элемент.
Зная эти основы, давайте посмотрим на сегодняшний вопрос.
Описание темы
Используйте стек реализации очереди:
Push (X) - Push Element X на стек
pop() -- удаляет верхний элемент из стека
top() -- получить верхний элемент стека
empty() -- возвращает, пуст ли стек
Уведомление:
- Вы можете использовать только основные операции с очередью, т. е. отодвигать назад, заглядывать/выталкивать спереди, размер и пусто;
- Используемый вами язык может не поддерживать очереди. Вы можете использовать list или deque (двусторонняя очередь) для имитации очереди, если это стандартная операция с очередью;
- Вы можете предположить, что все операции допустимы (например, операции pop или top не будут вызываться для пустого стека).
Тематический анализ
Название этого вопроса легко понять:Вам нужно только преобразовать очередь FIFO в «стек» LIFO., мы можем реализовать эту функцию с нескольких направлений, например, используя две очереди для вставки и обмена, или очередь для вставки и обмена, или двустороннюю очередь для достижения этой функции, конкретный метод реализации и код следующим образом.
Метод реализации 1: два стека реализации очереди
В статье, где мы реализовали очередь с двумя стеками, в основном использовалась идея «отрицательное и отрицательное есть положительное».Когда вы видите этот вопрос, первое, о чем вы должны подумать, это использовать две очереди для реализации стека Однако идея реализации здесь немного отличается от идеи использования стека для реализации очереди, потому что очередь в порядке поступления, мы можем понимать это как «положительное число», поэтому идея «отрицательное и отрицательное» не может быть использовано сейчас,Мы используем две очереди для реализации стека здесь Основная идея операции состоит в том, чтобы сначала вставить элементы во временную очередь, а затем вставить все элементы другой очереди в хвост временной очереди, чтобы реализовать последний в очереди. функция первого выхода., а конкретные шаги реализации заключаются в следующем.
шаг первый
Добавьте первый элемент, поставьте его во временную очередьqueue2:
Шаг 2
Поскольку в формальной очереди нет элементов, нет необходимостиqueue1Элементы перемещаются во временную очередьqueue2В конце просто поменяйте местами временную очередь и формальную очередь напрямую:
Шаг 3
Добавить второй элемент, поставленный первым во временную очередьqueue2:
Шаг 4
опять такиqueue1переместить элементы вqueue2Хвост , как показано ниже:
Шаг 5
опять такиqueue1а такжеqueue2Обмен:
Шаг 6
Чтобы выполнить операцию удаления из очереди:
окончательный эффект
Из окончательного рендеринга мы видим, что реализована функция «последний вошел — первый вышел» через две очереди, то есть преобразование из очереди в стек завершено Код реализации выглядит следующим образом:
import java.util.Queue;
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedBlockingQueue();
queue2 = new LinkedBlockingQueue();
}
/**
* 入栈
*/
public void push(int x) {
// 1.入列临时队列二
queue2.offer(x);
// 2.将队列一的所有元素移动到队列二
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
// 3.队列一和队列二互换
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/**
* 出栈并返回此元素
*/
public int pop() {
return queue1.poll();
}
/**
* 查询栈顶元素
*/
public int top() {
return queue1.peek();
}
/**
* 判断是否为空
*/
public boolean empty() {
return queue1.isEmpty();
}
}
Мы отправляем приведенный выше тестовый код в LeetCode, и результаты выполнения следующие:
Этот метод надежен и побеждает 100% пользователей.
Реализация 2: стек реализации очереди
Так можем ли мы использовать очередь для реализации стека? Ответ положительный.
Нам нужно только выполнить следующие два шага, чтобы преобразовать очередь в стек.Конкретные шаги реализации таковы:
- поставить элементы в конец очереди;
- Затем все элементы, кроме хвоста очереди, удаляются и перезаписываются в столбец.
После этой операции последний элемент в конце очереди становится головным элементом, который реализует функцию «последним пришел — первым ушел», как показано на следующем рисунке.
шаг первый
Элемент 1 ставится в очередь:
Шаг 2
Элемент 2 ставится в очередь:
Шаг 3
Извлеките из очереди и повторно поставьте в очередь все элементы перед последним элементом, который является элементом 1:
Шаг 4
Чтобы выполнить операцию удаления из очереди:
окончательный эффект
Кодекс реализации вышеуказанной идеи заключается в следующем:
import java.util.Queue;
class MyStack {
Queue<Integer> queue1;
public MyStack() {
queue1 = new LinkedBlockingQueue();
}
/**
* 入栈
*/
public void push(int x) {
// 获取原队列长度（要移动的次数）
int count = queue1.size();
// 将元素放入队尾
queue1.offer(x);
// 将除最后一个元素外，其他的元素重新入队
for (int i = 0; i < count; i++) {
System.out.println("for");
queue1.offer(queue1.poll());
}
}
/**
* 出栈并返回此元素
*/
public int pop() {
return queue1.poll();
}
/**
* 查询栈顶元素
*/
public int top() {
return queue1.peek();
}
/**
* 判断是否为空
*/
public boolean empty() {
return queue1.isEmpty();
}
}
Представляем вышеуказанный код в LeetCode, результаты выполнения следующие:
Этот метод по-прежнему очень стабилен и также превосходит 100% пользователей, но этот метод имеет лучшую производительность с точки зрения памяти.
Метод реализации 3: стек реализации двусторонней очереди
Если вы считаете, что описанный выше метод сложен, наконец, у нас есть более простой метод реализации, мы можем использовать двустороннюю очередь в Java.ArrayDequeЧтобы понять, что элементы могут быть вставлены в голову или хвост очереди, и то же самое может быть удалено, тогда мы можем войти из хвоста очереди, а затем выйти из хвоста очереди, тем самым реализуя функцию стека. .
Двусторонняя структура очереди выглядит следующим образом:
Давайте продемонстрируем конкретные шаги для реализации стека с двусторонней очередью.
шаг первый
Элемент 1 ставится в очередь:
Шаг 2
Элемент 2 поставлен в очередь (хвост очереди):
Шаг 3
Затем выйдите из конца очереди:
окончательный эффект
Код реализации вышеуказанной идеи выглядит следующим образом:
import java.util.ArrayDeque;
class MyStack {
ArrayDeque<Integer> deque;
public MyStack() {
deque = new ArrayDeque<>();
}
/**
* 入栈
*/
public void push(int x) {
deque.offer(x);
}
/**
* 出栈并返回此元素
*/
public int pop() {
return deque.pollLast();
}
/**
* 查询栈顶元素
*/
public int top() {
return empty() ? -1 : deque.peekLast();
}
/**
* 判断是否为空
*/
public boolean empty() {
return deque.isEmpty();
}
}
Мы отправляем вышеуказанный код в LeetCode, а результат выполнения выглядит следующим образом:
Суммировать
В этой статье мы реализовали преобразование очереди в стек тремя способами, самый простой способ — использовать двустороннюю очередь, которая идет в комплекте с JavaArrayDequeСтек реализуется заходом с конца очереди и выходом с конца очереди, два других метода используют обычную очередь, а функция стека реализуется методом перемещения элемента в конец очереди. очереди после входа в очередь.
Друзья, вы узнали?
Благосостояние в конце статьи: Поиск общедоступной учетной записи «Китайское сообщество Java», чтобы отправить «интервью», чтобы получить последние материалы интервью.