The algorithm questions will not explain the basic concepts, if you do not know the stack and queue, you may need to understand the first. If you have studied it before but have forgotten it, you can use this article to recall the details. This article will include codes, students with general code ability are advised to complete the reading on the computer.

Problem description

  1. How to implement fixed length stacks and queues with arrays? 【 basis 】
  2. How do I implement a stack using only queues? [With certain skills]
  3. How do I implement a queue using only stacks? [With certain skills]
  4. How do you implement a minimum stack, that is, a stack with functions that return a minimum? [With certain difficulty and skill]

Use arrays to implement a fixed-length stack

For most of us, this question is just a passing question. Of course, in the context of interview, how to ensure that we can complete this question quickly and accurately needs to test our coding ability. For students who think they have a good foundation, it is recommended to spend one or two minutes thinking about the design of push and POP functions, and then look down to verify. For those of you who think the basics are average, it is recommended that you spend 5-10 minutes writing the code and then verify it. Had not learned to the classmate, the proposal sees train of thought can.

Without further ado, we all know the characteristics of the stack: fifo, LIFO (FILO), so the key consideration is how to design the push and pop functions.

First we build a stack class:

class Stack {
    vector<int> arr;
    int size; // The current stack length
public:
    Stack(int len) { // Len is the initialization size
        arr.resize(len); // To allocate space for the array, call arr.size() to get this len
        size = 0; }};Copy the code

Push, first of all, is bound, if the stack is full, we can’t keep adding to the array, otherwise we’ll overflow; For push, it’s very convenient and neat to use size++, because size starts at 0, and the first position has a zero subscript, and when we push a number in, size should increase by one.

void push(int num) {
    if (size == arr.size()) { // Boundary, which is easy to ignore in an interview
        throw "the stack is full!";
    }
    arr[size++] = num;
}
Copy the code

The pop function, again, is bound, if the stack is already empty, then it can’t be pushed; We don’t need to do anything special with the data being pushed out, we actually just need to mark the current stack length.

int pop(a) {
    if (size == 0) { // If the stack is empty, it is no longer pushed
        throw "the stack is empty!";
    }
    return arr[--size];
}
Copy the code

In addition, we are mimicking the pop-up writing of the stack in Java, unlike CPP where there is no return value, we will return the value of the pushed number.

Use arrays to implement fixed length queues

The so-called queue, namely first in first out, last in last out (FIFO) structure. So, with the experience of writing stacks, I’m not going to talk about it here, but I’m still going to focus on boundaries, and of course queues are going to make the most of array space, so we need two variables, one at the beginning and one at the end.

Construct the queue class:

class Queue {
    vector<int> arr;
    int size;  // The current queue length
    int begin; // Start position subscript
    int end; 	 // End position subscript
public:
    Queue(int size) {
        arr.resize(size);
        size = 0;
        begin = 0;
        end = 0; }};Copy the code

Push function:

void push(int num) {
    size++;
    arr[end] = num;
    end = (size == arr.size() - 1)?0 : end + 1;
}
Copy the code

Note that when end reaches the end of the array but the current length is less than the size of the array, there is space in the front of the array (begin > 0).

If size is equal to arr.size() -1, the current queue has reached the end and end needs to return to the beginning. Otherwise, end can be moved back.

Pop function:

int pop(a) {
    if (size == 0) { // The queue is empty and cannot be popped again.
	      throw "the queue is empty!!";
        return NULL;
    }
    int tmp = begin;
    size--;
    begin = (begin == arr.size() - 1)?0 : begin + 1;
    return arr[tmp];
}
Copy the code

Begin = (begin == arr.size() -1)? 0 : begin + 1; If begin reaches the end of the queue and pop pops, begin needs to return to the beginning of the array. Otherwise, begin increments.

How do I implement a stack using only queues

Using only queues to implement a stack, if you haven’t seen this problem before, it may seem confusing at first glance, but you often ignore the number of queues. We can actually do this using two queues.

As shown in the figure below, we use two queues, Queue and help, to implement the stack:

First we put three numbers in queue˙. Notice we’re using a queue. Now we want to pop up 3, and the queue can only take the first number, so we have to do something different:

  1. queue.size() > 1That will bequeueThe team leader pops up and presses inhelp;
  2. queue.size() > 1That will bequeueThe team leader pops up and presses inhelp;
  3. queue.size() == 1, holds the current queue head (top element), which is the number we will return later;

  1. And the most critical step we’re going to takequeueandhelpExchange:
  2. Return the previously cached top of the stack element.

At this point, we’re basically done with the pop function, and the push function, which actually determines the boundary (if any), can be put in the queue.

Code implementation:

class Stack{
    queue<int> my_queue;	// Data queue
    queue<int> help;			// Secondary queue
public:
    void push(int num) { // I'm not using a fixed array here, so I don't need to judge the bounds
        my_queue.push(num);
    }
  
    int pop(a) {
        if (my_queue.empty()) {// Determine the boundary
            cout<<"the stack is empty!"<<endl;
            return NULL;
        }
        while (my_queue.size(a) >1) {
            help.push(my_queue.front());
            my_queue.pop(a); }int res = my_queue.front(a);// hold the top element of the stack
        my_queue.pop(a);swap(a);// Exchange two queues
        return res;
    }

    void swap(a) {
        queue<int> temp = my_queue; my_queue = help; help = temp; }};Copy the code

How do I implement a queue using only stacks

With the previous experience of implementing stacks with queues, it’s easier to consider implementing queues with stacks. Again, we use two stacks to implement queues.

Queues are fifO and stacks are lifO, so how do we do that with stacks? You might have already figured it out: dumping one stack into another:

The key part is that we only need to dump all the data in pushStack into popStack each time we reverse the stack, and only reverse the stack when popStack is empty. (Can you think about why?)

Reverse stack operation:

void pushToPop(a) {
   while(! push_stack.empty()) {
     pop_stack.push(push_stack.top());
     push_stack.pop();
   }
}
Copy the code

Other parts of code:

class Queue{
    stack<int> push_stack;
    stack<int> pop_stack;

    void pushToPop(a) {... }public:
    void push(int num) {
        push_stack.push(num);
    }

    int pop(a) {
        if (pop_stack.empty()) {
            pushToPop(a); }if(pop_stack.empty()) {
            cout <<"the queue is empty!" << endl;
        }
        int top = pop_stack.top(a); pop_stack.pop(a);returntop; }};Copy the code

How do you implement a minimum stack, that is, a stack with functions that return a minimum?

This problem is more interesting, how do we implement a stack, can always get the minimum value in the stack? Some friends may say without hesitation that this is very simple, use a variable to store the minimum value. Hey, that’s one thing I forgot. Stacks change. If the current top of the stack is the minimum, where do you find the minimum after you pop it out?

Most of you are confused here, so what should you do?

In fact, we simply take another stack to store the minimum value: we have a dataStack to store the data, and a minStack to store the minimum value. So how do YOU store the minimum?

Parallel storage with the data stack, that is, the length of the minimum stack is the same as the length of the data stack, each data represents the minimum value of the stack under the same length.

Let me draw a picture to show you:

  1. When we first press in2Because at this timeminStackforempty, soDirectly into theCan;
  2. When we press in3At this time3 > minStack.top()namely3 > 2Therefore, we press in the current minimum value2;
  3. When we press in1At this time1 < minStack.top()namely1 < 2, so we press in the new minimum1.
  4. Bouncing stacks is even easier,minStackJust followdataStackThe bomb stack can be.

The code implementation is as follows:

class MinStack {
    stack<int> data_stack; / / the data stack
    stack<int> min_stack;  / / minimum stack
public:
    void push(int num) {
        if (min_stack.empty()) { // minStack is empty
            min_stack.push(num);
        } else if (min_stack.top() < num) { // If the newly pushed value is greater than the minimum value, the minimum value is still pushed
            min_stack.push(min_stack.top());
        } else { // Otherwise push the new minimum
            min_stack.push(num);
        }
        // Just push the data in any case
        data_stack.push(num);
    }

    int top(a) {
        return data_stack.top(a); }int pop(a) {
        int top = data_stack.top(a); min_stack.pop(a); data_stack.pop(a);return top;
    }

    int getMin(a) { // Use STL to implement the boundary
        return min_stack.top();
    }
};
Copy the code