栈与队列

栈

栈是一种限定仅在一端进行插入和删除的 线性表 ，无论是往栈中插入元素还是删除栈中的元素，或者读取栈中的元素，都只能固定在线性表的一端进行。通常，栈的这一端被称为栈顶（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;  
}  

栈的特点

• 先进后出
• 具有记忆功能
• 对栈的插入与删除操作中，不需要改变栈底指针
• 栈可以使用顺序存储也可以使用链式存储