栈与队列
栈
栈是一种限定仅在一端进行插入和删除的 线性表 ，无论是往栈中插入元素还是删除栈中的元素，或者读取栈中的元素，都只能固定在线性表的一端进行。通常，栈的这一端被称为栈顶（top），与此相对，栈的另一端叫做栈底（bottom）。由此可知，最后插入栈中的元素是最先被删除或读取的元素，而最先压入的元素则被放在栈的底部，要到最后才能取出。换言之，栈的修改是按后进先出的原则进行的。因此，通常栈被称为后进先出（last in first out）表，简称LIFO表。
图1 栈的具体流程
栈的抽象数据类型
下面的C++类模版给出了栈类（名字为Stack，模版参数为元素类型T）的一个抽象数据类型定义。
栈的抽象定义
template <class T>
class Stack
{
public:
void clear();
bool push(const T item);
bool pop(T & item);
bool top(T & item);
bool isEmpty();
bool isFull();
};
栈的具体定义程序
该程序由C++编辑，可以实现 顺序栈 的存储和弹出
具体的栈程序
#include <iostream>
#define MAX 100//定义数组长度
using namespace std;
struct Stack//建立栈
{
int value[MAX];
int top;//栈顶的数组序号
};
void Init(Stack &s)//初始化栈
{
s.top=-1;
}
int Push(Stack &s,int e)//把元素e压入栈顶
{
if(s.top>MAX-1)//如果超出栈的容量，返回0
return 0;
s.top++;//栈顶加1
s.value[s.top]=e;//把e赋给栈顶
return 1;
}
int IsEmpty(Stack s)//判定栈是否为空
{
if(s.top==-1)
return 1;
else
return 0;
}
int Pop(Stack &s,int &m)//取出栈顶元素，并删除栈顶
{
if(s.top==-1)//top等于-1，栈为空
{
cout<<"栈为空，不能读取栈顶元素"<<endl;
return 0;
}
else
{
m=s.value[s.top]; //先取出top元素，再使top-1
s.top--;
return 1;
}
}
int main()
{
Stack slist;
Init(slist);
cout<<"栈是否为空(1为空，0为不空）"<<endl;
cout<<IsEmpty(slist)<<endl;
cout<<"输入"<<endl;
int e;
int m;
cin>>e;
while (e!=0)
{
Push(slist,e);
cout<<"栈是否为空(1为空，0为不空）"<<endl;
cout<<IsEmpty(slist)<<endl;
cout<<"获取并弹出栈顶元素:";
Pop(slist,m);
cout<<m<<endl;
cout<<"栈是否为空(1为空，0为不空）"<<endl;
cout<<IsEmpty(slist)<<endl;
cin>>e;
}
return 0;
}
栈的特点
- 先进后出
- 具有记忆功能
- 对栈的插入与删除操作中，不需要改变栈底指针
- 栈可以使用顺序存储也可以使用链式存储
