栈是一种重要的线性结构, 可以这样讲, 栈是线性表的一种具体形式
栈这种后进先出的数据结构应用是非常广泛的
例如我们 Word,Photoshop 等的撤销功能也是如此再例如我们 C 语言的函数, 也是利用栈的基本原理实现的
一定义
栈 (Stack) 是一个后进先出 (Last in first out,LIFO) 的线性表, 它要求只在表尾进行删除和插入操作
所谓的栈, 其实也就是一个特殊的线性表(顺序表链表), 但是它在操作上有一些特殊的要求和限制:
栈的元素必须后进先出
栈的操作只能在这个线性表的表尾进行
注: 对于栈来说, 这个表尾称为栈的栈顶(top),
相应的表头称为栈底(bottom)
栈的操作
栈的插入操作(Push), 叫做进栈, 也称为压栈, 入栈
栈的删除操作(Pop), 叫做出栈, 也称为弹栈
空栈. png
进栈. png
出栈. png
二栈的存储结构
因为栈的本质是一个线性表, 线性表有两种存储形式, 那么栈也有分为
栈的链式存储结构
特性:
最开始栈中不含有任何数据, 叫做空栈, 此时栈顶就是栈底
然后数据从栈顶进入, 栈顶栈底分离, 整个栈的当前容量变大
数据出栈时从栈顶弹出, 栈顶下移, 整个栈的当前容量变小
栈的顺序存储结构. png
定义:
- typedef int ElemType;
- typedef struct
- {
- ElemType *base;
- ElemType *top;
- int stackSize;
- }sqStack;
这里定义了一个顺序存储的栈, 它包含了三个元素 base,top,stackSize
base 是指向栈底的指针变量,
top 是指向栈顶的指针变量,
stackSize 指示栈的当前可使用的最大容量
使用 ElemType* base 和 ElemType* top:
使用指针方式. png
或:
- typedef int ElemType;
- typedef struct
- {
- ElemType data[MAXSIZE];
- int top; // 用于标注栈顶的位置
- int stackSize;
- }
使用 int:
使用 int.png
三栈的操作
1. 创建一个栈
代码实现:
- #define STACK_INIT_SIZE 100
- initStack(sqStack *s)
- {
- s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
- if( !s->base )
- exit(0);
- s->top = s->base; // 最开始, 栈顶就是栈底
- s->stackSize = STACK_INIT_SIZE;
- }
2. 入栈操作
入栈操作又叫压栈操作, 就是向栈中存放数据
入栈操作要在栈顶进行, 每次向栈中压入一个数据, top 指针就要 + 1, 直到栈满为止
代码实现:
- #define SATCKINCREMENT 10
- Push(sqStack *s, ElemType e)
- {
- // 如果栈满, 追加空间
- if( s->top s->base>= s->stackSize )
- {
- s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
- if( !s->base )
- exit(0);
- s->top = s->base + s->stackSize; // 设置栈顶
- s->stackSize = s->stackSize + STACKINCREMENT; // 设置栈的最大容量
- }
- *(s->top) = e;
- s->top++;
- }
3. 出栈操作
出栈操作就是在栈顶取出数据, 栈顶指针随之下移的操作
每当从栈内弹出一个数据, 栈的当前容量就 - 1
代码实现:
- Pop(sqStack *s, ElemType *e)
- {
- if( s->top == s->base ){ // 栈已空
- return;
- }
- *e = *--(s->top);
- }
出栈示意图. png
三栈的其他操作
1. 清空一个栈
清空一个栈, 就是将栈中的元素全部作废, 但栈本身物理空间并不发生改变(不是销毁)
思路:
我们只要将 s->top 的内容赋值为 s->base 即可,
这样 s->base 等于 s->top, 也就表明这个栈是空的了
这个原理跟高级格式化只是但单纯地清空文件列表而没有覆盖硬盘的原理是一样的
代码实现:
- ClearStack(sqStack *s){
- s->top = s->base;
- }
2. 销毁一个栈
销毁一个栈与清空一个栈不同, 销毁一个栈是要释放掉该栈所占据的物理内存空间, 因此不要把销毁一个栈与清空一个栈这两种操作混淆
代码实现:
- DestroyStack(sqStack * s) {
- int i,
- len;
- len = s ->stackSize;
- for (i = 0; i <len; i++) {
- free(s ->base);
- s ->base++;
- }
- s ->base = s ->top = NULL;
- s ->stackSize = 0;
- }
四计算栈的当前容量
计算栈的当前容量也就是计算栈中元素的个数, 因此只要返回 s.top-s.base 即可
就是将两个指针相减, 两个地址相减, 减完之后并不是两个地址的差; 如果两个指针是指向整型的, 那么相减之后是他们中间隔了几个元素; 实际上是相当于两个地址相减之后再除以该元素所占的空间; 例如整型是占 4 个字节, 那么就是地址相减之后除以 4, 最后得到中间有多少个元素(注意两个指针的类型必须相同)
注意: 指针可以 ++ 或 --; 指针之间可以相减, 但是不能相加
注意: 栈的最大容量是指该栈占据内存空间的大小,(能够容纳多少数据)其值是 s.stackSize, 它与栈的当前容量不是一个概念
代码实现:
- int StackLen(sqStack s)
- {
- return(s.top s.base); // 重点
- }
来源: http://www.jianshu.com/p/7261a93b909e