This is the 9th day of my participation in the August More Text Challenge

Zero foreword

Following the previous article about using arrays to simulate linked lists, this article will show you how to use arrays to simulate stacks and queues.

For similar reasons, it is easy to implement, avoids memory leaks and facilitates debugging. The most important reason for efficiency, if you use new it’s easy to time out.

Note: this article is C++ implementation, but all languages common, will omit part of the implementation irrelevant code.

A stack

A stack, “stack,” is a limited linear list in which elements can only be inserted and deleted at the same end.

The part of the stack where insertions and deletions are allowed is called the top, and the other end is called the bottom. Inserting new elements into a stack is called pushing, and removing elements from a stack is called popping.

We can imagine a stack of plates, and each time we take the plate from the top, we put it on the top. This operation can be summed up as LIFO last in first out.

implementation

We use a top pointer to the top of the stack, which initially points to bit 0 of the array and, for nullation purposes, does not store data.

The code is very simple, so I drew a diagram to make it easier to understand:

 // STK is the stack array, N is a constant
 int stk[N], top;
 ​
 // Insert and delete
 stk[++top] = x;     // push x
 top--;              // pop
 ​
 // Check whether the stack is empty
 return top == 0;    
 ​
 // Query the top element of the stack
 return stk[top];
Copy the code

The application of stack can be seen everywhere in the computer. For example, we use program call stack every day to write code and call function. When calling function, we will store the address of the next instruction in the stack and take it back to the original program after execution. For example, expression evaluation problem, binary tree traversal, graph depth-first search, recursive call and so on.

The second queue

Queues, like stacks, are restricted to inserting on one section of the table and deleting elements on the other.

The end that allows insertion is called rear, and the end that allows deletion is called front. Adding an element to a queue is called enqueue, and deleting an element is called dequeue.

The first person in line is the first person to go out. The newcomers have to wait in a FIFO first in first out.

implementation

Use two Pointers front and rear to point to the head and rear of the team respectively, with initial values of 0 and -1 respectively. Use front > rear to judge the void. Also draw a picture for easy understanding:

 int q[N], front, rear = - 1;
 ​
 q[++rear] = x;      // enqueue
 front++;            // dequeue
 ​
 // Check whether the queue is empty
 return front > rear;
 ​
 // Query the header element
 return q[front];
Copy the code

Queue is actually the concept of “first come, last come” in life. Queuing to buy things, registration system and so on all reflect the structure of queue. Computers are commonly used in operating systems, especially in multi-user environments. For example, multiple users apply for printer resources at the same time, but since printers can only print one document at a time, we need a queue to store print jobs submitted by users.

Three summary

LeetCode (leetcode-cn.com)

LeetCode (leetcode-cn.com)

Stacks and queues we just have to remember that they store data last in first out and first in first out. In order to improve efficiency, arrays are used to simulate stacks and queues.

Binary tree traversal and expression evaluation are generally implemented using stacks, and the most common algorithm problem for queues is sliding Windows, which will be updated in a few days.

All see here, click a like bai (crazy hint) 😆

Have any question can comment message ~ can pay attention to each other exchange

More interesting articles: Mancuoj’s homepage – Articles – Nuggets (juejin. Cn)