Stack and queue:

A stack is a linear table that is restricted to insert and delete operations only at the end of the table. We call the end that allows insertion and deletion as the top of the stack, the other end as the bottom, and the stack without any elements as an empty stack. The stack becomes a linear table of Last In First Out (LIFO structure for short).        

A queue is a linear table that only allows insertion at one end and deletion at the other.

Sequential storage structure of stack

The insertion operation of stack is called entering stack, also known as pressing stack and entering stack. Similar bullets enter the magazine, as shown in Figure 1 below.

The deletion operation of stack is also called stack, and some are called pop stack. Like the bullet out of the clip, as shown in Figure 2 below.

Stack structure definition:

typedef int SElemType; /* SElemType The type depends on the actual situation, which is assumed to be int */
/* Sequential stack structure */
typedef struct
{
        SElemType data[MAXSIZE];
        int top; /* Pointer for stack top */
}SqStack;

Stack push:

/* Insert element e as the new stack top element */
Status Push(SqStack *S,SElemType e)
{
        if(S->top == MAXSIZE -1) /* Stack full */
        {
                return ERROR;
        }
        S->top++;				/* Stack top pointer increases by one */
        S->data[S->top]=e;  /* Assign the newly inserted element to the stack top space */
        return OK;
}

Stack out operation pop:

/* If the stack is not empty, delete the top element of S, return its value with e, and return OK; Otherwise, ERROR is returned */
Status Pop(SqStack *S,SElemType *e)
{ 
        if(S->top==-1)
                return ERROR;
        *e=S->data[S->top];	/* Assign the stack top element to be deleted to e */
        S->top--;				/* Stack top pointer minus one */
        return OK;
}

Shared space of two stacks:

In extreme cases, if stack 2 is empty, stack 1 is full when top1 of stack 1 is equal to n-1. Conversely, when stack 1 is empty and top2 is equal to 0, stack 2 is full. But more often, when two stacks meet, that is, when the difference between two pointers is 1, that is, top1 + 1 == top2, the stack is full.

Code of two stack shared space structure:

/* Two stack shared space structure */
typedef struct 
{
        SElemType data[MAXSIZE];
        int top1;	/* Stack 1 stack top pointer */
        int top2;	/* Stack 2 stack top pointer */
}SqDoubleStack;

For the push method of shared space between two stacks, in addition to inserting the element value parameter, we also need to have a stack number parameter stackNumber to judge whether it is stack 1 or stack 2. Insert element code:

/* Insert element e as the new stack top element */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
        if (S->top1+1==S->top2)	/* The stack is full and cannot push new elements */
                return ERROR;	
        if (stackNumber==1)			/* There are elements in stack 1 */
                S->data[++S->top1]=e; /* If it is stack 1, first top1+1 and then assign a value to the array element. */
        else if (stackNumber==2)	/* There are elements in stack 2 */
                S->data[--S->top2]=e; /* If it is stack 2, first top2-1 and then assign a value to the array element. */
        return OK;
}

For the pop method of shared space between two stacks, the parameter is only to judge the stack number of stack 1 and stack 2, and the parameter stackNumber. code:

/* If the stack is not empty, delete the top element of S, return its value with e, and return OK; Otherwise, ERROR is returned */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{ 
        if (stackNumber==1) 
        {
                if (S->top1==-1) 
                        return ERROR; /* Description stack 1 is empty and overflows */
                *e=S->data[S->top1--]; /* Take the top element of stack 1 out of the stack */
        }
        else if (stackNumber==2)
        { 
                if (S->top2==MAXSIZE) 
                        return ERROR; /* Description stack 2 is empty and overflows */
                *e=S->data[S->top2++]; /* Take the top element of stack 2 out of the stack */
        }
        return OK;
}

Chain storage structure of stack (chain stack)

For the chain stack, the stack is basically not full, unless there is no space available for memory. At this time, the computer operating system has faced the situation of crash.

For the empty stack, the original definition of the linked list is that the head pointer points to null, so the emptiness of the chain stack is actually when top = NULL.

The structure code of the chain stack is:

/* Chain stack structure */
typedef struct StackNode
{
        SElemType data;
        struct StackNode *next;
}StackNode,*LinkStackPtr;


typedef struct
{
        LinkStackPtr top;
        int count;
}LinkStack;

The operation of chain stack is mostly similar to that of single chain list, but it is special in insertion and deletion.

Chained storage structure of stack - stacking operation:

For the push operation of the chain stack, it is assumed that the new node with the element value of e is s and top is the pointer to the top of the stack. The schematic diagram is as follows:

 

/* Insert element e as the new stack top element */
Status Push(LinkStack *S,SElemType e)
{
        LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); 
        s->data=e; 
        s->next=S->top;	/* Assign the current stack top element to the direct successor of the new node, as shown in figure ① */
        S->top=s;         /* Assign the new node s to the stack top pointer, as shown in figure ② */
        S->count++;
        return OK;
}

Chained storage structure of stack - out of stack operation:

pop operation of chain stack. Suppose that the variable p is used to store the top node of the stack to be deleted, move the top pointer down one bit, and finally release P.

 

/* If the stack is not empty, delete the top element of S, return its value with e, and return OK; Otherwise, ERROR is returned */
Status Pop(LinkStack *S,SElemType *e)
{ 
        LinkStackPtr p;
        if(StackEmpty(*S))
                return ERROR;
        *e=S->top->data;
        p=S->top;					/* Assign the top node of the stack to p, as shown in figure ③ */
        S->top=S->top->next;    /* Make the pointer at the top of the stack move down one bit and point to the next node, as shown in figure ④ */
        free(p);                    /* Release node p */        
        S->count--;
        return OK;
}

If the element changes during the use of the stack are unpredictable, sometimes small and sometimes very large, it is best to use the chain stack. On the contrary, if its changes are within the controllable range, it is better to use the sequential stack.

Recursion: we call a function that directly calls itself or indirectly calls itself through a series of call statements, which is called a recursive function.

Each recursive definition must have at least one condition. When it is satisfied, the recursion is not in progress, that is, it no longer references itself, but returns the value to exit.

queue

queue: a linear table that allows insertion at one end and deletion at the other.

Queue is a First In First Out linear table, called FIFO for short. The end that allows insertion is called the tail of the queue, and the end that allows deletion is called the head of the queue.

 

Definition of circular queue: we call this sequential storage structure of queue head to tail as circular queue.

Chain storage structure and implementation of queue: the chain storage structure of queue is actually a single chain list of linear table, but it can only end in and end out. We call it chain queue for short.

 

Structure code of chain queue:

typedef int QElemType; /* QElemType The type depends on the actual situation, which is assumed to be int */

typedef struct QNode	/* Node structure */
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct			/* Linked list structure of queue */
{
   QueuePtr front,rear; /* Head and tail pointer */
}LinkQueue;

Chained storage structure of queue -- queue entry operation

Code:

/* Insert a new tail element with element e as Q */
Status EnQueue(LinkQueue *Q,QElemType e)
{ 
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
	if(!s) /* Storage allocation failed */
		exit(OVERFLOW);
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;	/* Assign the new node s with element e to the successor of the original team tail node, as shown in figure ① */
	Q->rear=s;		/* Set the current s as the end of the queue node, and the rear points to s, as shown in figure ② */
	return OK;
}

Chained storage structure of queue -- out of queue operation

/* If the queue is not empty, delete the queue header element of Q, return its value with e, and return OK; otherwise, return ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return ERROR;
	p=Q->front->next;		/* Temporarily save the queue head node to be deleted to p, as shown in figure ① */
	*e=p->data;				/* Assign the value of the queue head node to be deleted to e */
	Q->front->next=p->next;/* Assign the successor p - > next of the original team's head node to the successor of the head node, as shown in figure ② */
	if(Q->rear==p)		/* If the head of the queue is the tail of the queue, point the rear to the head node after deletion, as shown in figure ③ */
		Q->rear=Q->front;
	free(p);
	return OK;
}

In general, when the maximum queue length can be determined, it is recommended to use circular queue. If you cannot estimate the length of the queue, use chain queue.