A stack is a linear list that only allows insertion or deletion operations at one end (last in first out)

Top of stack: The end of the linear table that allows insertion and deletion

Bottom of the stack: the end where insertion and deletion are not allowed

Empty stack: an empty list without any elements

n different elements are pushed onto the stack, and the number of different arrangements of elements popped out of the stack is:

Initstack (&S): Initialize an empty stack s

StackEmpty (S): Determines whether a stack is empty. If stack s is empty, it returns true, otherwise it returns false.

Push (&S, x): Push into the stack. If stack s is not full, add x to make it the top of the new stack.

Pop (&S, &x): Pop the stack. If the stack s is not empty, pop the top element of the stack and return with x.

GetTop (s,&x): Read the top element of the stack. If the stack s is not empty, use x to return the top element of the stack.

Destroystack (&S): Destroy the stack and release the storage space occupied by stack s ("&" indicates a reference call)

A set of storage units with consecutive addresses is used to store data elements from the bottom of the stack to the top of the stack, and a pointer (top) is attached to indicate the location of the current top element of the stack.

initialization

The stack is empty

push into stack

pop

Read the top element of the stack

Taking advantage of the relatively unchanged position of the stack bottom, let two sequential stacks share a one-dimensional array space. Set the bottoms of the two stacks at both ends of the shared space, and the tops of the two stacks extend toward the middle of the space.

Call it short

The sentence is full

A queue is a linear list (first in, first out) that only allows insertions at one end of the table and deletions at the other end of the table.

Enqueue: Insert elements to the end of the queue

Dequeue: delete elements at the head of the queue

InitQueue (&Q): Initialize the queue and construct an empty queue Q

QueueEmpty (Q): If the queue is empty, it returns true if the queue Q is empty, otherwise it returns false.

EnQueue (&Q,x): Enter the queue. If the queue Q is not full, add x to make it the new end of the queue.

DeQueue (&Q,&x): Dequeue, if queue Q is not empty, delete the head element of the queue and return with x

GetHead (Q,&x): Read the head element of the queue. If the queue Q is not empty, assign the head element to x

There is an "overflow" phenomenon

A linked queue is a singly linked list with both a head pointer and a tail pointer.

initialization

Team is empty

Join the team

Dequeue

The elements entered from the front end are arranged in front of the elements entered from the rear end in the queue.

Regardless of whether it is dequeued by the front end or the back end, the elements that come out first are arranged in front of the elements that come out later.

An empty stack is initially set, and parentheses are read sequentially.

If it is a right parenthesis, it either eliminates the most urgent expectation placed on the top of the stack, or it is an illegal situation (the sequence of brackets does not match, and the program exits).

If it is a left parenthesis, it will be pushed onto the stack as a new more urgent expectation, which will naturally reduce the urgency of all the original unresolved expectations in the stack by one level. At the end of the algorithm, the stack is empty, otherwise the bracket sequence does not match.

infix expression → postfix expression

postfix expression

Recursion: applying itself to the definition of a function, procedure, or data structure

process

Resolve speed mismatch between host and external device

Solve resource competition problems caused by multiple users

one-dimensional array

Multidimensional Arrays

Compressed storage: means that only one storage space is allocated for multiple elements with the same value, and no storage space is allocated for zero elements.

Special matrix: refers to a matrix that has many identical matrix elements or zero elements and has a certain regularity in its distribution.

Symmetric matrix

triangular matrix

Tridiagonal matrix (banded matrix)

sparse matrix