Stack and queue -- Restrictive linear table structure
These two data structures are linear data structures widely used in programming.
Compared with linear tables, the insertion and deletion operations of stacks and queues are more limited. The comparison is as follows:
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-pymQCA2N-1632487846533)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210910230250101.png)]
- Linear table can be inserted or deleted at any position;
- The stack can only be inserted and deleted at the top of the stack;
- The queue can only be inserted at the end of the queue and deleted at the head of the queue.
One stack (LIFO)
1. Definitions
Stack is a special linear table. It is limited that insert and delete operations can only be carried out at the end of the table. It has the characteristics of LIFO - Last In First Out.
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-VjYKMf7f-1632487846535)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210910230835197.png)]
Sequential stack - the sequential storage mode of the stack
The data elements in the sequential stack are stored in a continuous set of storage space. The bottom of the stack can be set at an endpoint of the storage space, and the top of the stack is
If it changes due to insertion and deletion, a top pointer is used to indicate the current top position of the stack.
2. Sequential storage structure of stack - sequential stack (array representation)
Sequential stack: a stack monopolizes a set of storage units with consecutive addresses.
(1) Type definition
CONST arrmax = 100 //Maximum storage capacity of stack
typedef struct{
ElemType* top;//Stack top pointer
ElemType* base;//Stack bottom pointer
int stacksize;//The maximum length of the stack (the length allocated to the stack)
}SqStack;
(the type definition of sequence stack can be memorized in combination with the type definition of sequence table)
In the sequence table, there are base address, current length and maximum length.
(2) Stack empty condition and stack full condition
SqStack S; //Stack empty condition S.base == S.top; //Stack full condition S.top == S.base + arrmax;
(3) Basic operation
1) Initialization of stack (basic operation)
bool InitStack(SqStack &S){//Reference pass parameter
//Allocate contiguous storage units
S.base = new ElemType[arrmax];
if(!S.base)
exit(1);
//Identify other
S.top = S.base;
S.stacksize = arrmax;
return true;
}
2) Empty stack (reference operation)
bool StackEmpty(SqStack &S){
if(S.top == S.base)
return true;
else
return false;
}
3) Element stacking operation (processing operation)
bool Push(SqStack &S, ElemType e){
//Check whether the stack operation is legal (judge whether the stack is full)
if(S.top - S.base == S.stacksize)
return false;
//Stack method, proceed to the next step
*(S.top) = e;
S.top++;
return true;
}
4) Element out of stack operation (processing operation)
bool Pop(SqStack &S, ElemType &e){
//Check whether the stack out operation is legal (empty)
if(S.top == S.base)
return false;
//Perform stack out operation
S.top--;
e = *(S.top);
return true;
}
5) Read stack top operation (reference operation)
bool GetTop(SqStack &S, ElemType &e){
//View legitimacy
if(S.top == S.base)
return false;
//read
e = *(S.top - 1);
return true;
}
(4) [Special] two stacks share a continuous set of storage units
Type definition + graphical visual representation
CONST arrmax = 500;
typedef struct{
ElemType* top;
ElemType* top1;
ElemType* base;
int stacksize;
}SqStack;
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-C2dkfD30-1632487846536)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911150549918.png)]
(5) Examples
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-5jqDRf2T-1632487846538)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911150714300.png)]
3. Chain storage structure of stack (chain stack representation)
(1) Type definition
The following is the type representation of each node in the linked list:
typedef struct node{
ElemType data;
struct node* next;
}LinkStack;
(2) Related introduction
The definition of chain stack is simpler. The node structure is the same as that in the single chain list, and there is no need to define it repeatedly. Because the stack only performs insert and delete operations at the top of the stack, the head node is not required in the chain stack, but it should be noted that the direction of the pointer in the chain stack is from the top of the stack to the bottom of the stack, which is just opposite to the single chain list.
simplify:
- No header node is required (only at the top of the stack)
- Pointer direction: from the top of the stack to the end of the stack (relevant operations are only carried out at the top of the stack. If the pointer direction is reversed, each operation must traverse the whole chain stack)
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-c0IATisl-1632487846539)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911152741877.png)]
(3) Basic operation
1) Chain stack initialization
Because there is no header node, initialization is not required.
2) Stack operation
Note that this is a reference operation, because the chain stack has no head node, the head pointer points to the top of the stack, and the top of the stack pointer needs to be changed, so the passed parameter needs to be the pointer of the pointer.
bool Push(LinkStack **top, ElemType e){
LinkStack* tmp = new LinkStack;
if(!*top)
exit(1);
tmp->data = e;
tmp->next = *top;
*top = tmp;
return true;
}
3) Out of stack operation
It is also a reference operation. The precautions are the same as the stack operation.
bool Pop(LinkStack **top, ElemType* e){
*e = (*top)->data;
LinkStack* tmp = (*top)->next;
delete *top;
*top = tmp;
return true;
}
Note: as for the delete operation, it is actually an internal operation of new. It only frees the memory space from new and assigns NULL to the pointer itself. It is not clear about the memory space occupied by the pointer itself.
4. Application examples of stack
(1) Number system conversion
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-OBBZOio6-1632487846540)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911162208712.png)]
1) Decimal - > octal
Question: suppose we want to compile a program that meets the following requirements: for any non negative decimal integer input, print out its equivalent octal number.
Analysis: the problem is very clear. It is to output all octal digits obtained in the calculation process. The order of each digit of octal is from low to high, and the order of printout is generally from high to low, which is just the opposite of the calculation process. Therefore, you need to save the bits of octal numbers obtained in the calculation process, and then output them in reverse order. Because it is carried out according to the law of "last in, first out", it is most appropriate to use stack. (in fact, the actual calculation process is not simplified, but the storage process and presentation process are simplified).
The code is as follows:
void conversion(){
SqStack* S;
InitStack(S);
int N;
cin >> N;
while(N){
Push(S, N%8);
N = N / 8;
}
while(!StackEmpty(S)){
int* e;
Pop(S, e);
cout << e;
}
cout << endl;
}
2) Octal - > decimal
void conversion(){
SqStack* S;
InitStack(S);
int X;
cin >> X;
while(X){
Push(S, X%8);
X = X / 8;
}
int N = 0;
while(!StackEmpty(S)){
int* e;
Pop(S, e);
N = N * 8 + e;
}
cout << N << endl;
}
(2) Bracket matching test
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-xfbcvp10-1632487846541)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911164830203.png)]
Key points: the left bracket is stacked, and the right bracket matches.
be careful:
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-AAUIaaIV-1632487846542)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911165051944.png)]
The code is as follows:
//We assume that there are only parentheses in the form of "()"
bool bracketMatch(string str){
//Initializes an open bracket stack
SqStack *S;
InitStack(S);
//Traverse the string and do the corresponding stack in and out operations
for(int i = 0; i < str.size(); i++){
if(str[i] == '('){
Push(S, str[i]);
}
else if(str[i] == ')'){
if(!StackEmpty(S))
return false;
char* ch;
Pop(S, ch);
if(*ch == '(')
Pop(S);
}
}
if(StackEmpty(S))
return true;
else
return false;
}
(3) Maze solving problem
When solving the maze by computer, the method of "exhaustive solution" is usually used, that is, start from the entrance, explore forward in a certain direction, and continue to move forward if you can get through; Otherwise, go back along the original road and continue to explore in another direction until all possible paths have been explored. If all possible paths have been explored and still can not reach the end, it means that there is no channel from the beginning to the end of the maze.
If the stack data structure is adopted to solve the problem:
- After entering the maze from the entrance, no matter which position in the maze, go East first. If you can go, continue to go east. If you can't go east at a certain position, test the directions of South, West and North in turn, and continue from a feasible direction to the exit;
- If you can't go in all four directions at a certain position, go back to the previous position (out of the stack) and try again in another direction (into the stack). If there is no direction to try at this position, go back one step. If all the four directions of the positions you have passed have been tested, * * go back to the starting point (the stack is empty) * * and don't go through, That means the maze doesn't work at all;
- The so-called "impassability" not only refers to the "wall blocking the road", but also "the road that has been passed can not be repeated for the second time", which includes "the road that has been passed but has not been passed".
- Obviously, in order to ensure that you can return along the original path at any location, you need to use a * * "last in first out" structure * *, that is, stack, to save the path from the entrance to the current location. And after walking out of the exit, what is saved in the stack is a path from the entrance to the exit.
bool MazePath(){
}
(code omitted here)
(4) Integer simple expression evaluation (emphasis)
Expressions: operands, operators, and delimiters.
- Operand: it can be a constant or an identifier described as a variable or constant;
- Operators: they can be divided into arithmetic operators, relational operators and logical operators;
- Basic delimiters: there are left and right parentheses, expression terminators, etc.
We are limited to discussing arithmetic expressions containing only binary operators. This expression can be defined as:
- Expression:: = operand operator operand
- Operand:: = simple variable | expression
- Simple variable:: = identifier | unsigned integer
Rules of arithmetic operation:
- Multiplication and division before addition and subtraction
- First left then right
- First inside the bracket and then outside the bracket
Operator priority table:
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-uEM9FDI4-1632487846542)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911202638689.png)]
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-c88nLVmi-1632487846543)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210911202840307.png)]
The code is as follows:
ElemType compute(string str){
//Initialize two compute stacks
SqStack* OPTR;
SqStack* OPND;
StackInit(OPTR);
StackInit(OPND);
Push(OPTR, '#');
//Traversal input expression
for(int i = 0; i < str.size(); i++){
if(JudgeType(str[i]) == Operand){
Push(OPND, str[i]);
}
else if(JudgeType(str[i]) == operator){
if(JudgePri(GetTop(OPTR), str[i]) == '>'){
Pop(OPTR, op);
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, operate(a, op, b));
}
else if(JudgePri(GetTop(OPTR), str[i]) == '='){
Pop(OPTR,x);
}
else if(JudgePri(GetTop(OPTR), str[i]) == '<'){
Push(OPTR, str[i]);
}
}
}
return(GetTop(OPND))
}
[key] expression evaluation
In the computer, there are three different identification methods for this binary expression.
Assuming Exp = S1 + OP + S2, then:
- OP + S1 + S2 is the prefix representation of expression (prefix expression for short)
- Call S1 + OP + S2 infix representation of expression (infix for short)
- Call S1 + S2 + OP the suffix representation of the expression (hereinafter referred to as the suffix expression)
The definition of expression can be explained as follows: binary expression is composed of three parts: the (first) operand (S1), the operator (OP) and the (second) operand (S2); The operands can be simple variables or expressions; Simple variables can be identifiers or unsigned integers.
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-mXN07nNf-1632487846544)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210912135917425.png)]
Comparison and points for attention of three expressions:
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-JA9HoXht-1632487846544)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210912140441633.png)]
Therefore, in addition to determining the operator priority table as before, we can also use this method to evaluate the expression:
- Convert infix expression into suffix expression (the order in which operators appear in suffix expression is the operation order)
- Calculate the expression according to the suffix expression: find the operator first, and then the operand (suffix calculation formula)
!!! Infix to suffix process:
- Set up operator stack;
- Set the end character of the expression as "#" and the bottom of the preset operator stack as "#";
- If the current character is an operand, it is sent directly to the suffix; (the relative order of operands does not change)
- If the current character is an operator and the priority number is greater than the stack top operator, enter the stack, otherwise exit the stack top operator and send it to the suffix;
- If the current character is a terminator, send all operators in the stack to the suffix from the top of the stack to the bottom of the stack;
- "(" is used to isolate the operators before and after it. If the current operator is "(" ", it will be stacked;
- ")" can be regarded as the terminator of the expression starting from the corresponding left parenthesis, then exit the stack top operator in turn from the top of the stack and send it to the suffix until the character at the top of the stack is "(".
!!! suffix expression evaluation procedure (operator first, operand later):
The suffix is "scanned" from left to right. When the operand is encountered, it is temporarily saved, and the operation can be carried out when the operator is encountered. At this time, the two operands participating in the operation should be the two operands just encountered before it, and the first operand appears first, and then the second operand. Therefore, the structure of saving operands during the operation should be a stack.
The code for expression evaluation is as follows:
//1. Infix expression exp - > suffix expression suffix
void transform(string exp, string suffix){
//Initialize operator stack S
SqStack* S;
InitStack(S);
Push(S, '#');//Push the end symbol # into the bottom of the stack
//Traverse the input expression and convert it according to different situations
for(int i = 0; i < exp.size(); i++){
if(JudgeType(exp[i]) == Operand){
suffix.append(exp[i].toString());
}
else if(exp[i] == '('){
Push(S, '(');
}
else if(exp[i] == ')'){
char* op;
while(GetTop(S) != '('){
Pop(S, op);
suffix.append(op.toString());
}
Pop(S, op);//Put the left bracket out of the stack, but the bracket does not need to add a suffix
}
else if(exp[i] == '#'){
char* op;
while(GetTop(S) != '#'){
Pop(S, op);
suffix.append(op.toString());
}
}
else if(JudgePri(GetTop(S), exp[i]) == '>'){
Push(S, exp[i]);
}
else if(JudgePri(GetTop(S), exp[i]) == '<'){
while((GetTop(S), exp[i]) == '<'){
char* op;
Pop(S, op);
suffix.append(op.toString());
}
Push(S, exp[i]);
}
}
}
//2. Evaluation of suffix expression
int suffixCompute(string suffix){
//Create operand stack
SqStack* S;
InitStack(S);
//Traversal suffix expression
for(int i = 0; i < suffix.size(); i++){
if(JudgeType(suffix[i]) == Operand){
Push(S, suffix[i]);
}
else if(JudgeType(suffix[i]) == operator){
int* a;
int* b;
Pop(S, b);
Pop(S, a);
int result = operate(a, suffix[i], b);
Push(S, &result);
}
}
int result = GetTop(S);
return result;
}
5. Stack and recursive process (the implementation principle of recursive algorithm is to use stack)
(1) Recursion
The meaning of recursion: the interior of a function, procedure or data structure is defined directly or indirectly by itself.
Suitable for the application of recursion (application conditions of recursion):
- Large scale problems can be resolved into smaller ones, and they are handled (or defined) in the same way
- When the scale of the problem is reduced to a certain extent, it can be solved directly (termination condition)
Problems needing attention when writing recursive algorithm:
- The recursive algorithm itself can not be run as an independent program. It needs to set the call initial value in other programs to call;
- Recursive algorithm should have an exit (termination condition)
Features of recursive algorithm:
- [advantages] recursive algorithm is simple, intuitive and easy to understand
- [disadvantages] the time efficiency is low, the space overhead is large, and the algorithm is not easy to optimize
!!! Implementation principle of recursive algorithm:
- Using the stack, each element in the stack is called work record, which is divided into three parts: return address, real parameter table (variable parameter and value parameter), and local variable
- When a call occurs, protect the site, that is, put the current work record into the stack, and then turn to the called process
- At the end of a call, the scene will be restored, that is, if the stack is not empty, it will exit the stack and continue to execute from the exit return address
Purpose of recursive algorithm:
- Solving recursively defined mathematical functions (factorials)
- Operations / operations on data structures defined recursively
- The solution process can be described recursively
Recursion related code:
int func(int n){
if(Recursive exit){
Recursive return;
}
else{
Recursive forward;
}
}
(2) [example] n-order Hanoi Tower problem
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-mUBt81eh-1632487846545)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210913145658508.png)]
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-HLPLHfbb-1632487846546)(C:\Polaris_LEARN\WORK-LEARNING \ profile \ data structure \ summary \ stack and queue. assets\image-20210913150533350.png)]
void hanoi(int n, char x, char y, char z){
//Move the n discs numbered 1 to n on tower base x from small to large and from top to bottom to tower base z according to rules, and y can be used as an auxiliary tower base.
if(n == 1){//Export (termination conditions)
move(x, 1, z);//Move the disc numbered 1 from x to z
}
else{//recursion
hanoi(n-1, x, z, y);//Move the disks numbered 1 to n-1 on x to y,z as the auxiliary tower
move(x, n, z);//Move the disc numbered n from x to z
hanoi(n-1, y, x, z);//Move the disks numbered 1 to n-1 on y to z,x as the auxiliary tower
}
}
(3) Convert recursive algorithm to non recursive algorithm
1) Iterative algorithm
- Recursion: call from top to bottom and return results from bottom to top
- Iterations: bottom to top
Find the factorial of n
-
recursion
int fact(int n){ if(n < 0){ return 0; } else if(n == 0 || n == 1){ return 1; } else{ return n * fact(n - 1) } } -
iteration
int fact(int n){ int result = 1; for(int i = 1; i <= n; i++){ result = result * i; } return result; }
2) Eliminate tail recursion -- pass the result through parameters, so as to achieve the purpose of not pressing the stack, and the efficiency is very high
On the definition and principle of tail recursion
In the traditional recursion, the typical model is to execute the recursive call first, and then obtain the return value of the recursive call and calculate the result. In this way, you will not get the result of the calculation until each recursive call returns. Traditionally, the recursive process is a function call, involving return address, function parameters, register value and other stack (function parameters are usually stored in registers on x86-64). This has two disadvantages:
- Low efficiency, occupying memory
- If the recursive chain is too long, it may stack overflow
If a function calls itself at the tail position (or other functions of a tail call itself, etc.), this situation is called tail recursion. Tail recursion is also a special case of recursion. Tail recursion is a special tail call, that is, it directly calls its own recursive function at the tail (get the result first, and then call itself). The optimization of tail recursion is also the main reason to pay attention to tail calls. Tail calls are not necessarily recursive, but tail recursion is particularly useful and easy to implement.
Principle of tail recursion
When the compiler detects that a function call is tail recursion, it overwrites the current activity record instead of creating a new one on the stack. The compiler can do this because the recursive call is the last statement to be executed in the current active period. Therefore, when the call returns, there is nothing else to do in the stack frame, so there is no need to save the stack frame. By overwriting the current stack frame instead of adding another one on it, the stack space used is greatly reduced, which makes the actual operation efficiency higher.
Tail recursion features:
Tail recursion has two additional features on the basis of ordinary tail calls:
- What is called at the end is the function itself (self called);
- Through optimization, the calculation only occupies constant stack space.
Calculate the factorial of n
-
Using recursion
int fact(int n) { if (n < 0) return 0; else if(n == 0 || n == 1) return 1; else return n * fact(n - 1); }Calculate n times (n-1) in each function call! Let n=n-1 and continue this process until n=1. This definition is not tail recursive, because the return value of each function call depends on multiplying n by the return value of the following function call. Therefore, the stack frame generated by each call will have to be saved on the stack until the return value of the next sub call is determined.
The return value of each call is different.
-
Tail recursion
int facttail(int n, int res) { if (n < 0) return 0; else if(n == 0) return 1; else if(n == 1) return res; else return facttail(n - 1, n *res); }Function has more parameters res than code 1, but there is not much difference. Res (initialized to 1) maintains the depth of the recursive hierarchy. This allows us to avoid having to multiply the return value by n each time. However, in each recursive call, let res=n*res and n=n-1. Continue to call recursively until n=1, which meets the end condition. At this time, you can directly return res.
Each call returns the same value.
[example] output the node data in the single linked list in sequence
The recursion used at this time is itself a tail recursion
void listPrint(LinkList L){
if(L != NULL){
cout << L->data;
listPrint(L->next);
}
else{
return;
}
}
3) Using stack to simulate recursion (general method) -- let's see later. I really can't see it anymore
Second queue (first in first out)
facttail(int n, int res)
{
if (n < 0)
return 0;
else if(n == 0)
return 1;
else if(n == 1)
return res;
else
return facttail(n - 1, n *res);
}
Function has more parameters than code 1 res，Apart from that, it doesn't make much difference.**res(Initialize to 1) maintain the depth of the recursive hierarchy**. This allows us to avoid the need to**Return value multiplied by n**. However, in each recursive call, the res=n*res also n=n－1. Continue calling recursively until n=1，This satisfies the end condition and returns directly res Just.
**Each call returns the same value.**
##### **[example] output the node data in the single linked list in sequence**
The recursion used at this time is itself a tail recursion
```c++
void listPrint(LinkList L){
if(L != NULL){
cout << L->data;
listPrint(L->next);
}
else{
return;
}
}