基础数据结构第二期 栈（数组模拟栈+STL）

前言

栈的内容不算多，题目也就那几个，因此只需要掌握基本操作即可

一、栈的基本概念

（1）栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。

（2）操作：
入栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二、栈的例题及AC代码

例题：

AC代码：

数组模拟：

//*****************************栈
//int stk[N], tt;

//输入
//stk[++tt] = x;

//弹出
//tt--;

//判断栈是否为空
//if (tt > 0)not empty
//else empty

//栈顶
//stk[tt];



#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int stk[N], tt;

//向栈顶插入一个数x
void push(int x) {
	stk[++tt] = x;
}

//从栈顶弹出一个数x
void pop() {
	tt--;
}

//判断栈是否为空
void empty() {
	if (tt > 0)
		cout << "NO" << endl;
	else
		cout << "YES" << endl;
}

//查询栈顶元素
void query() {
	cout << stk[tt] << endl;
}
int main() {
	int m;
	cin >> m;
	string op;
	while (m--) {
		cin >> op;
		if (op == "push") {
			int x;
			cin >> x;
			push(x);
		} else if (op == "pop") {
			pop();
		} else if (op == "empty") {
			empty();
		} else if (op == "query") {
			query();
		}
	}
	return 0;
}

STL：

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

stack<int>s;
int top,m,x;
int main()
{
	cin>>m;
	string a;
	while(m--){
	    cin>>a;
		if(a=="push"){
			cin>>x;
			s.push(x);
		}
		else if(a=="pop"){
			s.pop();
		}
		else if(a=="empty")
	    cout<<(s.empty()?"YES":"NO")<<endl;
		else cout<<s.top()<<endl;
	}
	return 0;
}

总结

该部分较为简单，也相对比较好理解，感谢大家的观看，谢谢大家！！！