Offer 09. Implement queue with two stacks

Title description:

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)

Example 1:
Input: [" CQueue appendTail ", ""," deleteHead ", "deleteHead"] [[], [3], [], []] output: [3, null, null, 1]Copy the code
Example 2:
Input: [" CQueue deleteHead ", ""," appendTail ", "appendTail", "deleteHead", "deleteHead"] [[], [], [5], [2], [], []] output: [null, 1, null, null, 5, 2]Copy the code
Tip:
1 <= values <= 10000 Calls to appendTail and deleteHead are performed at most 10000 timesCopy the code

Directions: For this part,

First of all, let’s look at the requirements of this problem. It’s easier to understand. First, understand the characteristics of these two data structures:

  • Stack is first in last out
  • The queue is first in, first out

With this basic concept in mind, we can see that the problem is to implement a fifO queue with two fifO stacks. So, we can maintain two stacks, the first for insert and the second for delete.

The sample is a little hard to understand when you first look at it, but it’s actually quite easy to understand once you know what each function means. The input is two lines: The first line is the function that executes, Cqueue for creating the queue (the two stacks we initialized), appendTail for enqueuing (stackA unqueuing), deleteHead for unqueuing (stackB unqueuing)

The second line inputs the values that are passed to each function. We find that only appendTail has the corresponding values because that function is the only one that passes the arguments.

Let’s look at the solution implementation:

Code implementation:

type CQueue struct { stack1, stack2 *list.List } func Constructor() CQueue { return CQueue{ stack1: list.New(), stack2: list.New(), } } func (this *CQueue) AppendTail(value int) { this.stack1.PushBack(value) } func (this *CQueue) DeleteHead() int { // If the second stack is empty if this.stack2.Len() == 0 {for this.stack1.Len() > 0 { this.stack2.PushBack(this.stack1.Remove(this.stack1.Back())) } } if this.stack2.Len() ! = 0 { e := this.stack2.Back() this.stack2.Remove(e) return e.Value.(int) } return -1 }Copy the code

Conclusion:

In addition to implementing the queue with two stacks, you can also implement the stack with queue 225. The idea is also to use the characteristics of the queue. You need to be familiar with the properties of the two data structures to figure out how to perform the transformation. The next step is to think about optimizing time complexity and simplifying code.