1, Principle of stack

Stack is a linear table (commonly known as stack) that is restricted to insert and delete operations at one end

The end at which operations are allowed is called the "top of the stack"

The other fixed end is called "stack bottom"

When there are no elements in the stack, it is called "empty stack". Stack features: last in first out (LIFO).

2, Implementation of sequential stack

For the principle and implementation of sequence table, see this article:
[data structure and algorithm] program internal skill Part II - linear sequence table

1. Sequential stack principle

It is a kind of sequential table, which has the same storage structure as the sequential table. It is defined by the array and completes various operations with the stack top pointer top (relative pointer) represented by the array subscript.

Structure definition:

typedef  int  data_t ; /*Defines the data type of the data element in the stack*/
typedef struct 
{	
       data_t  *data ; 	/*Point to the storage space of the stack with a pointer*/
       int  maxlen;	/*Maximum number of elements in the current stack*/
       int  top ; 	/*A variable indicating the top position of the stack (array subscript)*/
  } sqstack; 		/*Sequential stack type definition*/

2. Stack creation

/**
 * @description: Creation of sequential stack
 * @param {int} len -User specified stack length
 * @return {sqstack-Stack top pointer}
 */
sqstack* stack_create(int len) {
	sqstack * s;

	if ((s =(sqstack *)malloc(sizeof(sqstack))) == NULL) 
	{
		printf("malloc sqstack failed\n");
		return NULL;
	}

	if ((s->data = (data_t *)malloc(len * sizeof(data_t)))==NULL) 
	{
		printf("malloc data failed\n");
		free(s);
		return NULL;
	}

	memset(s->data, 0, len*sizeof(data_t));
	s->maxlen = len;
	s->top = -1;

	return s;
}

3. Sequential stack

/**
 * @description: Enter the stack
 * @param {sqstack* } s-Stack top pointer
 * @param {data_t} value-Stack value
 * @return {-1-Function failed, 0-function succeeded}
 */
int stack_push(sqstack *s, data_t value) 
{
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}

	if (s->top == s->maxlen-1) 
	{
		printf("stack is full\n");
		return -1;
	}

	s->top++;
	s->data[s->top] = value;

	return 0;
}

4. Sequential stack

/**
 * @description: Out of stack
 * @param {sqstack*} s-Stack top pointer
 * @return {Stack top value}
 */
data_t stack_pop(sqstack *s) {
	s->top--;
	return (s->data[s->top+1]);
}

5. Sequential stack deletion

/**
 * @description: Sequential stack deletion
 * @param {sqstack*} s-Stack top pointer
 * @return {-1-Function failed, 0-function succeeded}
 */
int stack_free(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	
	if (s->data != NULL) 
		free(s->data);
	free(s);

	return 0;
}

6. Empty stack and whether to empty stack

/**
 * @description: Stack emptying
 * @param {sqstack*} s-Stack top pointer
 * @return {-1-Function failed, 0-function succeeded}
 */
int stack_clear(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	
	s->top = -1;
	return 0;
}

/**
 * @description: Determine whether the stack is empty
 * @param {sqstack*} s-Stack top pointer
 * @return {-1-Function failed, 1-stack is empty, 0-stack is not empty}
 */
int stack_empty(sqstack *s) 
{
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	return (s->top == -1 ? 1 : 0);
}

3, Implementation of linked list stack

For the principle and implementation of linked list, please see this article:
[data structure and algorithm] program internal skill Part III - single linked list

1. Single linked list implementation of stack

The insertion and deletion operations are carried out at the head of the linked list. The tail of the linked list is the bottom of the stack, and the pointer at the top of the stack is the head pointer.

Node definition:

typedef  int  data_t ;	 /*Define the data types of data elements in the stack*/
typedef  struct  node {
    data_t data ;		   /*Data domain*/
	struct  node  *next ;   /*Link pointer field*/
}stacklist,*stacklink; 		  /*Chain stack type definition*/

2. Create empty stack

/**
 * @description: Creation of single linked list stack
 * @param {*}
 * @return {Stack top pointer}
 */
stacklink stacklist_create()
{
	stacklink top;
	if((top = (stacklink)malloc(sizeof(stacklist))) == NULL)
	{
		#if DEBUG
		printf("stacklist create error!\n");
		#endif
		return 0;
	}
	
	top->data = 0;
	top->next = NULL;

	return top;
}

3. Stack

/**
 * @description: Stack - header insertion
 * @param {stacklink} top-Stack top pointer
 * @param {data_t} value-Stack value
 * @return {0-Function succeeded, 1-function failed}
 */
int stacklist_top_insert(stacklink top, data_t value)
{
	stacklink sl;
	if(top == NULL)
	{
		#if DEBUG
		printf("top is NULL!\n");
		#endif
		return 0;
	}
	
	if((sl = (stacklink)malloc(sizeof(stacklist))) == NULL)
	{
		#if DEBUG
		printf("stacklist create error!\n");
		#endif
		return 0;
	}
	
	sl->data = value;
	sl->next = top->next;
	top->next = sl;

	return 1;
}

4. Out of stack

/**
 * @description: Out of stack
 * @param {stacklink} top-Stack top pointer
 * @return {0-Function succeeded, 1-function failed}
 */
int stacklist_out(stacklink top)
{
	stacklink sl;
	int value;
	if(top == NULL)
	{
		#if DEBUG
		printf("top is NULL!\n");
		#endif
		return 0;
	}
	if(top->next == NULL)
	{
		#if DEBUG
		printf("stacklist is empty!\n");
		#endif
		return 0;
	}

	sl = top->next;
	top->next = sl->next;
	value = sl->data;
	
	free(sl);

	return value;
}

5. Delete linked list stack

/**
 * @description: Stack deletion
 * @param {stacklink} top-Stack top pointer
 * @return {0-Function succeeded, 1-function failed}
 */
int stacklist_free(stacklink top)
{
	stacklink sl = top;
	if(top == NULL)
	{
		#if DEBUG
		printf("top is NULL!\n");
		#endif
		return 0;
	}

	while(top)
	{
		top = top->next;
		free(sl);
		sl = top;
	}

	return 1;
}

6. Judge whether it is an empty stack

/**
 * @description: Judge whether it is an empty table
 * @param {stacklink} top-Stack top pointer
 * @return {-1-Function failed, 1 - empty stack, 0 - not empty stack}
 */
int stacklist_empty(stacklink top)
{
	if(top == NULL)
	{
		#if DEBUG
		printf("top is NULL!\n");
		#endif
		return -1;
	}
	return (top->next == NULL? 1:0);
}

4, Application of stack

Create operand stack and operator stack. Operators have priority.

① Scan the expression from left to right. When encountering an operand, it will enter the operand stack.
② When an operator is encountered, if its priority is higher than that of the element at the top of the operator stack, it will be put on the stack. On the contrary, take out the two consecutive operands at the top of the stack, store the results in the operand stack, and then continue to compare the priority of the operator with the top of the stack operator.
③ The left bracket will be put into the operator stack and the right bracket will not be put into the operator stack. Take out the operator at the top of the operator stack and the two operands at the top of the operand stack for operation, and press the result into the operand stack until the left bracket is taken out.

For example: calculation (4 + 8) × 2－3 ;

Operand stack: 4 8    	| 12  2		|24  3		|21
 Operator stack:( ＋     	|×		    |－		        |

To basically implement the program, click the following link for free:
Basic C program of stack

That's it!