©2020-2024 ioDraw All rights reserved
, 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 ：
Linked 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; }
stack.h: Header file
#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