[C++知识库]C++用数组模拟栈结构(stack)

首先提出问题：为什么有STL不用，反而要自己用数组来模拟stack？

1.最致命的原因，99%的测评网站，竞赛系统不会对C++代码使用O2优化，导致使用STL的速度慢，容易造成TLE（超时）。

2.学习栈的操作流程和内部原理。

3.虽然咱们可以使用以下代码手动开启O2优化， 但是在竞赛中有被举报和取消成绩的风险。

#pragma GCC optimize(2)

创建数组栈

需要一个数组stk[N]，一个指针tt指向栈顶。

我们stk[0]不存放数据，可以将栈数组初始化。

int stk[N],tt = 0;

把数据x压入栈

void stkpush(int x)
{
    stk[++tt] = x;//++tt可保证从stk[1]开始压入数据并且tt指向栈顶
}

把栈顶数据弹出栈

void stkpop()
{
    tt--;//最后一个数据没有被销毁，但是已经“失效了”，下次压入栈会把失效数据覆盖
}

读取栈顶元素

int stktop()
{
    return stk[tt];//具体类型根据栈的数据类型确定
}

判断栈为空

bool stkempty()
{
    return tt == 0;
}

虽然这些操作都比较简单，但是单独写个函数来操作还是比较方便使用的，下面是完整示例代码。

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 1000010;
int stk[N],tt = 0;
void stkpush(int x)
{
    stk[++tt] = x;
}
void stkpop()
{
    tt--;
}
int stktop()
{
    return stk[tt];
}
bool stkempty()
{
    return tt == 0;
}
int main()
{
    char op;//表示操作数
    while(scanf("%c",&op))
    {
        if(op=='S')//停止操作，退出
            break;
        if(op=='P')//压入x元素
        {
            int x;
            scanf("%d",&x);
            stkpush(x);
        }
        if(op=='D')//弹出栈顶元素
        {
            if(!stkempty())stkpop();//若非空则弹出
            else printf("Empty!\n");
        }
        if(op=='T')//查询栈顶元素
        {
            if(!stkempty())printf("%d\n",stktop());
            else printf("Empty!\n");
        }
    }
    return 0;
}