栈

一、栈的特点
(1)   栈(stack)是后进先出(last-in-first-out, LIFO)或先进后出(FILO)的。
(2)   栈有三个基础操作压入(push)，弹出(pop)，取数(getTop)操作都为O(1)时间。
(3)   栈有一个计数器counter或栈顶指针。

二、栈的基本操作
(1)   建栈(init)：在使用栈之前，首先需要建立一个空栈，称建栈；
(2)   压栈(push)：往栈顶加入一个新元素，称进栈(压栈)；
(3)   出栈(pop)：删除栈顶元素，称出栈(退栈、弹出)；
(4)   取栈顶(gettop)：查看当前的栈顶元素，称读栈；
(5)   测试栈(empty) 在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈；
(6)   显示栈(display)：输出栈的所有元素;
(7)   释放栈(setnull)：清空栈；

三、数组实现栈：

#include <iostream>
#define MAXN 505  //常量：栈的长度
using namespace std;
int stack[MAXN];//数组模拟栈
int top = -1;   //初始化栈指针 
int pop(){      //出栈
    int r;
    if(top < 0){
	r = -1; cout<<"栈空！"<<endl;
    }else{
	r = stack[top]; top--;
    }
    return r;
} 
void push(int value){  //入栈
    if(top >= MAXN - 1){ 
        cout<<"栈满"<<endl;
    }else{
	top++; stack[top] = value;
    }
} 
void display(){//显示栈,栈其实没有这个功能
    int i;
    for(i = top;i >= 0;i--){
	cout<<stack[i]<<" ";
    }
    cout<<endl;
} 
int main(){
    int order;  //指令 
    int x,t;
    cout<<"输入指令：";
    while(true){
	cout<<"1:入栈,2:出栈,3:显示栈!"<<endl;
	cin>>order;
	if(order == 1){
	    cin>>x;
	    push(x);
	    display();	
	}else if(order == 2){
	    t = pop();
	    if(t != -1){
		cout<<t<<"出栈!"<<endl;
		display();
	    }
	}else if(order == 3){
	    display();
	}
    }
    return 0;
}