Section 10.栈和队列

一、基本概念

• 栈：先进后出。越后插入的元素，越先弹出来（有底的圆桶）
• 队列：先进先出。越先插入的元素，越先弹出来（无底的圆桶）

二、实现

• 栈：

#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt = 0;//初始化栈，tt是当前的下标

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

//弹出
tt--;

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

//栈顶
stk[tt];

• 队列

#include <iostream>
using namespace std;
const int N = 100010;
int q[N], hh = 0, tt = -1;  //hh表示队头，tt表示队尾

//在队尾插入x
q[++tt] = x;

//队头弹出
hh++;

//判断是否为空
if (hh <= tt)  //非空
else  //为空

//取出队头元素
q[hh];

三、配套练习

AcWing828

AcWing829