数组模拟实现 栈

一、栈简介

栈（stack）又名堆栈，它是一种运算受限的 线性表 。用于数据的暂时存储。

1. 运算受限：限定仅在 表尾 进行插入和删除操作
也因此使得栈元素 后进先出 ( LIFO )

2. 栈顶：表尾元素，即能够进行插入和删除操作的元素；
3. 栈底：相对于栈顶的另一端元素。

4. 入栈：向栈中插入新的元素（又称为 进栈、压栈），形成新的栈顶；
5. 出栈：删除栈顶元素（又称为 退栈）

6. 空栈：栈中元素个数为 0；

{:height=”35%” width=”35%”}

二、用数组实现栈

1. 栈的定义

int stk[N]; // 用于存储栈中的元素 
int tt; // 表示 栈顶 元素的下标，初始值为 0
// 若将 tt 定义为全局变量，则其值默认为 0

说明：
最初栈中没有元素，为空栈，此时 tt == 0 。
本模板中，舍弃下标为 0 的数组元素，让栈底从下标 1 开始

2. 入栈 ( push )

tt++;
stk[tt] = x;
//stk[ ++t ] = x; // 在栈顶增加一个元素

{:height=”40%” width=”40%”}

tt 的含义

在本模板中，tt 的值为栈顶元素的下标，
因此在新元素入栈时，要先执行 tt++ ，让 tt 移动到新的栈顶，再加入新元素，
此时 tt 仍然为栈顶元素的下标。

3. 栈顶元素

stk[tt]; // tt 的值为栈顶元素的下标

4. 出栈 ( pop )

tt--; // 直接删除栈顶元素 

{:height=”50%” width=”50%”}

说明：
栈中原有的值仍暂时保存在数组 stk 中，
但若又有新的元素入栈，则新元素的数值会直接覆盖原有的数，
因此不用处理出栈后留下的数值。

5. 判断栈是否为空

if( tt > 0 ) not empty
else empty

tt 的引申含义：

当栈为空栈（ 栈中没有元素 ），此时 tt == 0
当有新元素入栈，此时tt == 1（栈中有 1 个元素）
又有新元素入栈，此时tt == 2（栈中有 2 个元素）
当有元素出栈，此时tt == 1（栈中有 1 个元素）
……

因此 tt 的值也等于栈中元素的个数

六、应用场景

用数组实现一个栈，并支持栈的基本操作。

题源： 828. 模拟栈 - AcWing题库

七、函数模板

#include<iostream>
using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int m;
    cin >> m;

    while( m-- )
    {
        int x; 
        string op;

        cin >> op;

        if( op == "push" ) // 入栈
        {
            cin >> x;
            stk[ ++tt ] = x; // 在栈顶增加一个元素
        }
        else if( op == "pop" ) // 出栈
        {
            tt--; // 删除栈顶元素
        }
        else if( op == "empty" ) // 判断栈是否为空
        {
            if( tt == 0 )
                cout << "YES" << endl;
            else cout << "NO" << endl; 
        }
        else if( op == "query" ) // 输出栈顶元素
        {
            cout << stk[tt] << endl;
        }
    } 
    return 0;
}

八、参考资料

1. y 总的课~~
2. 栈（计算机术语）_百度百科 (baidu.com)

九、( 无注释版 ) 函数模板

#include<iostream>
using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int m;
    cin >> m;

    while( m-- )
    {
        int x; 
        string op;

        cin >> op;

        if( op == "push" )
        {
            cin >> x;
            stk[ ++tt ] = x;
        }
        else if( op == "pop" ) tt--;
        else if( op == "empty" )
            if( tt == 0 )
                cout << "YES" << endl;
            else cout << "NO" << endl; 
        else if( op == "query" ) cout << stk[tt] << endl;
    } 
    return 0;
}

（接受批评指正，欢迎交流补充~~ XD）