Today we continue to look at the sword finger offer series topic —- stack queue mutual implementation.

1. The sequence

Stack is a very common data structure, which is widely used in the field of computer. For example, the operating system will create a stack for each thread to store the parameters, return address and temporary variables of each function when the function is called. The characteristics of the last in first out, namely, the last pressed into the stack element will be the first to be popped.

Generally, the stack is a data structure without regard to sorting, and we need ○ (n) time to find the largest or smallest element in the stack. If you want to get the maximum or minimum value of the stack in 0(1) time, you need to make a special design for the stack. See question 3, “Stacks with min functions”.

Queues are another important data structure. Unlike stacks, queues are first-in, first-out, meaning that the first element to enter the queue will be the first to come out.

Stack and queue are two data structures with opposite characteristics, but the interesting thing is that they are related to each other. The reader may also consider how to implement a stack with two queues.

2. Stack implementation of a queue

The title

Implement a queue with two stacks. Implement appendTail and deleteHead to insert nodes at the end of the queue and delete nodes at the head of the queue, respectively.

Analysis of the

Create two stacks stack1 and Stack2 to implement a fifo queue using two fifO stacks.

Let’s examine the process of inserting and deleting elements into the queue with a concrete example. Insert element A into stack1, where {a} is in stack1 and stack2 is empty. Insert elements B and C into stack1 ({a,b, C}), where C is at the top of the stack and Stack2 is still empty.

At this point we try to remove an element from the queue. According to the first-in, first-out rule, since A is inserted into the queue before B and C, the first element to be deleted should be A. Element A is stored in Stack1, but not at the top of the stack, so it cannot be removed directly. Note that we haven’t used Stack2 yet, and now it’s time to put Stack2 to work. If we pop stack1 elements into Stack2 one by one, the order of the elements in Stack2 is exactly the reverse of the order in Stack1. So after three pop-ups to Stack1 and to Stack2, Stack1 is empty and the element in Stack2 is {c,b,a}. At this point, stack2 can pop top A. Stack1 is empty and stack2 has elements {b,a} where B is at the top of the stack.

So the idea is that when stack2 is not empty, the top element in Stack2 is the first element to be queued and can be popped. If Stack2 is empty, we pop stack1 elements one by one and push them into Stack2. Since the first queued element is pushed to the bottom of stack1, after being ejected and pushed to the top of stack2, it can be ejected directly. If a new element D is inserted, we can simply push it into Stack1.

Process diagram:

LeetCode topic

Use stacks to implement the following operations on queues:

Push (x) – Puts an element at the end of the queue.

Pop () — Removes the element from the head of the queue.

Peek () — returns the element at the head of the queue.

Empty () — Returns whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);

queue.push(2);

queue.peek(); / / returns 1

queue.pop(); / / returns 1

queue.empty(); / / returns false

Description:

You can only use standard stack operations — that is, only push to Top, peek/ Pop from Top, size, and is empty are legal.

Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.

Assume that all operations are valid (for example, an empty queue does not call pop or PEEK).

code

import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() {if(stack1.isempty () &&stack2.isempty ()){system.out.println (" exception "); Throw new RuntimeException(" exception "); }else if(stack2.isEmpty()){ while(! stack1.isEmpty()){ stack2.push(stack1.pop()); } return stack2.pop(); }else{ return stack2.pop(); } } } import java.util.Stack; public class MyQueue { private Stack<Integer> s1 ; private Stack<Integer> s2; private int front; /** Initialize your data structure here. */ public MyQueue() { s1 = new Stack<>(); s2 = new Stack<>(); } /** Push element x to the back of queue. */ public void push(int x) { s1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if (s1.isEmpty() && s2.isEmpty()) { throw new RuntimeException("Queue is empty."); }else if(s2.isempty ()){// Transfer the data from the first stack to the second stack; while(! s1.empty()){ s2.push(s1.pop()); } } return s2.pop(); } /** Get the front element. */ public int peek() {if(s1.empty() &&s2.empty ()) {throw new RuntimeException("queue is empty"); }else if(s2.isempty ()){//stackPop must be empty; while(! s1.empty()){ s2.push(s1.pop()); } } return s2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { if(s1.empty() && s2.empty()){ return true; } return false; }}Copy the code

3. Implement stacks with queues

Use queues to implement the following operations on the stack:

Push (x) — element X is pushed

Pop () — Removes the top element of the stack

Top () — Gets the top element on the stack

Empty () — Returns whether the stack is empty

Note:

You can only use the basic operations on queues — push to back, peek/pop from front, size, and is empty are legal.

Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.

You can assume that all operations are valid (for example, no pop or top operations are called on an empty stack).

Train of thought

Since the queue has a first-in, first-out feature, when the number of queue elements is stored in queue 1 and the top element C needs to be ejected, all the elements in queue 1 minus 1 are stored in queue 2 and the elements in queue 1 are ejected, so as to realize a last-in, first-out, left-right and left-right iteration until the queue is empty and an exception is thrown.

We analyze the process of simulating a stack with two queues through a series of stack push and eject operations. As shown in Figure (a), we first push an element A onto the stack. Since both queues are now empty, we can choose to insert A into either queue. We might as well plug a into Queuel. Next, we push b and C onto the stack and insert them into queuel. Queuel contains three elements a, B, and C, with a at the head of the queue.

C is at the end of the queue. Now let’s consider popping an element from the stack. According to the last in first out principle of the stack, the last is

The C stack should be the first to be ejected. Since C is at the end of queuel and we can only remove elements from the head of the queue at a time, we can remove elements A and B from Queuel and insert Queue2, and then remove element C from Queuel. This is equivalent to popping element C from the stack, as shown in Figure (b). We can pop element B from the stack in the same way, as shown in Figure (c).

Now let’s think about pushing an element D onto the stack. When queuel already has one element, we insert D at the end of queue], as shown in figure (d). If we pop another element off the stack, then the one that gets popped should be d, the last one pushed in. Since d is at the end of Queuel, we can only delete queuel’s elements from scratch and insert Queue2 until d is encountered in Queuel and then delete it directly, as shown in Figure (e).

Algorithm diagram

code

import java.util.LinkedList; import java.util.Queue; public class MyStack { /** Initialize your data structure here. */ private Queue<Integer> queue1; private Queue<Integer> queue2; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { queue1.offer(x); } /** Removes the element on top of the stack and returns that element. */ public int pop() { while (queue1.size() ! =1){ queue2.offer(queue1.poll()); } int temp = queue1.poll(); // Save this last one while (queue2.size()! = 0) { queue1.offer(queue2.poll()); } // return temp; } /** Get the top element. */ public int top() { while (queue1.size() ! = 1) { queue2.offer(queue1.poll()); } return queue1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue1.size() == 0; }}Copy the code

Please pay attention to the public number “programmer interview way” reply to “interview” to get a complete set of interview package!!

This public account to share their own from programmer xiao Bai to experience spring recruitment autumn recruitment cut more than 10 offer interview written test experience, including [Java], [operating system], [computer network], [design mode], [data structure and algorithm], [Dacheng face by], [database] look forward to you join!!

Quality articles recommended:

1. Computer network —- Three times shake hands four times wave hands

2. Dream come true —– Project self-introduction

3.IntelliJ IDEA 2020.3.2 Activation cracking (with installation package and patch, activation code)

4. Shocked! Check out this programmer interview manual!!

5. Teach you the interview “Profile” word for word

6. Nearly 30 interviews shared

7. Here are the free books you asked for