Stack

Basic concept of stack

Basic properties of stack

1. A Stack is a linear table that allows only one segment to be inserted or deleted.
2. Top of stack. The end of a linear table that allows insertion and deletion.
3. The Bottom of the stack is fixed and cannot be inserted or deleted.
4. 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;
}
}
bool getTop(SqStack &S, int &x) {
if (S->top == -1)
return false;
*x = S->data[S->top];
return true;
}

Chain stack

int data;
}stack;

Insertion and deletion are performed in the header

bool push(stack* S,int e){
p->data=e;
p->next=S;
S=p;
return true;
}
bool empty(stack* S){
return true;
}
else{
return false;
}
}
bool pop(stack* S,int* e){
if(emptyz(S)){
return false;
}
e=S->data;
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.

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;
typedef struct{

Q. Front = = null & & q.rear = = null queue is empty

//When initializing the queue, a header node is given for easy operation
Q.front->next=NULL;
}
if(Q.front==Q.rear)
return true;
else
return false;
}
s->data=x;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
if(Q.front==Q.rear)
return false;
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.

Keywords: data structure

Added by aprinc on Sat, 01 Jan 2022 20:00:00 +0200