棧與隊列
棧
棧是一種限定僅在一端進(jìn)行插入和刪除的 線性表 馋贤，無論是往棧中插入元素還是刪除棧中的元素，或者讀取棧中的元素畏陕，都只能固定在線性表的一端進(jìn)行配乓。通常，棧的這一端被稱為棧頂（top）惠毁，與此相對犹芹，棧的另一端叫做棧底（bottom）。由此可知鞠绰，最后插入棧中的元素是最先被刪除或讀取的元素腰埂，而最先壓入的元素則被放在棧的底部，要到最后才能取出蜈膨。換言之屿笼，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此翁巍，通常棧被稱為后進(jìn)先出（last in first out）表驴一，簡稱LIFO表。
圖1 棧的具體流程
棧的抽象數(shù)據(jù)類型
下面的C++類模版給出了棧類（名字為Stack灶壶，模版參數(shù)為元素類型T）的一個抽象數(shù)據(jù)類型定義肝断。
棧的抽象定義
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++編輯，可以實現(xiàn) 順序棧 的存儲和彈出
具體的棧程序
#include <iostream>
#define MAX 100//定義數(shù)組長度
using namespace std;
struct Stack//建立棧
{
int value[MAX];
int top;//棧頂?shù)臄?shù)組序號
};
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;
}
棧的特點
- 先進(jìn)后出
- 具有記憶功能
- 對棧的插入與刪除操作中，不需要改變棧底指針
- 椉浒Γ可以使用順序存儲也可以使用鏈?zhǔn)酱鎯?/li>
