栈（Stack）

1、顺序栈的定义

  • 堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈遵循“后进先出”（Last In First Out，LIFO）的原则，即最后一个被放入栈中的元素总是第一个被取出。
  • 先进入栈的元素在底部，接着进去的在底部上面一个位置，出栈的时候从栈顶取。类似于自动步枪的弹夹，最先进入弹匣的，是最后射出的。

2、栈的特点

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

3、栈的基本操作

  1. 建栈（init）：在使用栈之前，首先需要建立一个空栈，称建栈；

  2. 压栈（push）：往栈顶加入一个新元素，称进栈（压栈）；

  3. 出栈（pop）：删除栈顶元素，称出栈（退栈、弹出）；

  4. 取栈顶（gettop）：查看当前的栈顶元素，称读栈；

  5. 测试栈（empty）在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试 栈；

  6. 显示栈（display）：输出栈的所有元素；

  7. 释放栈（setnull）：清空栈；

4、栈的操作代码

初始化、入栈、出栈、显示栈！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream> 
#define size 3//常量：栈的长度
using namespace std;
int stack[size];//数组模拟栈 int top = -1;//初始化栈指针
//入栈
void push(int value){
    if(top == MAXN - 1){
    	cout<<"栈满"<<endl;
        return;
    }
    top++;
    stack[top] = value;
}
//出栈
int pop(){
    if(top == -1){
        cout<<"栈空！"<<endl;
        return;
    }
    top--;
}

//显示栈
void display(){
    int i;
    for(i = top;i >= 0;i--){
    	cout<<stack[i]<<" ";
    }
    cout<<endl;
}

int main(){
    int order;//指令 int x,t;
    cout<<"输入指令："; 
    while(1 == 1){
        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; 
}