This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

Hey, guys. I’m balls.

Today’s stack implementation of queues is a good question to test the understanding of stacks and queues.

Rest assured, in the actual work, are not brain-dead ten, will hardly make such a strange request.

Don’t say a word. Just turn it on.

LeetCode 232: Implement queues with stacks

The question

Only two stacks are used to implement a first-in, first-out queue, which supports all operations normally supported by queues:

  • Void push(int x) : Pushes element X to the end of the queue.
  • Int POP () : Removes and returns elements from the beginning of the queue.
  • Int peek() : Returns the element at the beginning of the queue.
  • Boolean empty() : Return true if the queue is empty; Otherwise, return false.

The sample

prompt

  • 1 <= x <= 9
  • Push, POP, peek, and Empty are called up to 100 times
  • Assume that all operations are valid (eg. An empty queue does not call pop or PEEK)

title

Water problem, the difficulty is simple, mainly tests the stack and queue understanding ability.

If you’re not familiar with stacks and queues, take a look at the following article by Shuabi:

What ho! Hold the stack, queue!

If you look closely, there are four general operations involved:

  • The team a push
  • The pop team
  • Sentenced to empty empty
  • Take the first element peek

Now that you know the requirements, all that remains is how to emulate the queue with the stack.

Queue is a first in, first out (FIFO) data structure, and stack is a last in, first out (LIFO) data structure, so a stack can never meet the FIFO characteristics of queue.

Let’s say 1, 2, 3, queue 1, 2, 3 goes in, it should go out 1, 2, 3, but 1, 2, 3 goes into the stack, and it comes out as 3, 2, 1, which is the opposite of 1, 2, 3, so we need another stack to return 3, 2, 1 back to 1, 2, 3.

Therefore, we need two stacks, namely the input stack and the output stack:

The input stack reverses the queue order of elements, which can only be pushed from the input stack.

The output stack is used to store the normal order of elements, and elements can only be ejected from the output stack (POP, PEEK).

The illustration

The input and output stacks are initialized first.

Def __init__(self): self. InStack = [] self. OutStack = []Copy the code

Push (x), queue operation, directly pushed into the input stack.

Push (1), push(2).

Def push(self, x: int) -> None: self.instack.append (x)Copy the code

For push operation, the time complexity of each element is O(1) and the queue length is N, so the time complexity is O(n). Because additional stacks are required to store the elements in the queue, the space complexity is O(n).

If the output stack is empty, all elements of the input stack are pushed into the output stack, and then the top element is thrown out.

Def pop(self) -> int: empty if self.empty(): return None # If self.outstack is not empty if self.outstack: Return self.outstack.pop () # return self.outstack.pop () # return self.instack: val = self.inStack.pop() self.outStack.append(val) return self.outStack.pop()Copy the code

The time complexity of pop operations is O(n) and the space complexity is O(n).

Empty (), nulls operation. Nulling is very simple, if the input stack and output stack are both empty, the queue is empty, otherwise the queue is not empty.

If not(self. InStack or self. OutStack): return True return FalseCopy the code

There is nothing to say about this, I made a judgment, the time complexity is O(1), the space complexity is O(n).

Peek (), which takes the first element of the queue, does much the same as pop(). The only difference is that POP removes the team head element, while Peek looks at the team head element.

Def peek(self) -> int: # pop res = self.pop() # pop res = self.outstack.append (res) return resCopy the code

The first element of the queue uses the existing pop function, which has the same time and space complexity as POP, both O(n).

Code implementation

Python code implementation

class MyQueue: def __init__(self): Self. inStack = [] self.outStack = [] def push(self, x: Self.instack.append (x) def pop(self) -> int: self.instack.append (x) def pop(self) -> int: self.instack.append (x) "" post the element from in front of queue and return that element. "" # if empty if self.empty(): If self.outstack: return self.outstack.pop () # If the output stack is empty, push the input stack onto the output stack else: while self.inStack: val = self.inStack.pop() self.outStack.append(val) return self.outStack.pop() def peek(self) -> int: # pop res = self.pop() # pop res = self.pop() Append (res) return res def empty(self) -> bool: If not(self.instack or self.outstack): Returns whether the queue is empty. return True return False # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()Copy the code

Java code implementation

class MyQueue { Stack<Integer> stack1; Stack<Integer> stack2; /** Initialize your data structure here. */ public MyQueue() { stack1 = new Stack<>(); Stack2 = new Stack<>(); */ public void Push (int x) {stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { dumpStack1(); return stack2.pop(); } /** Get the front element. */ public int peek() { dumpStack1(); return stack2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); Private void dumpStack1(){if (stack2.isempty ()){while (! stack1.isEmpty()){ stack2.push(stack1.pop()); } } } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); * /Copy the code

This is the end of the diagram stack implementation queue, is not very simple, as long as you are familiar with the stack and queue.

Move your little hands and click “like”.

I’m handsome. I’ll see you next time.