栈的定义
栈实际上也是线性表，只不过是一种特殊的线性表。其特殊性在于栈的基本操作是线性表操作的子集，他们的操作受限于线性表，可称为限定性的数据结构。
栈(stack)是限定仅在表尾进行插入和删除操作的线性表，它是一种后进先出(Last in First out ,LIFO)的线性表
栈的特性
- 允许插入和删除的一段称为栈顶(top)，另外一段称为栈底(bottom)。
- 不含任何数据元素的栈称为空栈。
- 栈的元素必须后进先出。
栈的操作
- 插入操作
栈的插入操作(Push)，叫做进栈，也称压栈、入栈。
进栈
- 删除操作
栈的删除操作(Pop)，叫做出栈，也称弹栈。
出栈
栈的顺序存储结构及实现
栈的本质是一个线性表，线性表有两种存储形式，栈也分为栈的顺序存储结构和栈的链式存储结构
在操作栈的时候，栈会有三种情况：栈普通情况、空栈、栈满。
栈的三种情况
定义一个顺序顺序存储结构
#include <stdio.h>
#include <stdlib.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;
#define STACK_INIT_SIZE 100 /* 初始化栈空间为 100 */
#define STACKINCREMENT 10
typedef int Status; /*Status是函数的类型，其值是函数结果状态码，如OK等*/
typedef int ElemType;
typedef struct {
ElemType * base; /* 指向栈底的指针变量 */
ElemType * top; /* 指向栈顶的指针变量 */
int stackSize; /* 栈的当前可使用的最大容量 */
}sqStack;
也可以这样声明
typedef struct {
ElemType data[MAXSIZE];
int top; /* 用于标注栈顶的位置 */
int stackSize; /* 栈的当前可使用的最大容量 */
}sqStack;
创建一个顺序顺序存储结构的栈
#define STACK_INIT_SIZE 100 /* 初始化栈空间为 100 */
/**
* 创建栈
*/
void 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;
}
一、入栈操作
/**
* 入栈操作
*/
Status 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; // 元素e入栈，赋值到栈顶空间
s->top++; // 栈顶指针增加1
return OK;
}
二、出栈操作
/**
* 出栈操作（删除栈S的栈顶元素，用e返回其值）
*/
Status Pop(sqStack * s, ElemType *e){
if (s->top == s->base) // 栈空
return ERROR;
s->top--; // 栈顶指针减1
*e = *(s->top); // 将要删除的栈顶元素赋值给e
// *e = *--(s->top);
return OK;
}
三、清空栈
清空一个栈，就是将栈中的元素全部作废，但是栈本身物理空间并不发生变化。这里的方式定义的栈，只需要将s->top = s->base;即可实现栈的清空。
/**
* 清空一个栈(将栈中的元素全部作废，栈本身的物理空间并不发生变化)
*/
Status ClearStack(sqStack *s){
s->top = s->base;
return OK;
}
四、销毁栈
销毁一个栈和释放一个栈不同，销毁一个栈是要释放该栈所占据的物理内存空间。
/**
* 销毁栈(释放该栈锁占据的物理内存空间)
*/
Status DestoryStack(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;
return OK;
}
五、计算栈的当前容量
计算栈的当前容量也就是计算栈中元素的个数，在这里只需要返回即可
/**
* 计算栈的当前容量
*/
int StackLen(sqStack s){
return (s.top - s.base);
}
网友评论