In the next section, let's learn about stacks and queues!

(1) Stack

It can store operands in sequence and output them in reverse order when necessary! This is the stack!

Stack: a linear table with certain operation constraints. It aims to insert and delete one end (top, stack top).

(1) The stack implements the first in first out principle

Push(S,A)
Push(S,B)
Push(S,C)
Pop(s)
Pop(s)
Pop(s)//Output CBA

(2) The sequential structure of the stack is usually composed of a one-dimensional array and a variable that records the position of the elements at the top of the stack

#define Maxsize / / stores the maximum number of data elements
typedef struct SNode*Stack;
struct SNode{
    int Date[20];
    int top;
};

Important operations:

1) Stack

void Push(Stack PtrS,ElementType item)
{
   if(Ptrl->top==Maxsize-1)
  {
    printf("Stack full "");
    return;
 }
  else{
   Ptrs->Date[++PtrS->Top]=item;//->Priority over++
   return;
 }

2) Out of stack

ElementType Pop(stack ptrs)
{
  if(Ptrs->Top==-1)
   {
    printf("Stack empty ");
    return ERROR;
  }//ERROR is a special value of ElementType, which indicates an ERROR
 else
{
 return(Ptrs->Date[(Ptrs->Top)--]);
}

3) one array is used to store two stacks. It is required to maximize the array space, so that the array can succeed as long as there is a stack operation

Idea: the two stacks are placed on the two sides of the array and grow towards the middle. When the pointers at the top of the two stacks meet, it means that they are full

#define Maxsize 10
struct DStack{
 int Date[Maxsize];
 int Top1;//Stack top pointer of stack 1
 int Top2;//Stack top pointer of stack 2
 }s;

Empty stack condition
S.Top1=-1;
S.Top2=Maxsize;

 

void push(struct DStack*PtrS,int item,int Tag)//tag is the flag of two stacks, with values of 1 and 2
{
   if(PtrS->Top2-PtrS->Top1==1)
    {
         printf("Stack full");  return;
    }
   
   if(Tag==1)
    PtrS->Date[++(PtrS->Top1)]=item;
   else
      Ptrs->Date[--(PtrS->Top2)]=item;
}

int pop(ptrs,int tag)
{
  if(tag==1)
   {
     if(ptrs->top1==-1){
        printf("Stack 1 empty");
        return;
     }
   else return Ptrs->Data[Ptrs->top1--];
}
    else{
     if(ptrs->top2==maxsize)
      { printf("Stack 2 empty");
       return NULL;}
     else return Ptrs->Data[Ptrs->top2++];
    }
}

(3) Chain storage structure of stack

The chain storage structure of stack is actually a single chain list, which is called chain stack. Insert and delete operations can only be implemented at the top of the} chain stack.

When using a linked list to represent a stack, the linked list must be on the head of the stack. Top must be on the head of the linked list

typedef struct SNode*Stack;
struct SNode{
        int Date;
        struct SNode*Next;
  }

 

Stack CreateStack()
{//Build a header node of the stack and return a pointer
  Stack S;
  S=(Stack)malloc(sizeof(struct SNode));
  S->Nest=NULL;
  return S;
}

int IsEmpty(Stack S)
{  //Judge whether stack S is empty. If it is empty, return integer 1; otherwise, return 0
   return(S->Next==NULL);
}

 

void Push(ElementType item,Stack S)
{   //Put the element item on the stack S

 struct SNode *TmpCell;
 TmpCell=(struct SNode*)malloc(struct SNode);
 TmpCell->Element=item;
 TmpCell->Next=S->Next;
 S->Next=TmpCell;

}

ElementType Pop(Stack S)
{
   //Delete and return the top element of stack S
 struct SNode *FirstCell;
 ElementType TopElem;

if(isempty(s))
 {
  printf("Stack empty ");
  return NULL;
 }

else{
 FirstCell=s->Next;
 S->Nest=FirstCell->Next;
 TopElem=FirstCell->Element;
 free(FirstCell);
 return TopElem;
}
}

(4) Example: operational evaluation of infix expression -- conversion to suffix expression

2+9/3-5-------2 9 3 / +5 -

1) the relative order of operands remains unchanged

2) Change the order of operation symbols (store the waiting symbols and compare the waiting symbols with subsequent symbols)

Encountered an open parenthesis and pushed onto the stack

If you encounter the right parenthesis, pop up the operator at the top of the stack and output it until you encounter the left parenthesis

Encountered operator: compare the priority of the operator and the stack top operator (if it is greater than the stack top, press the stack. If it is less than the stack top, pop up the stack top operation symbol for output, and then compare the new stack top operator until it is greater than the priority of the stack top operator, and then press the operator on the stack)

Output: 2 9 3 ／ Output: 2 9 3 /+

Storage: + / storage:

What to do with brackets: a*(b+c)/d=abc+*d/

(II) queue

Queue: linear table with certain operation constraints

(1) Insert and delete operations: you can only insert at one end and delete at the other

Data insertion: in queue (AddQ)

Data deletion: out of queue (DeleteQ)

First come first serve: FIFO table

(2) sequential storage: it is composed of a one-dimensional array, a variable front for recording the position of the head element of the queue and a variable rear for recording the position of the tail element of the queue

#define MaxSize 10
struct QNode{
  int a[MaxSize];
  int rear;
  int front;
 };
typedef struct QNode*queue;

For the formation of a forward loop queue, if the first few elements are empty and deleted, but the rear has pointed to the end of the queue, but still needs to be added, so a closed loop should be formed When front=rear, it can be considered that the queue has no elements But for example, there are a elements, but there are a+1 cases (0 elements, 1 element... A element). As a result, empty and full cannot be fully determined.

Solution: (1) use an additional tag: Size or tag field

(2) There are n array spaces, but only (n-1) array spaces are used

Queue:

void Add(Queue PtrQ,int item)
{
 if((PtrQ->rear+1)%MaxSize==ptrl->front)//To become 0, you can use the remainder function
  { 
  printf("Queue full");
  return;
  }

PtrQ->rear=(PtrQ->rear+1)%MaxSize;
PtrQ->Data[PtrQ->rear]=item;
}

Out of queue:

int deleteQ(queue PtrQ)
{
 if(PtrQ->front==ptrQ->rear)
 {
   printf("Queue empty ");
   return error;
 }
 else{
   PtrQ->front=(PtrQ->front+1)%MaxSize;
   return PtrQ->a[PtrQ->front);
  }
}

(3) Implementation of chain storage structure of queue: single chain list Deletion and insertion are carried out at the two heads of the linked list respectively

Front in front, rear

struct Node{
  int Data;
 struct Node*Next;
}//Each node in the linked list

struct QNode{//Chain queue structure
  struct Node*rear;
  struct Node*front;
 };

typedef struct QNode*Queue;
Queue PtrQ;//Is a pointer to the structure containing rear and front

Out of queue operation of chain queue without leading node:

int DeleteQ(Queue PtrQ)
{
  struct Node*FrontCell;
  int FrontELem;
 
 if(PtrQ->front==NULL)
 {
  printf("queue is empty");
  return ERROR;
 }

 FrontCell=PtrQ->front;
 if(PtrQ->front==PtrQ->rear)//If there is only one element in the queue
   PtrQ->front=PtrQ->rear=NULL;//Set the queue to empty after deletion
 else
   PtrQ->front=PtrQ->front->Next;
FrontElem=FrontCell->Data;
free(FrontCell);//Free up space for deleted nodes
return FrontElem;
}