Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Problem description

Use two stacks to implement a queue, complete n times to insert integer (push) at the end of the queue and delete integer (pop) at the head of the queue. Elements in the queue are of type int. Ensure that the operation is valid, that is, ensure that there are elements in the queue when the POP operation is performed.

Example:

Input: [” PSH1 PSH2 “, “”,” POP “, “POP”]

Return values: 1,2

Description:

“PSH1” : inserts 1 into the end of the queue “PSH2” : inserts 2 into the end of the queue “POP “: deletes an element and returns 1. “POP” : deletes an element and returns 2

To analyze problems

First, we need to know the difference between a queue and a stack.

  1. A queue is a first-in, first-out data structure. Elements in a queue enter the queue from the back end and exit from the front end. It’s like waiting in line for a ticket.
  2. A stack is a lifO data structure. Elements in the stack are pushed in and ejected from the top of the stack.

To implement the fifO feature of queues with two stacks, we need a stack to reverse the order in which elements are queued.

Team entry operation Push:

Since the stack is lifO and the queue is fifO, to use the stack to implement fifO, we need to put the new element at the bottom of the stack. To do this, we need to move the elements from S1 to S2, then push the new elements into S2, and then pop all the elements from S2 again into S1. This enables the new element to be pushed to the bottom of the stack.

    def push(self, node):
        # write code here
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack2.append(node)
        while self.stack2:
            self.stack1.append(self.stack2.pop())
Copy the code

Out of line operation Pop:

We can pop it directly from S1, because after the inversion, the top element in S1 is the first element on the stack, the first element in the queue.

    def pop(self):
        if self.stack1:
            return self.stack1.pop()
Copy the code

Let’s look at the complete code implementation.

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack2.append(node)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def pop(self):
        if self.stack1:
            return self.stack1.pop()
Copy the code

We can see that the time complexity of the enqueue operation is O(n) and the space complexity is also O(n). The queuing time complexity is O(1), and the space complexity is also O(1).

To optimize the

In the algorithm above, I don’t know if you noticed, but every time we push a new element, we need to move from S1 to S2, and then from S2 back to S1. This is obviously redundant. In fact, we only need to plug in S1 to join the team. In order to implement fifO, we need to reverse the elements of S1, since the first element is pushed at the bottom of the stack. We can Pop elements out of S1 and push S2. This puts S1 at the bottom of the stack at the top of the stack S2, and we pop it straight from S2. Once S2 is empty, all we have to do is transfer S1 to S2 again.

Let’s take a look at the code implementation.

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()
Copy the code