1. 1. stack栈
    1. 1.1 举个栗子
    2. 1.2 生活中的例子
    3. 1.3 最基本的操作
    4. 1.4 栈的实现
    5. 1.5 举个例子
    6. 1.6 更多练习
    7. 1.7 一些注意点
    8. 1.8 计算机中的栈
    9. 1.9 递归与堆栈
  2. 2. queue队列
    1. 2.1生活中的例子
    2. 2.2最基本的操作
    3. 2.3 队列的实现
    4. 2.4 举个例子
    5. 2.5 更多练习
    6. 2.6 一些注意点

这是给协会上课介绍栈和队列时用的课件，简单介绍了栈和队列这两种数据结构，并列出了一些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. 数组模拟
    数组模拟栈

           // 入栈
      stack[top]=data;
      top++;
       // 出栈
      top--;
      //取栈顶元素
  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 举个例子

例题
题目地址

#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方法，，所以清空方法如下：
    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. 数组模拟

数组模拟队列

//入队
queue[tail]=data;
tail++;
//出队
head++;
//判空
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 举个例子

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

#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，自定义比较结构来实现。这里有一篇博文讲解。

参考资料

除另有声明外，本博客文章均采用 知识共享(Creative Commons) 署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议 进行许可。