栈是只能在某一端插入和删除的特殊线性表。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进栈(PUSH),删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）。

一、栈的定义

二、分类

• 静态栈：使用数组

• 动态栈：链表

• 标准库STL中的stack

三、算法

• 入栈：push

• 出栈：pop

• 判断栈空：empty

• 栈大小：size

• 访问栈顶：top
  

1. 进栈（PUSH）算法

   ①若top >= n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则进行②）

   ②top++ (栈指针加1，指向进栈地址)

   ③s[top]=x，结束（x为新进栈的元素）

2. 退栈（POP）算法

   ①若top<=0，则给出下溢信息，作出错处理（退栈前先检查是否已为空栈，空则下溢；不空则进行②）

   ②x=s[top],(退栈后的元素赋给x)

   ③top--,结束（栈指针减1，指向栈顶）

四、应用

• 函数中调用其他函数

• 中断

• 表达式求值

• 内存分配

• 缓冲处理

• 迷宫