栈
1.1 栈的形象概念
栈(Stack)是一种线性结构,可以想象成一个封闭的箱子。数据只能从一端插入和删除,这一端称为栈顶,另一端称为栈底。其存取方式为后进先出(LIFO, Last In First Out)或先进后出。

图中展示了空栈到压入三个元素的过程,最底下是栈底,最顶部是栈顶。
核心操作:
- 压栈(Push):数据的插入操作,从栈顶进入。
- 出栈(Pop):数据的删除操作,从栈顶弹出。
- 栈顶定位:通常用
top表示。初始化为 0 时代表栈顶元素的下一个位置;初始化为 -1 时代表当前栈顶元素位置。
1.2 栈的实现
栈通常以数组或链表方式实现。动态增长的数组较为常见,需要用到 malloc 进行扩容。基本操作包括初始化、压栈、出栈、获取栈顶元素、判空及销毁。
1.2.1 头文件内容
// Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack {
STDataType* _a;
int _top; // 栈顶下标
int _capacity; // 容量
} Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
;
STDataType ;
;
;
;



