Stack and queue -- 232. Implement queue with stack

1 Title Description

232. Using stack to realize queue

Please use only two stacks to implement the FIFO queue . The queue should support all operations supported by the general queue （push、pop、peek、empty）：

Realization MyQueue class ：

• void push(int x) Put the element x Push to the end of the queue

• int pop() Remove from the beginning of the queue and return the element

• int peek() Returns the element at the beginning of the queue

• boolean empty() If the queue is empty , return true ; otherwise , return false
  explain ：

• you Can only Use standard stack operations —— It's just push to top, peek/pop from top, size, and is empty Operation is legal .

• The language you use may not support stacks . You can use list perhaps deque（ deque ） To simulate a stack , As long as it's a standard stack operation .

2 Title Example

Input ：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
Output ：
[null, null, null, 1, 1, false]

explain ：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

3 Topic tips

1 <= x <= 9
Call at most 100 Time push、pop、peek and empty
Suppose all operations are valid （ for example , An empty queue will not call pop perhaps peek operation ）

4 Ideas

The queue is — First in first out (first in - first out,FIFO) Data structure of , The elements in the queue are all from the back end （rear） The team (push), From the front end (front) Out of the team (pop).
The most intuitive way to implement queues is to use linked lists , But in this article I will introduce another — A way - Use stack .
A stack is a last in, first out (last in - first out,LIFO) Data structure of , Stack elements from the top of the stack (top） Push the (push), It also pops up from the top of the stack (pop). In order to satisfy the queue of FIFO Characteristics of , We need to use two stacks , Use one of them to reverse the queue order of elements , Use another to store the final order of elements .

The team (push)
One line is FIFO Of , But a stack is LIFO Of . This means that the latest pressed element must be placed at the bottom of the stack . To achieve this goal , First of all, we need to put s1 Move all elements in to s2 in , Then press the new element in s2. Finally, put s2 All elements in pop up , Then press the pop-up elements into s1.
Out of the team (pop)
Directly from s1 Just pop it up , because s1 The top element of the stack is the first element of the queue . At the same time, we pop it up s1 The top element of the stack is assigned to the first element of the team front Variable .
Judge empty (empty)
s1 All the elements of the queue are stored , So just check s1 It is OK if the is empty .
Take the team lead (peek)
In our algorithm , It was used front Variable to store the first element of the queue , This variable will be updated after each queue operation or queue operation .

5 My answer

The team

private int front;

public void push(int x) {
    
    if (s1.empty())
        front = x;
    while (!s1.isEmpty())
        s2.push(s1.pop());
    s2.push(x);
    while (!s2.isEmpty())
        s1.push(s2.pop());
}

Out of the team

// Removes the element from the front of queue.
public void pop() {
    
    s1.pop();
    if (!s1.empty())
        front = s1.peek();
}

Sentenced to empty

// Return whether the queue is empty.
public boolean empty() {
    
    return s1.isEmpty();
}

Take the team lead

// Get the front element.
public int peek() {
    
  return front;
}