1. Basic concept of stack

Stack is a restrictive linear table, which limits the insertion and deletion of linear tables to only one end of the table. Generally, the end of the table that allows insertion and deletion is called the Top of the stack. Therefore, the current position of the Top of the stack changes dynamically, which is indicated by a position indicator called the Top of the stack pointer. The other end of the table is called the Bottom of the stack. When there are no elements in the stack, it is called an empty stack.

The stack is modified according to the principle of last in first out. For example, if the elements are stacked in the order of a1,a2,a3,..., an, the stack order is an,..., a3,a2,a1. Each time the elements of the elements entering the stack are placed on the original stack top element to become a new stack top. Each time the elements leaving the stack are the stack top elements in the current stack, that is, the last elements entering the stack.

Stack mainly has two storage structures: sequential storage structure and chain storage structure.

2. Sequence stack

Sequential stack is a stack realized by sequential storage structure, which uses a group of storage units with continuous addresses to store data elements from the bottom of the stack to the top of the stack in turn. A position pointer top is used to dynamically indicate the position of the top element of the stack in the sequential stack. top=-1 means an empty stack.

Storage structure and initialization of sequential stack

/*Storage structure of sequential stack*/
# define Stack_Size 50

typedef struct {
	int elem[Stack_Size];			//A one-dimensional array used to store elements in the stack
	int top;						//Store the subscript of the top element of the stack. Top is - 1, indicating an empty stack
}SeqStack;

/*Initialization sequence stack*/
void InitStack(SeqStack* S) {
	S->top = -1;
}

Empty and full judgment of sequence stack

/*Air judgment*/
int IsEmpty(SeqStack* S) {
	if (S->top == -1)				//Stack is empty
		return TRUE;
	else
		return FALSE;
}

/*Full sentence*/
int IsFull(SeqStack* S) {
	if (S->top == Stack_Size - 1)	//Stack full
		return TRUE;
	else
		return FALSE;
}

Sequentially stack in, stack out, and read stack top elements

/*Sequential stack*/
int Push(SeqStack* S, int x) {
	if (S->top == Stack_Size - 1)	//Stack full
		return FALSE;
	S->top++;
	S->elem[S->top] = x;			//x stack
	return TRUE;
}

/*Sequential stack*/
int Pop(SeqStack* S, int *x) {
	if (S->top == -1)				//Stack is empty
		return FALSE;
	*x = S->elem[S->top];			//Stack top element assigned to x
	S->top--;
	return TRUE;
}

/*Read stack top element*/
int GetTop(SeqStack* S, int* x) {
	if (S->top == -1)				//Stack is empty
		return FALSE;
	else {
		*x = S->elem[S->top];		//Stack top element assigned to x
		return TRUE;
	}
}

3. Double ended sequential stack (two stack sharing technology)

Double ended sequential stack is a two stack sharing technology. Apply for a shared one-dimensional array space S[M], and place the bottom of the two stacks at both ends of the one-dimensional array, which are 0 and M-1 respectively.

Storage structure and initialization of double ended stack

/*Double ended sequential stack storage structure*/
# define M 100

typedef struct {
	int Stack[M];
	int top[2];						//top[0] and top[1] are two stack top indicators respectively
}DqStack;

/*Dual ended sequential stack initialization*/
void InitStack(DqStack* S) {
	S->top[0] = -1;
	S->top[1] = M - 1;
}

Double end stack in and out

/*Stacking operation of double ended sequential stack*/
int Push(DqStack* S, int x, int i) {
//Push data element x into stack i
	if (S->top[0] + 1 == S->top[1])		//Stack full
		return FALSE;
	switch (i) {
	case 0:								//Press into stack 0
		S->top[0]++;
		S->Stack[S->top[0]] = x;
		break;
	case 1:								//Press into stack 1
		S->top[1]--;
		S->Stack[S->top[1]] = x;
		break;
	default:
		return FALSE;
	}
	return TRUE;
}

/*Stack out operation of double ended sequential stack*/
int Pop(DqStack* S, int *x, int i) {
//Pop the stack top element from stack i and send it to x
	switch (i) {
	case 0:								//Stack 0 out of stack
		if (S->top[0] == -1)			//Stack is empty
			return FALSE;
		*x = S->Stack[S->top[0]];
		S->top[0]--;
		break;
	case 1:								//Stack 1 out of stack
		if (S->top[1] == M)				//Stack is empty
			return FALSE;
		*x = S->Stack[S->top[1]];
		S->top[1]++;
		break;
	default:
		return FALSE;
	}
	return TRUE;
}

4. Chain stack

The chain stack uses the linked list as the storage structure, and the header pointer of the linked list is the top pointer of the stack.
Storage structure of chain stack

/*Chain stack storage structure*/
typedef struct node {
	int data;
	struct node* next;
}LinkStackNode;

typedef LinkStackNode* LinkStack;

Chain stack in and out

/*Chain stack operation*/
int Push(LinkStack LS, int x) {
	LinkStackNode* temp;
	temp = (LinkStack*)malloc(sizeof(LinkStackNode));
	temp->data = x;
	temp->next = LS->next;
	LS->next = temp;					//Modify the current stack top pointer
}

/*Chain stack out operation*/
int Pop(LinkStack LS, int* x) {
	LinkStackNode* temp;
	temp = LS->next;
	if (temp == NULL)					//Stack is empty
		return FALSE;
	LS->next = temp->next;
	*x = temp->data;
	free(temp);
	return TRUE;
}

Reference: Geng Guohua data structure - Description in C language (Second Edition)