Во время интервью стеки и очереди часто появляются парами для изучения. Эта статья содержит следующее тестовое содержимое для стека и очередей:
(1) Создание стека
(2) Создание очереди
(3) Два стека реализуют очередь
(4) Две очереди реализуют стек
(5) Разработайте стек с минимальной функцией min () и требует, чтобы временная сложность мин, толчка, поп -музыки и все это (1)
(6) Определите, согласны ли последовательности Push и POP стека
1. Создание стека:
Затем мы создаем стек в виде связанного списка, чтобы облегчить расширение.
Реализация кода:
Общедоступный класс {public node; Node = New Node (Data); } public node pop () {if (current == null) {return null; Узел помещается в стек, текущий обратный узел;} класс Node {int Data; }} public void main (String [] args) {Stack = new Stack (); pop (). Data);При входе в стек 14 или 15 строк кода являются ключом.
Эффект бега:
2. Создание очереди:
Существует две формы создания очередей: на основе реализации структуры массива (последовательная очередь) и на основе реализации связанной структуры списка (цепная очередь).
Затем мы создадим очередь в форме связанного списка, чтобы очередь была более удобной при расширении. Когда очередь будет отменена, начните с начала головки узла.
Реализация кода:
При входе в стек он такой же, как добавление узлов в обычном связанном списке;
Общественный класс queue {public Node Head; } else {current.next = new Node (data); «очередь пуст»); Data; i = 0; .out.println (queue.pop ());}}Эффект бега:
3. Два стека реализуют очередь:
Идеи:
Stack 1 используется для хранения элементов, стек 2 используется для элементов POP, отрицательные и отрицательные являются положительными.
Проще говоря, теперь поместите данные 1, 2 и 3 в стек. Это соответствует правилам очереди, то есть отрицательным и отрицательным является положительным.
Полная версия реализации кода:
Импорт java.util.stack;/*** Создан Smyhvae на 2015/9/9. Stack <Integer> Stack2 = новый стек <> (); // Stack для выполнения операции dequeue // Метод: добавить операцию по очереди в Queue public void push (int data) {Stack1.push (data);}//Метод : Дайте очередь операции Dequeue Public int pop (), бросает исключение {if (stack2.empty ()) {// Перед размещением данных в стек1 в стек. Либо данные в Stack2 были выпущены), в противном случае порядок DequeUting будет испорчен, что легко забыть, пока (! Stack1.empty ()) {Stack2.push (stack1.pop ()); // Откройте Данные в Stack1 и поместите его в Stack2 [Core Code]}} if (stack2.empty ()) {// Когда Stack2 пуст, есть две возможности: 1. В начале два стека все данные пусты; Данные в Stack2 заканчивают новое исключение («Queu пусто»); push (1); );Обратите внимание на порядок кода в строке 22 и строке 30, а также к комментариям, и вам необходимо тщательно понять его значение.
Эффект бега:
4. Две очереди реализуют стек:
Идеи:
Поместите 1, 2 и 3 в очередь 1, затем оставьте верхнюю 3 в очереди 1, поместите нижнее 2 и 3 в очередь 2 и поместите 3 из очереди 1. В это время очередь пуст, а затем все В очереди 2 остаются данные. Полем Полем Циркулировать по очереди.
Реализация кода:
Import java.util.arraydeque; импорт java.util.queue;/*** Создан Smyhvae на 2015/9/9.*/Public Class Stack {queue <Integer> queue1 = new arr aydeque <Integer> (); <Integer> queue2 = new Arraydeque <integer> (); // Метод: операция стека Public void push (int data) {queue1.add (data); int data; {data = queue1.poll (); queue1.poll ()); = new Stack (); Stack.push (1); );Эффект бега:
5. Разработайте стек с минимальной функцией min () и требует, чтобы временная сложность мин, толчка, поп и все это (1). Цель метода MIN состоит в том, что он может вернуть минимальное значение в стеке. 【Вопросы интервью WeChat】
Обычные идеи:
Вообще говоря, мы можем думать таким образом: используя переменную MIN, каждый раз, когда мы добавляем элемент, он сравнивается с элементом MIN, чтобы она мог гарантировать, что минимальное значение, хранящееся в мин, может быть гарантировано. Но в этом случае возникнет проблема: если самый маленький элемент выходит из стека, как вы можете узнать, какой из оставшихся элементов является наименьшим элементом?
Идеи для улучшения:
Здесь вам нужно добавить вспомогательный стек, чтобы обмениваться пространством на время. В вспомогательном стеке верхняя часть стека всегда сохраняет наименьшее значение в текущем стеке. Это конкретно: каждый раз, когда в исходном стеке добавляется новый элемент, сравнивается с верхним элементом вспомогательного стека Элемент большой, затем скопируйте верхний элемент вспомогательного стека в верхнюю часть вспомогательного стека;
Полная реализация кода:
Import java.util.stack;/*** Создан Smyhvae на 2015/9/9. Новый стек <Integer> (); /В вспомогательном if (minstack.size () == 0 || Data <minstack.peek ()) {minstack.push (data); Код] Метод PEEK Возвращает элемент в верхней части стека}} public int pop () data = Stack.pop (); Hollow ");} return minstack.peek ();} public static void main (string [] args) бросает исключение {minstack stach = new minstack (); Stack.push (4); Stack.pus h (3); .push (5); System.out.println (stack.min ());Эффект бега:
6. Определите, согласованы ли последовательности толкания и поп -последовательности стека:
Проще говоря: известно, что набор данных 1, 2, 3, 4 и 5 помещается в стек последовательно, поэтому есть много способов выпустить его. ?
Например:
данные:
1, 2, 3, 4, 5
Вывод 1:
5, 4, 3, 2, 1 (правильно)
Вывод 2:
4, 5, 3, 2, 1 (правильно)
Вывод 3:
4, 3, 5, 1, 2 (ошибка)
Полная версия код:
Импорт java.util.stack;/*** Создан Smyhvae на 2015/9/9.
*/
открытый класс stacktest {
// Метод: Порядок массивов Data1 указывает порядок укладки. Теперь судите, правильным ли порядок на укладку данных2.
Общественная статическая логическая последовательность (int [] data1, int [] data2) {
Stack <Integer> стек = новый стек <Integer> ();
для (int i = 0, j = 0; i <data1.length; i ++) {
stack.push (data1 [i]);
while (stack.size ()> 0 && Stack.peek () == data2 [j]) {
stack.pop ();
J ++;
}
}
return stack.size () == 0;
}
public static void main (string [] args) {
Stack <Integer> Stack = new Stack <Integer> ();
int [] data1 = {1, 2, 3, 4, 5};
int [] data2 = {4, 5, 3, 2, 1};
int [] data3 = {4, 5, 2, 3, 1};
System.out.println (SequenseSpop (data1, data2));
System.out.println (SequenseSpop (Data1, Data3));
}
}
Код является относительно кратким, но его также трудно понять, поэтому вам необходимо тщательно понять его.
Эффект бега:
Вышеупомянутые вопросы интервью о Java Stack и очереди.