什么是数据？

在计算机系统中，各种字母、数字符号的组合、语音、图形、图像等统称为数据。

在计算机科学中，数据是指所有能输入到计算机并被计算机程序处理的符号总称。

什么是数据结构？

数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合

栈的定义

1、栈(Stack)是一种线性存储结构，它具有如下特点：

（1）栈中的数据元素遵守“先进后出”(First In Last Out)的原则，简称FILO结构。（后进先出的叫法，也是可以的）

（2）限定只能在栈顶进行插入和删除操作。

生活实例：

弹夹：第一个装进去的子弹，最后才被打出来。
洗碗：第一个摞起来的碗，最后才会被洗到。
羽毛球筒：最后放进去的球最先被取出。

栈的相关概念

（1）栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。

（2）压栈：栈的插入操作，叫做进栈，也称压栈、入栈。

（3）弹栈：栈的删除操作，也叫做出栈。

栈的操作与 C++实现

二、栈的操作与C++实现

在C++中，使用 #include<stack> 头文件来定义和操作栈。

3、栈的常用操作为：

（1）弹栈，通常命名为pop

（2）压栈，通常命名为push

（3）求栈的大小

（4）判断栈是否为空

（5）获取栈顶元素的值

操作功能	代码用法	说明	举例
定义栈	stack<数据类型> 栈名;	声明一个指定类型的栈	stack<string> s;
入栈	栈名.push(数据);	将数据压入栈顶（唯一有参数的操作）	s.push(“草莓”);
获取元素个数	栈名.size();	返回栈中当前元素的数量	s.size();
获取栈顶元素	栈名.top();	返回栈顶元素的值（不移除）	s.top();
出栈	栈名.pop();	移除栈顶元素（无返回值）	s.pop();
判断是否为空	栈名.empty();	栈为空返回1 (true)，否则返回0 (false)	s.empty();

⚠️ 注意事项：

只有 push 操作需要参数，其他操作均无参数。
对空栈进行 pop() 或 top() 操作会导致错误，操作前必须先用 empty() 判断。

#include<iostream>
#include<stack>
using namespace std;


int main(){
    stack<int> s;
    s.push(5);
    s.push(6);
    s.push(7);
    
    cout << s.size() << endl;
    cout << s.top() << endl;
    s.pop();
    cout << s.top() << endl;
    
    if(s.empty() != 0) cout << "不为空";
    return 0;
}

经典例题与应用场景

1. 判定问题：合法的出栈序列

题目类型：给定入栈顺序（如 1, 2, 3, 4），判断某出栈序列（如 3, 1, 2, 4）是否可能。
判定法则：

若元素 x 出栈，则比 x 小且尚未出栈的元素，必须以逆序出栈。

数组模拟栈

使用数组 stk[N] 和指针 tt。
初始化 tt = 0 （视具体实现而定，通常 top 指向栈顶元素）。
入栈：stk[++tt] = x;
出栈：tt--;

#include <iostream>
using namespace std;

const int N = 100010; // 栈的最大容量
int stk[N]; // 用数组存储栈元素
int tt = 0; // 栈顶指针，初始化为0（指向下一个要插入的位置）

// 压栈操作
void push(int x) {
    if (tt < N) {
        stk[++tt] = x; // 将x放入栈顶，栈顶指针+1
    }
}

// 弹栈操作
void pop() {
    if (tt > 0) {
        tt--; // 栈顶指针-1，相当于删除栈顶元素
    }
}

// 查询栈顶元素
int query() {
    return stk[tt]; // 返回栈顶元素（栈顶指针tt指向栈顶元素，所以栈顶元素在tt处）
}

// 判断栈是否为空
bool empty() {
    return tt == 0; // 栈顶指针为0表示栈空
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        string op;
        cin >> op;
        if (op == "push") {
            int x;
            cin >> x;
            push(x);
        } else if (op == "pop") {
            pop();
        } else if (op == "query") {
            cout << query() << endl;
        } else if (op == "empty") {
            if (empty()) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}