3. Stacks and queues

3.1 the stack

3.1.1 Basic concepts of stacks

Logical structure: Linear tables (restricted operation)

Storage structure: 1. Sequential stack 2. Chain stack

Data operations: First in last out (LIFO)

3.1.2 Sequential storage structure of stacks

1. Sequential storage structure code description:

#define Maxsize 50
typedef struct{
    Elemtype data[Maxsize];
    int top;
}SqStack;
Copy the code

Pointer to top of stack: s. pop, initially set to S. pop =-1; Top element: s.data [s.tep];

1. Check that the stack is full (s.table ==MaxSize-1) 2. Top++ 3. s.data [s.table]=x

Check whether the stack is empty (s.table ==-1). X =S.data[s.table] 3

Stack: long S.t op + 1

2. Share the stack

Top pointer (initial) : top0=-1,top1=Maxsize

1. Judge that the stack is full (top1-TOP0 =1); top0++ ; The assignment

(top1-top0=1)**; **top1--** ; The assignmentCopy the code

1. Determine that the stack is empty (TOP0 ==-1); The assignment; top0–

2. Check whether the stack is empty (top1==Maxsize); The assignment; top1++

3.1.3 chain stack

The stack using chain storage is called chain stack. The advantage of chain stack is that it is convenient for multiple stacks to share storage space and improve their efficiency, and there is no stack overflow situation.

Multiple stacks are generally linked to the stack.

3.1.4 examination site

Cattelan number: if X_i is already out of the stack, the previous elements that have not been out of the stack must be reversed.


3.2 the queue

3.2.1 Basic Concepts of queues

Queues are also linear tables with limited operations, first-in, first-out (FIFO).

3.2.2 Sequential storage structure of queues

1. Sequential queue

Header pointer (front) : Points to the header element

Rear pointer: Points to the next position of the rear element

Initial state (queue empty condition) : q.front = q.ear =0

Queue operation: judge full queue, assign value, rear++

Queue operation: judge queue empty, assign value, front++

When front and rear are both at the end, re-entry will cause an overflow, which is a false overflow, which leads to the circular queue to solve the problem.

2. Circular queue (emphasis)

Initial state (non-queue empty condition) : q.front = q.ear =0

Q.ear =(q.ear +1)%Maxsize

Queue operation: judge queue empty, assign value, q.front =(q.front +1)%Maxsize

Queue length :(q.ear +Maxsize- q.fold)%Maxsize

To judge an empty or full line:

1. Sacrifice a unit

Queue full condition :(q.ear +1)%Maxsize== q.front

Queue empty condition: q.front == q.ear

2. Add data members that represent the number of elements

Full condition: q.front == q.ear && q.size ==Maxsize

Queue empty condition: q.front == q.ear && q.size ==0

3. Add a tag to the type

Full conditions: q.front == q.ear &&Q.tag==1

The enqueue operation also sets the tag to 1

Queue empty condition :Q.front== q.ear &&Q.tag==0

The dequeue operation also sets the tag to 0

3.2.3 Chain storage structure of queues

1. Chain queue without leading node

Team head pointer: Team head node

Tail pointer: tail node (as opposed to sequential storage)

Initial status: q.front = q.ear =NULL

Create new node s, rear->next=s, rear=rear->next(front=rear)

Front = back ->next(front=rear=NULL)

Q.front**== q.ear ==NULL**

2. Chain queue of leading nodes

Queue header pointer: the header

Tail pointer: tail node of the team

Initial status: q.front = q.ear =head

Create a new node s, rear->next=s, rear=rear->next

Front = back ->next(front=rear(not NULL))

Q.front**==** q.ear (front=head, rear not)

3.2.4 Dual-ended Queue

Output constrained dual-ended queues: allow insert and delete at one end and insert only at the other

Input restricted dual-ended queues: allow insert and delete at one end and delete only at the other

unattainable The same different
Input constraints 4231 4213
The output is limited 4231 4132

The possible sequence of a double-ended queue is judged by drawing a vertical line in the middle and increasing in each direction.

Column: b | acde, db | ace, the ECB | AD

3.3 Stack application

3.3.1. Matching parentheses

(1) An open parenthesis is encountered

(2) when a close parenthesis is encountered, a stack is compared with it, otherwise it fails

(3) If the stack is empty after scanning, it matches

3.3.2 rainfall distribution on 10-12Expression evaluation

conversion Postfix expression Prefix expression
Infix expression 1. Parentheses are placed around all units based on priority

2. Operator moves to parenthesesbehind

3. To the brackets		 1. Parentheses are placed around all units based on priority

2. Operator moves to parenthesesIn front of the

3. To the brackets

Note that the order of the variables remains the same regardless of the expression.

Postfix representation = post-order traversal of the expression tree

(1) Suffix expression calculated value

Scan in sequence (left to right) :

Letter -> push

Symbol -> Exits two from the stack and evaluates, pushing the result onto the stack

The top of the stack is the final result

(2) Prefix expression evaluates value

Scan in sequence (from right to left) :

Letter -> push

Symbol -> Remove two from the stack and evaluate, pushing the result onto the stack (pay attention to the order of calculation, the basic principle is the same alphabetical order)

The top of the stack is the final result

Practice: prefix expression to infix expression: +-*^ABCD/E/F+GH

3.3.3Stack application in recursion

Recursion: The application of itself to the definition of a function, procedure, or data structure.

Recursion condition: Recursive expression (recursive body)

Boundary conditions (recursive exit)

The essence of recursion is the ability to transform the original problem into a smaller problem with the same attributes.

Any recursive algorithm can use a stack transform, but it doesn’t have to.