栈和队列

这是给协会上课介绍栈和队列时用的课件,简单介绍了栈和队列这两种数据结构,并列出了一些STL中stack和queue的一些用法。

1. stack栈

1.1 举个栗子

栈^1
桶里面有三个球,从下往上分别是3 1 2,那我们想要取出2,需要先取出3,再取出1,最后才能取出2
这体现了的特点FILO(First in Last Out)(先进后出)

1.2 生活中的例子

  1. 吃饭的时候要把碗上层的饭吃掉或者扒开,才能吃碗底部的饭。
  2. 浏览网页的时候,需要退回到之前某个网页,需要一步步地点击后退键。
  3. 装填手枪弹夹,最后装入得那颗子弹,是第一颗打出去的。

1.3 最基本的操作

PUSH:压栈、进栈……
POP:弹栈,出栈……
TOP:取栈顶元素

1.4 栈的实现

  1. 数组模拟
    数组模拟栈

    1
    2
    3
     // 入栈
    stack[top]=data;
    top++;
    1
    2
    // 出栈
    top--;
    1
    2
    //取栈顶元素
    Request = stack[top];
  2. STL中的stack容器

成员函数 功能
empty Test whether container is empty (public member function )
size Return size (public member function )
top Access next element (public member function )
push Insert element (public member function )
emplace Construct and insert element (public member function )
pop Remove top element (public member function )
swap Swap contents (public member function )

详细用法参考:cplusplus stack

1.5 举个例子

例题
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stack>
#include <string>
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
int n;
cin >> n;
while(n--)
{
string s;
cin >> s;
stack<char> st;
bool ok = true;
for(int i = 0;i < s.size();i++)
{
if(s[i]=='('||s[i]=='[') st.push(s[i]);
else{
if(st.size()==0){
ok = false;
break;
}
if(s[i]==')'){
if(st.top()=='(') st.pop();
else ok = false;
}
if(s[i]==']'){
if(st.top()=='[') st.pop();
else ok = false;
}
}
}
if(st.size()!=0) ok=false;
ok?printf("Yes\n"):printf("No\n");
}
return 0;
}

1.6 更多练习

POJ 1363 Rails
POJ 1028 Web Navigation
POJ 1686 Lazy Math Instructor
有关递归的问题例如:深度优先搜索(DFS) and so on…
Hdu 1241

1.7 一些注意点

  1. 对于多组样例的题目,每组样例注意在使用前先清空栈,防止上一组样例对本次造成影响。
    STL里的stack没有clear方法,,所以清空方法如下:
    1
    2
    3
    4
    while(!st.empty())
    {
    st.pop();
    }

或者把stack声明在循环体内部。

1.8 计算机中的栈

C编译器处理函数的时候,就是使用栈来保存数据的。当函数调用另一个函数时,C编译器将主调函数的所有实参和放回地址压入栈当中,栈指针将移动到合适的位置来容纳这些数据。
当进行被调函数时,编译器将栈中实参数据弹出,赋值给函数的形参。在被调用函数执行期间,还可以用栈来保存函数执行过程的局部变量。当被调用函数准备返回时,系统将弹出栈中所有当前函数压如栈中的值,这时,栈指针将移动到被调用函数刚开始执行时的位置。接着被调用函数返回,系统从栈中弹出返回地址,主函数就可以继续执行了。^2
函数调用
左图:函数1调用函数2
右图:函数2调用结束返回函数1

1.9 递归与堆栈

递归算法(自身不断调用自身)的程序代码更简洁清晰,可读性更好。但缺点是每次递归调用,需要将返回地址、参数等数据压入堆栈,也就是说,递归内部实现需要消耗额外的空间和时间。如果递归的层次太深,就可能导致堆栈溢出(stack overflow)(俗称的爆栈),从而使程序执行出错。
在OJ上通常的反馈就是
RE:Runtime Error
或者
MLE: Memory Limit Exceeded


2. queue队列

队列数据结构
解密规则:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数放到这串数的末尾,再将第5个数删除…… 直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一起就是小哈的QQ啦。

队列的特点:FIFO(First In First Out)先进先出。

2.1生活中的例子

普通队列

  1. 饭堂排队,先来的先打饭。
  2. 在独木桥上单方向行走,先上桥的先下桥。

优先队列

  1. 银行VIP来了优先服务。
  2. 军训期间,教官喊队伍里最高的同学出列。该同学出列后,教官喊剩下的同学里最高的同学出列,以此循环。

2.2最基本的操作

PUSH_BACK:入队
POP:出队
Front:取队头元素

2.3 队列的实现

  1. 数组模拟

数组模拟队列

1
2
3
//入队
queue[tail]=data;
tail++;

1
2
//出队
head++;
1
2
//判空
head==tail
  1. STL中的queue容器
成员函数 功能
empty Test whether container is empty (public member function )
size Return size (public member function )
front Access next element (public member function )
back Access last element (public member function )
push Insert element (public member function )
emplace Construct and insert element (public member function )
pop Remove next element (public member function )
swap Swap contents (public member function )

详细用法参考:cplusplus queue

2.4 举个例子

好像没有裸队列的题目,所以这里给一个基本的操作代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <queue>
using namespace std;

int main()
{
int a[5]={3,4,1,2,6};
queue<int> q;
for(int i = 0;i < 5;i++)
{
q.push(a[i]);
}
printf("size:%d\n",q.size());
while(!q.empty())
{
printf("%d ",q.front());
q.pop();
}
return 0;
}

2.5 更多练习

基础队列:
bfs相关题目。
HDU 1728 逃离迷宫
POJ 3278 Catch That Cow
HDU 1495 非常可乐

优先队列:
HDU 4006 The kth great number
HDU 1896 看病要排队

2.6 一些注意点

  1. 上面用数组模拟的队列,由于head和rail一直向后移动,所以占用的空间是非常大的。因此就有了循环队列
  2. 优先队列也常用语贪心算法当中。优先队列的优先级可以通过重载结构体的<运算符functional头文件中的greater/less自定义比较结构来实现。这里有一篇博文讲解。

参考资料