During interviews, stacks and queues often appear in pairs to examine. This article contains the following test contents for stack and queues:
(1) Creation of stack
(2) Queue creation
(3) Two stacks implement a queue
(4) Two queues implement a stack
(5) Design a stack with the minimum function min(), and requires that the time complexity of min, push, pop, and all are O(1)
(6) Determine whether the push and pop sequences of the stack are consistent
1. Creation of stack:
Next, we create a stack in the form of a linked list to facilitate expansion.
Code implementation:
public class Stack {public Node head; public Node current;//Method: stack operation public void push(int data) { if (head == null) { head = new Node(data); cur rent = head; } else { Node node = new Node(data); node.pre = current;//The current node will be used as the predecessor node of the current node. Current = node; //Let the current node always point to the newly added node} } public Node pop() { if (current == null) { return null; }Node node = current; // The current node is the node we want to put on the stack. Current = current.pre; //After each node being put on the stack, , current back one return node;}class Node { int data; Node pre; //We need to know the previous node of the current node public Node(int data) { this.data = data; } }public static void main (String[] args) {Stack stack = new Stack(); stack.push(1); stack.push(2); stack.push(3);System.out.println(stack.pop().data) ; System.out.println(stack.pop().data); System.out.println(stack.pop().data); }}When entering the stack, 14 or 15 lines of code are the key.
Running effect:
2. Queue creation:
There are two forms of queue creation: based on array structure implementation (sequential queue), and based on linked list structure implementation (chain queue).
Next, we will create a queue in the form of a linked list, so that the queue will be more convenient when expanding. When the queue is dequeued, start from the beginning of the node head.
Code implementation:
When entering the stack, it is the same as adding nodes in an ordinary linked list; when dequeuing, the head nodes are always sent.
public class Queue { public Node head; public Node current;//Method: Add nodes in the linked list public void add(int data) { if (head == null) { head = new Node(data); current = head; } else { current.next = new Node(data); current = current.next; } }//Method: dequeuing the queue operation public int pop() throws Exception { if (head == null) { throw new Except ion("queue is empty"); }Node node = head; //Node node is the node we want to dequeue head = head.next; //After dequeue, move the head pointer downward return node.data;}class Node { int data; Node next;public Node(int data) { this.data = data; } }public static void main(String[] args) throws Exception { Queue queue = new Queue() ; //Enter the queue operation for (int i = 0; i < 5; i++) { queue.add(i); }//Dequeue operation System.out.println(queue.pop()); System.out.println(queue.pop()); System .out.println(queue.pop());}}Running effect:
3. Two stacks implement a queue:
Ideas:
Stack 1 is used to store elements, Stack 2 is used to pop elements, negative and negative are positive.
To put it simply, now put data 1, 2, and 3 into stack one, then come out of stack one (3, 2, 1) and put it into stack two, then the data out of stack two (1, 2. 3) It conforms to the rules of the queue, that is, negative and negative are positive.
Full version of the code implementation:
import java.util.Stack;/*** Created by smyhvae on 2015/9/9.*/public class Queue {private Stack<Integer> stack1 = new Stack<>();//Stack pr for performing enqueue operation ivate Stack<Integer> stack2 = new Stack<>();//Stack for executing dequeue operation//Method: Add an enqueue operation to the queue public void push(int data) { stack1.push(data);}/ /Method: Give the queue a dequeue operation public int pop() throws Exception {if (stack2.empty()) {//Before putting the data in stack1 into stack2, you must ensure that stack2 is empty (or It's empty at the beginning, either the data in stack2 has been released), otherwise the order of dequeuing will be messed up, which is easy to forget while (!stack1.empty()) { stack2.push(stack1.pop()) ;//Open the data in stack1 and put it into stack2 [Core Code] }}if (stack2.empty()) { //When stack2 is empty, there are two possibilities: 1. At the beginning, two stacks all data are empty; 2. The data in stack2 is finished throw new Exception("queu is empty"); } return stack2.pop(); }public static void main(String[] args) throws Exception { Queu e queue = new Queue(); queue.push(1); queue.push(2); queue.push(3);System.out.println(queue.pop());queue.push(4);System.out .println(queue.pop()); System.out.println(queue.pop()); System.out.println(queue.pop());}}Pay attention to the order of the code on line 22 and line 30, as well as the comments, and you need to carefully understand its meaning.
Running effect:
4. Two queues implement a stack:
Ideas:
Put 1, 2, and 3 into queue 1, then leave the top 3 in queue 1, put the bottom 2 and 3 into queue 2, and put 3 out of queue 1. At this time, the queue is empty, and then all the in queue 2 are left. Data is queued one; leave the top 2 in queue one and the bottom 3 in queue two. . . Circulate in turn.
Code implementation:
import java.util.ArrayDeque;import java.util.Queue;/*** Created by smyhvae on 2015/9/9.*/public class Stack {Queue<Integer> queue1 = new Arr ayDeque<Integer>(); Queue< Integer> queue2 = new ArrayDeque<Integer>();//Method: stack operation public void push(int data) { queue1.add(data); }//Method: stack operation public int pop() throws Excel tion { int data; if (queue1.size() == 0) { throw new Exception("Stack is empty"); }while (queue1.size() != 0) { if (queue1.size() == 1) { data = queue1.poll(); while (queue2.size() != 0) { //Put all the data in queue2 into queue1.add(queue2.poll()); return data; } } queue2.add(queue1.poll()); } throw new Exception("stack is empty");//I don't know what the code in this line means}public static void main(String[] args) throws Exception { Stack st ack = new Stack();stack.push(1); stack.push(2); stack.push(3);System.out.println(stack.pop()); System.out.println(stack.pop( )); stack.push(4); }}Running effect:
5. Design a stack with the minimum function min(), and requires that the time complexity of min, push, pop, and all are O(1). The purpose of the min method is: it can return the minimum value in the stack. 【WeChat Interview Questions】
Ordinary ideas:
Generally speaking, we may think this way: using the min variable, every time we add an element, it is compared with the min element, so that it can ensure that the minimum value stored in min can be guaranteed. But in this case, there will be a problem: if the smallest element is out of the stack, how can you know which of the remaining elements is the smallest element?
Improvement ideas:
Here you need to add an auxiliary stack to exchange space for time. In the auxiliary stack, the top of the stack always saves the smallest value in the current stack. It is specific: every time a new element is added in the original stack, it is compared with the top element of the auxiliary stack. If the new element is small, put the value of the new element into the auxiliary stack. If the new element is large, Then copy the top element of the auxiliary stack to the top of the auxiliary stack; when the original stack is released,
Complete code implementation:
import java.util.Stack;/*** Created by smyhvae on 2015/9/9.*/public class MinStack {private Stack<Integer> stack = new Stack<Integer>(); private S tack<Integer> minStack = new Stack<Integer>(); //Auxiliary stack: The top of the stack always saves the smallest element in the stack public void push(int data) { stack.push(data); //Add data directly to the stack//In the auxiliary If (minStack.size() == 0 || data < minStack.peek()) { minStack.push(data); } else { minStack.add(minStack.peek()); //【 Core code] The peek method returns the element at the top of the stack} } public int pop() throws Exception { if (stack.size() == 0) { throw new Exception("Empty in the stack"); }int data = stack.pop(); minStack.pop(); //Core code return data; }public int min() throws Exception { if (minStack.size() == 0) { throw new Exception("The stack is hollow") ; } return minStack.peek(); }public static void main(String[] args) throws Exception { MinStack stack = new MinStack(); stack.push(4); stack.pus h(3); stack.push(5 );System.out.println(stack.min()); }}Running effect:
6. Determine whether the push and pop sequences of the stack are consistent:
To put it simply: it is known that a set of data 1, 2, 3, 4, and 5 are put into the stack in sequence, so there are many ways to put it out. Please judge whether the given stack out is correct?
For example:
data:
1, 2, 3, 4, 5
Output 1:
5, 4, 3, 2, 1 (correct)
Output 2:
4, 5, 3, 2, 1 (correct)
Output 3:
4, 3, 5, 1, 2 (Error)
Full version code:
import java.util.Stack;/*** Created by smyhvae on 2015/9/9.
*/
public class StackTest {
//Method: The order of data1 arrays indicates the order of stacking. Now judge whether the stacking order of data2 is correct.
public static boolean sequenceIsPop(int[] data1, int[] data2) {
Stack<Integer> stack = new Stack<Integer>(); //The auxiliary stack needs to be used here
for (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(sequenseIsPop(data1, data2));
System.out.println(sequenseIsPop(data1, data3));
}
}
The code is relatively concise, but it is also difficult to understand, so you need to understand it carefully.
Running effect:
The above are classic interview questions about Java stack and queues. I hope they can help everyone pass the interview smoothly.