栈与队列

栈(stack)是一种特殊的线性表，只能从一端进行插入或者删除操作。这一端被称为栈顶，另一端被称为栈底，栈的特点是后进先出（Last In First Out）

栈操作

stack<int> sta;//定义一个栈

sta.push(x);//向栈顶放入一个 x

cout<<sta.top();//查看栈顶

sta.pop();//丢出栈顶

cout<<sta.size();//查看栈的大小

cout<<sta.empty();//查看栈是否为空

//以上操作复杂度均为O(1)

使用数组模拟栈

int sta[1000],int top=0;

sta[++top]=x;//入栈

cout<<sta[top];//查看栈顶
z
top--;//出栈

cout<<top;//查看栈的大小
//以上操作复杂度均为O(1)

习题：

B.小鱼的数字

C.括号匹配问题

队列

queue

和栈不同，队列是只能从一端进入，从另一端出去的数据结构

队列操作

queue<int> que;//定义一个存储int类型的队列 名字叫 que

que.push(x);//在队列中加入一个数字

que.front();//返回队列最前面的数字

que.pop();//丢掉队列最前面的数字

que.size();//返回队列里的大小

que.empty();//返回布尔值，是否为空
//以上操作复杂度均为O(1)

除了只有一端能进入，一端能出去的队列，还有两端都能进出的队列

双端队列

deque

deque<int> dq;//定义

dq.push_back(x);//在队尾操作
dq.pop_back();

dq.push_front(x);//在队首操作
dq.pop_front();

dq.size();//查询队列大小
dq.empty();
//以上操作复杂度均为O(1)

习题

D.周末舞会

E.约瑟夫问题

优先队列

priority_queue

优先队列是一种特殊的队列，它的本质是一个大顶堆

priority_queue<int> que;

que.push(x);

que.top();
que.pop();

que.size();

习题

F.合并果子