, I'm here again .

be careful , be careful This is probably the most detailed blog post you've seen so far about stacks in linear tables

therefore , You must study hard !!!

After learning , You'll learn to stack . If you can't learn , Just watch it a few more times !

Be sure to finish it , No pains, no gains

1. Concept and structure of stack

2. Implementation of stack

3. Code implementation

1. Concept and structure of stack

Stack ： A special linear table , It only allows the insertion and deletion of elements at the fixed end . Data insertion and deletion The end of the operation is called the top of the stack , The other end is called the bottom of the stack . Data elements in the stack comply with last in first out
LIFO（Last In First Out） Principle of .

notes ： The stack is like a gun , Advanced post launch , Backward first launch

Stack pressing ： Stack insertion is called stack entry / Stack pressing / Push , The input data is at the top of the stack .

Out of stack ： The deletion of stack is called out of stack . The output data is also at the top of the stack

notes ： Stack pressing , They are all operated at the top of the stack

Stack pressing ：

Out of stack ：

In short, we must remember to enter the stack , All operations are performed at the top of the stack , They all meet one characteristic, which is last in first out

2. Implementation of stack

The implementation of stack can generally use sequence table （ array ） Or linked list implementation , Relatively speaking, the implementation of the structure of the sequence table is better . Because the sequence table is at the end The cost of inserting data is relatively small .

Sequential storage ：

3. code implementation

test.c： Test file
#define _CRT_SECURE_NO_WARNINGS 1 #include"stack.h" int main() { ST
st;// Defines a ST Structural variables StackInit(&st); StackPush(&st, 1); StackPush(&st, 2);
StackPush(&st, 3); printf("%d ", StackTop(&st)); StackPop(&st); StackPush(&st,
4); printf("%d ", StackTop(&st)); StackPop(&st); StackPush(&st, 5);
StackPush(&st, 6); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st));
StackPop(&st); } StackDestory(&st); return 0; }
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h>
#include<stdbool.h> #include<assert.h> #include<stdlib.h> typedef int
STDataType; typedef struct Stack { STDataType *a; int top;// Subscript of stack top element int
capacity;// Space size }ST; // initialization void StackInit(ST* ps); // Destroy void StackDestory(ST*
ps); // Insert at top of stack （ Push ） void StackPush(ST* ps, STDataType x); // Delete at top of stack （ Stack out ） void
StackPop(ST* ps); // Get the data at the top of the stack STDataType StackTop(ST* ps); // Stack elements int
StackSize(ST* ps); // Determine whether the stack is empty bool StackEmpty(ST* ps);
The header of the library contains the function declaration , Type redefinition , Structure type , Custom function .

Next, let's implement the function of the custom function in the header file !!!

High energy ahead , Please note that , be careful   Cheer up

initialization ：
// initialization void StackInit(ST* ps) { assert(ps); STDataType tmp =
(STDataType)malloc(sizeof(STDataType)* 4); if (tmp == NULL) { assert(tmp); }
ps->a = tmp; ps->capacity = 4; ps->top = 0; }

First opened up 4 individual STDataType Such a big space , If the development is successful, assign the first address of the development space to ps->a,ps->capacity Record the size of the current space ,ps->top Number of elements in stack

Destroy stack ：
// Destroy void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL;
ps->top = ps->capacity = 0; }
Direct use free release ps->a, Then let ps->a by NULL

Give Way ps->top  ps->capacity  The number of recording elements and space size are changed to 0

Push ：
// Insert at top of stack （ Push ） void StackPush(ST* ps, STDataType x) { if (ps->top ==
ps->capacity) { STDataType tmp = realloc(ps->a,
ps->capacity*sizeof(STDataType)* 2); if (tmp == NULL) { printf("realloc
fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top]
= x; ps->top++; }
First, judge whether the stack needs to be increased , Then insert

Out of stack ：
// Delete at top of stack （ Out of stack ） void StackPop(ST* ps) { assert(ps); // The stack is empty , call Pop, Direct termination procedure
assert(ps->top); ps->top--; }
Push , Out of the stack is executed from the top of the stack

Get stack top element ：
// Get the data at the top of the stack STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return
ps->a[ps->top - 1]; }
First judge whether there is data in the stack , If any, go straight back to the top of the stack , If ps->top==0, that ps->top It's the top of the stack

Stack elements ：
// Stack elements int StackSize(ST* ps) { assert(ps); return ps->top; }
ps->top Is the number of elements in the stack , Because the subscript is stored by array 0 start , therefore ps->top Is the number of elements

Determine whether the stack is empty ：
// Determine whether the stack is empty bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
ps->top==0 It represents emptiness

You have get Are you there ???

QQ：2186529582​​​

Technology
Daily Recommendation