Data structure and algorithm (1) linear table implementation
Data structure and algorithm (2) unidirectional circular linked list creation insert delete implementation
Data structure and algorithm (3) Implementation of bidirectional linked list and bidirectional cyclic linked list
Data structures and algorithms (4) Linked list related interview questions
Data structures and algorithms (5) Stack and queue operation and implementation
Data structures and algorithms (6) The operation and implementation of queues
@[TOC]
Data structure and algorithm (5) stack operation and implementation
- Demo download of this blog:
- The basic operation of sequential stack is realized
- Chain stack basic operation implementation
1. Introduction to the stack
A stack is a lifO structure, with a pointer to the bottom of the stack and a pointer to the top of the stack, and a pointer to the top of the stack. Its structure is shown as follows:
A queue is a first-in, first-out data structure that can only be entered from the end of the queue and left from the end. The structure of the queue is shown as follows:
2. The realization of sequential stack
2.1 Basic operation of sequential stack
2.1.1 Sequential stack structure
// The sequential stack structure
typedef struct KSqueueStack{
KStackElementType data[MAXSIZE];
int top; // For the top pointer
}SqStack;
Copy the code2.1.2 Sequential Stack construction
//1. Build an empty stack S
KStatus initStack(SqStack *S) {
S->top = -1;
return OK;
}
Copy the code2.1.3 The sequential stack is empty
//2. Empty the stack
KStatus clearStack(SqStack *S) {
S->top = -1;
return OK; } ` ` ` # # # #2.1.4Sequential stack nulls SWIFT//3. Check whether the sequence stack is empty
KStatus isEmpty(SqStack S) {
return S.top == -1 ;
}
Copy the code2.1.5 Obtaining the length of sequential stack
//4. Get stack length
int getLength(SqStack S) {
return S.top + 1;
}
Copy the code2.1.6 Sequential Stack To obtain the top element of the stack
//5. Get the top of the stack
KStatus getTop(SqStack S.KStackElementType *e) {
// return an error if the stack is empty
if (S.top == -1) return ERROR;
*e = S.data[S.top];
return OK;
}
Copy the code2.1.7 Sequential Stack pushing
Before pushing, see the figure below:
After being pushed, the picture is as follows:
/ / 6. Pressure stack
KStatus push(SqStack *S.KStackElementType e) {
// Check whether the stack is full
if (S->top == MAXSIZE -1) return ERROR;
//1. Stack pointer +1;
//2. Assign the newly inserted element to the top space of the stack
//S->top ++;
//S->data[S->top] = e;
S->data[++(S->top)] = e;
return OK;
}
Copy the code2.1.8 Removing a stack in sequence
/ / 7. Out of the stack
KStatus pop(SqStack *S.KStackElementType *e) {
// Check whether the stack is empty
if(S->top == -1) return ERROR;
//1. Assign e to the top element to be removed
//2. Stack pointer --;
//*e = S->data[S->top];
//S->top--;
*e = S->data[S->top--];
return OK;
}
Copy the code2.1.9 Sequential stack traversal
/ / 8. Stack traversal
KStatus traverse(SqStack S) {
int i = 0;
printf("Stack all elements:");
while (i < S.top) {
printf("%d ".S.data[i++]);
}
printf("\n");
return OK;
}
Copy the code2.1.10 Sequential stack unit test
/ / 9. Testing
void test() {
SqStack S;
int e;
if (initStack(&S) = =OK) {
for (int j = 1 ; j < 10; j++) {
push(&S, j);
}
}
printf("The element in the sequential stack is :\n");
traverse(S);
pop(&S, &e);
printf("Pop-out top element: %d\n",e);
traverse(S);
printf("Empty stack :%d\n",isEmpty(S));
getTop(S, &e);
printf("Top element :%d\n Stack length :%d\n",e,getLength(S));
clearStack(&S);
printf("Have you cleared stack %d with stack length :%d\n?",isEmpty(S),getLength(S));
}
Copy the code- The output
Hello, World! All elements in the stack: 1, 2, 3, 4, 5, 6, 7, 8 9 All elements in the stack: 1, 2, 3, 4, 5, 6, 7 Whether the stack is empty :0 Top element in the stack :8 Length of the stack :8 Whether the stack has been cleared 1, the stack length is 0 Program ended with exit code: 0Copy the code3. Realization of chain stack
Chain stack is a stack structure realized by linked list. Its structure diagram is shown as follows:
3.1 Basic operation of chain stack
3.1.1 Chain stack structure
// stack node
typedef struct KStackNode {
KStackElementType data; // Node data
struct KStackNode *next; // pointer to next node}StackNode, *LinkStackPtr; // Stack structuretypedef struct KLinkStack {
LinkStackPtr top; // top of stack
int count; / / stack size
}LinkStack;
Copy the code3.1.2 Chain stack construction
//1. Construct an empty stack S
KStatus initStack(LinkStack *S) {
S->top = NULL;
S->count = 0;
return OK;
}
Copy the code3.1.3 Chain stack empty
//2. Empty the stack
KStatus clearStack(LinkStack *S) {
LinkStackPtr p,q;
//p points to the top of the stack
p = S->top;
while (p) {
// save the node p to be deleted
q = p;
// Then p points to its next node
p = p->next;
// delete node p
free(q);
}
return OK;
}
Copy the code3.1.4 Chain stack emptying
//3. Check whether the stack is empty
KStatus isEmpty(LinkStack S) {
return S.count= =0;
}
Copy the code3.1.5 Chain stack length acquisition
//4. Get stack length
int getLength(LinkStack S) {
return S.count;
}
Copy the code3.1.6 Chain Stack Get the top element of the stack
//5. Get the top element of the stack
KStatus getTop(LinkStack S.KStackElementType *e) {
// Check whether the stack is empty
if (S.top == NULL) return ERROR;
*e = S.top->data;
return OK;
}
Copy the code3.1.7 Chain stack pressing
Chain stack structure, the schematic diagram of the stack is as follows:
/ / 6. Pressure stack
KStatus push(LinkStack *S.KStackElementType e) {
// create a new node.
LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(StackNode));
//2. Assign the value to the new node
newNode->data = e;
// add a new node to the top of the stack
//3.1 Points the current top element to its immediate successor
newNode->next = S->top;
// assign the new node to the top pointer
S->top = newNode;
// Stack size +1
S->count+ +;return OK;
}
Copy the code3.1.8 Chain out of the stack
Chain stack structure, the schematic diagram of the stack is as follows:
/ / 7. Out of the stack
KStatus pop(LinkStack *S.KStackElementType *e) {
LinkStackPtr p;
if (isEmpty(*S)) return ERROR;
//1. Assign the top element to *e
*e = S->top->data;
//2. Assign the top node to p
p = S->top;
//3. Move the top pointer down one bit to the next node
S->top = S->top->next;
//4. Release p
free(p);
// Stack size is reduced by 1
S->count-;return OK;
}
Copy the code3.1.9 Chain stack traversal
/ / 8. Traversal stack
KStatus traverse(LinkStack S) {
LinkStackPtr p = S.top;
printf("Traverse stack elements:");
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
Copy the code3.1.10 Unit test of chain stack
// unit tests
void test() {
int j;
LinkStack s;
int e;
if(initStack(&s)==OK)
for(j=1; j<=10; j++) push(&s,j); printf("The elements in the stack are:");
traverse(s);
pop(&s,&e);
printf("Popup top element e=%d\n",e);
traverse(s);
printf("Stack empty no: %d(1: empty 0: no)\n",isEmpty(s));
getTop(s,&e);
printf("Top element e=%d stack length %d\n",e,getLength(s));
clearStack(&s);
printf("Empty stack no: %d(1: empty 0: no)\n",isEmpty(s));
}
Copy the code- The output
Hello, World! The elements in the stack are as follows: traversal stack elements: 10 9 8 7 6 5 4 3 2 1 Popup top element e=10 Traversal stack elements: 9 8 7 6 5 4 3 2 1 Stack empty No: 0(1: empty 0: no) Top element e=9 Stack length is 9. After clearing the stack, the stack is empty No: 0(1: empty 0: no) Program ended with exit code: 0Copy the code3. Stack application
3.1 the recursive
3.1.1 Function call and recursive implementation
There are three situations in which recursion is used to solve a problem
- The definition is recursive
- The data structure is recursive
- The solution to the problem is recursive
3.1.2 Depth-first search
3.1.3 Backtracking algorithm
3.1.4 Hanoi Tower issue
Problem description: if there are 3 towers named A,B and C respectively, there are n directly large and small different on tower A, from small to large numbered 1,2,3… Disk of n. Now it is required to move n disks from Tower A to Tower C. And still stack in the same order. The disks must be moved according to the following rules :1. Only one disk can be moved at a time. 2. The disk can be inserted in any tower of A,B and C; 3. At no time should a larger disk be pressed on top of a smaller disk.
The solution process is shown as follows:
3.2 Expression evaluation
In the compilation system, arithmetic expressions can be divided into three categories: arithmetic expressions, relational expressions, and logical expressions.
Any arithmetic expression consists of operands, operators, and delimiters. We call operands, operators, and delimiters (delimiters mark the end of an arithmetic expression) words of an arithmetic expression.
- Infix expression: Operators in arithmetic expressions always appear between operands (except for unary operators). For example:
A plus B minus C over D times E - Postfix expressionOperators in expressions appear after operands. The compiler handles infix expressions by changing them to postfix expressions, for example:
ABCD/-E*+
Postfix expression features:
- The operands of postfix expressions are in exactly the same order as those of infix expressions (ABCDE above), except that the order of the operators has changed (+-/*);
- There are no parentheses in postfix expressions. The order in which postfix expressions are evaluated is the order in which they are executed
Application stack to implement the basic process of postfix expression evaluation:
Read items (operators or operands) of postfix expressions from left to right:
- Operand: push
- Operator: Pops an appropriate number of operands from the stack, evaluates and pushes the result onto the stack
- Finally, the element at the top of the stack is the resulting value of the expression
3.2.1 Evaluation of infix expression
Basic strategy: Convert an infix expression to a postfix expression, and then evaluate it.
- How do I convert an infix expression to a postfix expression? Such as:
2 + 9/3-5->2, 9, 3 over plus 5 minus
Process:
- The relative order of the operands remains the same
- The order of operation symbols changed
- Need to store “waiting” operation symbol
- Compare the current operation symbol with the last operation symbol in waiting
3.2.2 How can an infix Expression be converted into a suffix Expression
Each object of an infix expression is read from beginning to end and treated differently for different objects.
- Operand: Direct output
- Open bracket: push onto stack
- Close parenthesis: Pops the operator at the top of the stack and prints it until an open parenthesis is encountered (out of the stack, no output)
- Operator: (1) If the priority is greater than the top of the stack operator, push it to the stack. (2) If the priority is less than or equal to the top of the stack operator, pop the top of the stack operator and output; The new top of the stack operator is compared until it is greater than the priority of the top of the stack operator, and then the operator is pushed onto the stack
- When each object is processed, the remaining operators on the stack are printed
3.2.3 Implementation process of postfix expression
The compilation system sets up a stack of operators, starting with a “#” delimiter at the top. The compilation system scans infix expressions from left to right, reads each operand as part of the output of the postfix expression, and compares the priority of each operator read (delimiters are also considered operators) to the priority of the top-stack operator to determine whether to push the read operator. Again, the top of the stack operator is output as part of the most suffixed arithmetic expression.
- Operator priority Note: if O1 is regarded as the top of the stack operator, O2 is regarded as the operator read by the current scan.
- When shown as “+” or “-“, O2 as “*” or “/” < O1 priority priority of O2 (after meet, first, add and subtract)
- When O1 is “+”, “-“, “*” or “/” and O2 is “(“, the priority of O1 is less than the priority of O2 (following parentheses rule)
- When the O1 operator is of the same level as the O2 operator, the priority of O1 is greater than that of O2 (left-to-right rule for the same level)
- Because the suffix expression has no parentheses, when O1 is “(” and O2 is”) “, mark “=” to remove the pair of algorithms at this time.
- When O1 is “#” and O2 is “#”, mark “=” to make the algorithm end processing at this time
- If the value in the table is empty, this situation is not allowed. Once this situation occurs, the infix arithmetic expression syntax error, such as O1 is “) “, and O2 is “(“, that is, the infix expression syntax error! .
- Algorithm steps:
- Set up a stack, starting with the top element as #
- Read infix arithmetic expressions sequentially, print out when the word is an operand, and proceed to the next word
- When the single-read word is an operator, let A be the variable of the current top of the stack operator, and let B be the variable of the current read operator. Assign the currently read operator to B, and then compare the priority of variable A with that of variable B. If the priority of A is higher than that of B, unstack A and print it as a word of the postsuffix expression, and then compare the priority of the new top-stack element operator A with that of B.
If priority A < b, the value of B is pushed and the next word is read
If priority A > b, unstack a and print it as a word of the postsuffix expression, and then compare the priority of the new top-stack element operator, A, with that of B.
If priority A = B, a is (, and B is). Unstack a and read the next word
If priority A = B and priority A is #, priority B is #. The algorithm ends.
- Code implementation:
int PostExp(char str[]) // Use the stack to calculate the value of the postfix expression STR
{
KStackElementType x,x1,x2;
int i;
KNode *head; // Define the head pointer variable head
initStack(&head); // Initialize the chained stack head
for(i-0; str[i]! = #; i++)// loop until the input is #
{
if(isdigit(str[i])) // when STR [I] is the operand
{
x=(int)(str[i]-48); // The data converted to int is stored in variable x
push(head,x); / / x into the stack
}
else // when STR [I] is the operator
{
pop(head,&x2); // The unstack operand is stored in variable x2
pop(head,&x1); // The unstacked operand is stored in x1
switch(str[i]) // Perform the operation represented by STR [I]
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case'/' : {if(x2==0.0)
{
printf("Divisor zero error! \n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
push(head,x1); // The result of the operation is pushed
}
}
pop(head,&x); // get the calculated result in x
return x; // Return the calculated result
}
Copy the code4. The queue
Queue: A linear table with certain operation constraints has the following characteristics:
- Insert and delete operations: You can only insert at one end and delete at the other
- Data insertion: Enqueue (AddQ)
- Delete data: DeleteQ
- First in, first out: FIFO
4.1 Basic Queue Operations
4.2 Circular Queue
- The relationship between the head and tail Pointers and elements in a circular queue
