Recently I saw an interview post about “how to use two stacks to achieve the operation of the queue”, curious I also want to try this topic, at first glance this topic is quite easy ah, well, it is not difficult. Let me just tell you a little bit about the solution that came to mind when I first saw this problem. So let’s talk a little bit about stacks and queues in data structures, just in case you don’t understand stacks and queues, you can’t go on.

The stack (stack)(wiki)

We often hear the term “stack” in interviews, and understanding this concept is critical to understanding how programs work. The word stack has different meanings in different contexts. Next I will explain the three meanings of the Stack (see the Three Meanings of Stack).

  • Meaning 1: Data structure

That’s what we’re talking about here. A stack is a structure that stores data, characterized by LIFO, or last in First out.

​

The bottom of this data structure is to use a linked list to reality, the biggest characteristic is that only the operation of the top elements, so the advanced stack is pressed below the stack can only be out.

This data structure typically operates on the uppermost element in the following ways:

Push: into the stack

Pop: out of the stack

Top: Gets the top element on the stack

Empty: Checks whether the stack is empty

  • Meaning two: How the code is run

    The second meaning of stack is “call stack”, which means that functions are stacked like building blocks to be called layer upon layer. We use the stack to achieve recursion in a function. Recursion simply means calling the function in a function.

  • Meaning three: Memory area

    The third definition of stack is an area of memory where data is stored. Programs need a certain amount of space to store data while running. Generally speaking, the system divides two different memory Spaces, one is the stack, and the other is the heap.

    The stack is automatically allocated and released by the operating system, holding function parameter values, local variable values, etc. The heap is usually allocated and released by the programmer. If the programmer does not release the heap, it may be reclaimed by the OS at the end of the program, similar to a linked list. When we talk about memory leaks, we’re talking about the heap.

After introducing the definition of stack, simply say the difference between stack and queue, the characteristics of the stack is advanced last out, the characteristics of queue is advanced first out. The focus of this question is again an understanding of the stack and queue nature, followed by some thought.

After reading this problem, I actually thought it was quite simple at first. Create two new stacks S1 and S2, and when there is a push request, first remove the data from S1 and put it into S2, then put the data from S2 into S1, and finally remove the data from S2 and put it into S1. Just push the s1 data off the stack every time there is a push request. This solution should be a more conventional solution, and relatively easy to think of.

However, if you think carefully, this method is relatively inefficient, with frequent stack and stack operations, which has a great impact on performance. Is there a better way to solve this problem? In fact, we can take the bottom element out of the stack on the way out, and push it normally on the way in. When there is a push request, the data is pushed onto S1, and when there is a push request, the data of S1 is pushed onto S2 in turn. Then, the top element of S2 is the bottom element of S1, and finally, the data of S2 is pushed onto S1 in turn. In this case, only the out of the stack operation will have frequent stack operations, and there will be no extra stack operations for the in. This is actually quite efficient.

In fact, there is a more efficient way to solve this problem. If you think about the problem, you can optimize the above solution by pushing s1 into S2 and then s1, so why should you push S2 back into S1? In fact, this operation can be avoided. We can push the data into S1 when there is a push operation, push the data in S2 when there is a push operation, and push the data in S2 when there is a push operation. If S2 is empty, all the data in S1 will be pushed into S2 in turn.

The following code is an implementation of the last method mentioned above:

#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>

using namespace std;
std: :stack<int>s1, s2;
int main(a)
{
    printf("Please input argument: 1 push, 2 pop\n");
    int operation, num;
    while(scanf("%d", &operation) ! = EOF) {if(operation == 1)
        {
            printf("please input queue push num:");
            scanf("%d", &num);
            s1.push(num);
        }
        else if(operation ==2)
        {
            if(! s2.empty()) {printf("Queue pop num: %d\n", s2.top());
                s2.pop();
            }
            else if(! s1.empty()) {while(! s1.empty()) { s2.push(s1.top()); s1.pop(); }printf("Queue pop num: %d\n", s2.top());
               s2.pop();
            }
            else
            {
                printf("queue empty\n"); }}else
        {
            printf("Input invalid, please input repeat"); }}return 0;
}
Copy the code