Stack
Basic concept of stack
Basic properties of stack
- A Stack is a linear table that allows only one segment to be inserted or deleted.
- Top of stack. The end of a linear table that allows insertion and deletion.
- The Bottom of the stack is fixed and cannot be inserted or deleted.
- Empty stack. Does not contain any elements.
Basic operation of stack
void InitStack(&S);//Initialize an empty stack s. bool StackEmpty(S);//Judge whether a stack is empty. If the stack s is empty, return true; otherwise, return false. bool Push(&S,x);//Enter the stack. If the stack s is not full, add x to make it the top of the new stack. bool Pop(&S,&x);//Out of the stack. If the stack s is not empty, the top element of the stack will pop up and return with x. bool GetTop(S,&x);//Read the stack top element. If the stack s is not empty, use x to return the stack top element. bool DestroyStack(&S);//Destroy the stack and release the storage space occupied by the stack s.
Storage structure of stack
Sequential stack
#define MaxSize 50 / / maximum number of elements in the stack
typedef struct{
int data[MaxSize];//Store elements in the stack
int top;//Stack top pointer
}SqStack;
Stack top pointer: S.top, initially set s.top=-1;
Stack top element: S.data[S.top];
Stack entry: when the stack is not satisfied, the stack top pointer first adds 1, and then sends the value to the stack top element;
Stack out operation: when the stack is not empty, first take the value of the top element of the stack, and then reduce the top pointer by 1;
Stack empty condition: S.top= =-1;
Stack full condition: S.top= =MaxSize-1;
Stack length: S.top+1.
basic operation
//initialization
void InitStack(SqStack &S) {
S->top = -1;
}
//Judge stack empty
bool StackEmpty(SqStack S) {
if (S->top == -1)
return true;
else
return false;
}
//Enter the stack
bool Push(SqStack &S, int x) {
if (S->top == MaxSize - 1)
return false;
else {
S->top++;
S->data[S->top] = x;
}
return true;
}
//Out of stack
bool Pop(SqStack &S, int &x) {
if (S->top == -1)
return false;
else {
*x = S->data[S->top];
S->top--;
return true;
}
}
//Read stack top element
bool getTop(SqStack &S, int &x) {
if (S->top == -1)
return false;
*x = S->data[S->top];
return true;
}
Chain stack
typedef struct LinkNode{
int data;
struct Linknode *next;
}stack;
Insertion and deletion are performed in the header
bool push(stack* S,int e){
p=(struct linkNode*)malloc(sizeof(LinkNode));
p->data=e;
p->next=S;
S=p;
return true;
}
bool empty(stack* S){
if(S->head==NULL){
return true;
}
else{
return false;
}
}
bool pop(stack* S,int* e){
if(emptyz(S)){
return false;
}
e=S->data;
struct Linknode* p=S;
S=S->next;
free(p);
return true;
}
queue
Basic concepts of queue
Definition of queue
Queue is also a linear table with limited operations. It is only allowed to insert in one segment and delete at the other end.
Queue operation
void InitQueue(&Q);//Initialize the queue and construct an empty queue Q. bool QueueErnpty(Q);//Judge that the queue is empty. If the queue Q is empty, return seven rue, otherwise return false. void EnQueue(&Q,x);//Join the queue. If queue Q is not full, add x to make it a new tail. void DeQueue(&Q,x);//Out of the queue. If queue Q is not empty, delete the queue header element and return it with x. void GetHead(Q, &x);//Read the queue header element. If queue Q is not empty, assign the queue header element to x.
Storage structure of queue
Sequential team
#define MaxSize 50 / / define the maximum number of elements in the queue
typedef struct{
int data[MaxSize];//Store queue elements
int front,rear;//Queue head pointer and queue tail pointer
}SqQueue;
Initial state (team empty condition): Q.front = =Q.rear= = 0.
Queue entry operation: when the queue is not satisfied, first send the value to the queue end element, and then add 1 to the queue end pointer.
Out of queue operation: when the queue is not empty, first take the value of the queue head element, and then add 1 to the queue head pointer.
Generally, sequential queues are not used because the utilization of space is very low. If arrays are needed to implement queues, they are through circular queues
Circulation team
Initial: Q.front=Q.rear=0
Team leader pointer plus 1: Q.front=(Q.front+1)%MaxSize
End of queue pointer plus 1: Q.rear=(Q.front+1)%MaxSize
It should be noted that in this way, we can see that the conditions for full and empty teams are Q.front=Q.rear=0
So how to distinguish between full and empty?
Method 1: use a zone to distinguish between air and full teams
It is agreed that the queue head pointer will be full when the queue tail pointer is next, so we will use one less element
Full queue condition: (Q.rear+1)%MaxSize==Q.front
Air condition: Q.rear=Q.front
Method 2: add an element to represent the number of queue members
Full queue: Q.size==MaxSize
Team empty: Q.size==0
Method 3: add new members to distinguish whether the team is full or empty
Add operation flag=true, delete operation flag = false
Team full: q.rear = q.front & & fall
Team air: q.rear = q.front & &! falg
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0;
}
bool isEmpty(SqQueue Q){
if(Q.rear==Q.front) return true;
else return false;
}
bool isFull(SqQueue Q){
if((Q.rear+1)%MaxSize==Q.front)) return true;
else return false;
}
bool EnQueue(SqQueue &Q,int x){
if(isFull(Q))
return false;
Q.data[Q.rear]=x;
Q.rear=(Q.front+1)%MaxSize;
return true;
}
bool DeQueue(SqQueue &Q,int* x){
if(isEmpty(Q)) return false;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}
Chain team
typedef struct{
int data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear; ／／Queue head and tail pointers
}LinkQueue;
Q. Front = = null & & q.rear = = null queue is empty
//When initializing the queue, a header node is given for easy operation
void initQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}
bool isEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return true;
else
return false;
}
void enQueue(LinkQueue &Q,int x){
LinkNode* s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
bool deQueue(LinkQueue &Q,int* x){
if(Q.front==Q.rear)
return false;
LinkNode*p=Q.front->next;
x=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return true;
}
Double ended queue
Queues that can be inserted or deleted at the head and tail of the queue.