# 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

[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}
*/
{
if((top = (stacklink)malloc(sizeof(stacklist))) == NULL)
{
#if DEBUG
printf("stacklist create error!\n");
#endif
return 0;
}

top->data = 0;
top->next = NULL;

}
```

### 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)
{
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 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}
*/
{
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}
*/
{
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! Keywords: C Algorithm data structure linked list

Added by MNS on Thu, 10 Mar 2022 15:07:56 +0200