定义
栈是限定仅在表头进行插入和删除操作的线性表。
一种可以实现“先进后出”的存储结构
栈类似于箱子
允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；
栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。
分类
静态栈
动态栈
算法
出栈
压栈
应用
函数调用
中断
表达式求值
内存分配
缓冲处理
迷宫
栈的顺序存储
图片.png
- 代码实现（C语言）
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct {
ElemType *base; //指向栈底的指针
ElemType *top; //指向栈顶的指针
int stackSize; //当前可使用的最大容量
}sqStack;
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;
}
//入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1,直到栈满为止
void 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) = e;
s->top++;
}
//出栈操作就是在栈顶取出数据，栈顶指针随之下移操作，每当从栈内弹出一个数据，栈的当前容量就-1
void Pop(sqStack *s, ElemType *e) {
if (s->top == s->base)
{
return;
}
*e = *--(s->top);
}
//求栈的长度
int StackLen(sqStack s) {
return s.top - s.base;
}
//清空栈， 将栈中的元素全部作废，但栈本身物理空间并不发生改变（不是销毁）
void ClearStack(sqStack *s) {
s->top = s->base;
}
//销毁一个栈， 释放掉该栈所占据的物理内存空间
void 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;
}
栈的链试存储结构
- 栈因为只是栈顶来做插入和删除操作，所以比较好的方法就是将栈顶放在单链表的头部，栈顶指针和单链表的头指针合二为一。
- 入栈出栈操作代码实现如下：
typedef int ElemType;
typedef struct StackNode {
ElemType data; //存放栈的数据
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack {
LinkStackPtr top; //top指针
int count; //栈元素计数器
};
bool Push(LinkStack *s, ElemType e) {
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
p->data = e;
p->next = s->top;
s->top = p;
s->count++;
return true;
}
bool Pop(LinkStack *s, ElemType *e) {
LinkStackPtr p;
*e = s->top->data;
p = s->top;
s->top = s->top->next;
free(p);
s->count--;
return true;
}
利用栈的特点将二进制转换成十进制
- 将二进制转换成十进制的公式如下：
图片.png
- 代码实现
int main() {
ElemType c;
sqStack s;
int len, i, sum = 0;
InitStack(&s);
printf("请输入二进制数， 输入#符号表示结束!\n");
scanf_s("%c", &c);
while (c != '#')
{
Push(&s, c);
scanf_s("%c", &c);
}
//把'\n'从缓冲区去掉
getchar();
len = StackLen(s);
printf("栈的当前容量是:%d\n", len);
for (i = 0; i < len; i++)
{
Pop(&s, &c);
sum = sum + (c - 48) * pow(2, i);
}
printf("转换化为十进制数是：%d\n", sum);
getchar();
}
