Train of thought

Since we’re using stacks to simulate queues, we first need to clarify two concepts: stacks and queues. Those of you who have studied data structures should be familiar with this concept, so you can skip the concept part.

Basic concepts of queues

The concept of the queue should be familiar to everyone, everyone from childhood to the queue should be many. First come, first served. Take a look at baidu Baike’s definition:

A queue is a special kind of linear table, special in that it only allows deletion at the front of the table and insertion at the rear. Like a stack, a queue is a linear table with limited operation. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue.

From the above definition, we can see that to implement a queue, in addition to the size() and empty() API of the linear table itself, we also need to implement push(), that is, insert an element from the end of the table; Pop (), which removes an element from the table header, and front(), which fetches data from the table header, and back(), which fetches elements from the table tail.

Let’s look at a specific example:

There are 5 elements 1,2,3,4,5 join the team in turn. What is the order in which they leave the team?

I know from life experience that it’s 1,2,3,4,5, and it’s easy to see that the character of the queue is first in, first out

Basic concepts of stacks

In Baidu encyclopedia, stack is explained as follows:

A stack, also known as a stack, is a linear table with limited operations. Defines linear tables that only perform insert and delete operations at the end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack. Adding a new element to a stack is also called pushing, pushing, or pushing. It is done by placing the new element on top of the top element to make it the new top element. To remove an element from a stack is also called to stack or unstack. It is to remove the top element from the stack so that the adjacent element becomes the new top element.

From the above definition, we can see that to implement a stack, in addition to the size() and empty() API of the linear table itself, we need to implement push(), that is, to insert an element from the end of the table; Pop () removes an element from the end of the table, and a top() fetches data from the end of the table. In general, this end of the table is called the top of the stack and the other end is called the bottom of the stack (see figure below).

Let’s look at the characteristics of the stack:

There are 5 elements 1,2,3,4, and 5 on the stack. What is the order of their removal from the stack?

5,4,3,2,1

The reader who is good at summing up can easily see that the stack is characterized by last in, first out, which is key to our problem solving.

Analysis of the

We have two tables, each with push(), pop(), top(), size() and empty() apis for us to use. Then the data structure we want to implement is a linear table with push(), pop(), front(), back(), size(), empty() six apis, among which the core difference is the implementation of pop(), because the pop() of the two is just opposite. But we have two stacks! One stack is last in, first out. There is an idea in mathematics that two negatives make a positive. Can two stacks achieve first in, first out? Let’s take a look at this picture.

Let’s take the example of 1,2,3,4,5. Let’s put 1,2,3,4,5 in inStack, and then let’s take the elements off the stack and put them in outStack, and then let’s see if the stack order becomes 1,2,3,4,5. See here, believe clever you had the train of thought that realizes certainly! Let’s take a look at the JS implementation.

implementation

JS does not implement Stack and Queue for us, but the array in JS is very powerful, can be regarded as a two-way Queue, can be accessed from both ends and can be evaluated by index, so here we use the array in JS instead of Stack, can only use pop() and push().

class Queue {
  constructor() {
    //inStack processes input
    this.inStack = [];
    //outStack handles the output
    this.outStack = [];
  }

  / * * *@description The simulated queue inserts data at the end of the queue *@param {number} val* /
  push(val) {
    this.inStack.push(val);
  }

  / * * *@description The simulated queue removes data from the queue header *@returns {number} Returns the deleted value */
  pop() {
    // If the output stack is empty, the input stack will be reloaded once
    if (!this.outStack.length) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop()); }}return this.outStack.pop();
  }

  / * * *@description Read queue header data */
  front() {
    // If the output stack is empty, the input stack will be reloaded once
    if (!this.outStack.length) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop()); }}// Get the value at the top of the output stack
    return this.outStack[this.outStack.length - 1];
  }

  / * * *@description Take the last element *@returns {number} Return the last queue element */
  back() {
    // If the input stack is not empty, the element at the top of the stack is the element at the end of the queue
    if (this.inStack.length) {
      return this.inStack[this.inStack.length - 1];
      // Otherwise, the bottom element of the output stack is the bottom element of the queue.
    } else {
      //PS: The standard Stack does not have a way to fetch the bottom of the Stack, here is to achieve a complete queue, refer to LeetCode 232 for real problems
      return this.outStack[0]; }}/ * * *@description Checks whether the queue is empty *@returns {boolean}* /
  empty() {
    return !this.inStack.length && !this.outStack.length; }}// a simple test
const q = new Queue();
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
console.log(q.front());
console.log(q.back());
q.pop();
console.log(q.front());

Copy the code

The output

$ node stack_mock_queue.js 
1
5
2
Copy the code

Time/space complexity

A good algorithm is one that can withstand both time complexity and space complexity.

In this case, it’s easy to say that the space is O(n), because you push n elements into the queue, and the length of the queue is n.

The time complexity of push() is O(1). Pop () is one of the core methods in this problem. We use the idea of limit to analyze its time complexity.

Suppose the caller performs 1000 consecutive push operations and then 1000 consecutive POP operations. It is not difficult to analyze that in 1000 pop operations, only the time complexity of the first pop operation will reach O(n), because the data needs to be poured from the input stack to the output stack, and then O(1) each time, so that the amortization, It can be approximated that the time complexity of each operation is O(1).

At the other extreme, suppose the caller does 2000 operations, pop every push and reverse every pop, but note that the time complexity of this reverse is also very low, because there is only one data, so the time complexity is constant, O(1).

To sum up, in both extreme cases, the amortized time complexity is O(1), and in other cases, the amortized time complexity is only between the two. Therefore, in general, the amortized time complexity is also O(1). Now, for those of you who have studied advanced mathematics, the squeeze theorem should make a lot of sense.