c++-STL stack介绍与使用方法

stack(栈)

在学习数据结构中我们知道，栈是一种逻辑数据结构，其具有后进先出的特性。同时，我们也可以把它想象成一个容器，一个真实容器，添加与删除只能在容器顶部完成。栈的应用非常广，我们知道任何程序从内存进入CPU执行，系统为了保证程序正确的执行，将程序二进制代码存放在一个系统运行栈上面。调用函数A，则A的代码入栈，函数A中调用了函数B，则B入栈，B执行结束后，先出栈，这时再继续执行函数A。因此这种后进先出的工作方式在很多地方都非常有用。

stack内部数据结构可以是其它容器，因此可以看成是容器的容器。stack内部实现默认使用双端队列(deque)来实现，当然你也可以主动指定存储内省，如vector与list

构造函数

deque<int> mydeque(3, 100);
vector<int> myvector(2, 200);

stack<int> first;       //申明一个栈对象
stack<int> second(mydeque);    //用一个双端队列初始化一个栈对象，默认内部容器为deque
stack<int, vector<int> > third;   //表明third对象内部数据结构为vector
stack<int, vector<int> > fourth(myvector);  //用vector初始化fourth对象，必须要主动指定内部容器类型

常用函数

由于stack是一种操作受限制的线性结构，所有的操作只能是在栈顶，因此其内部函数也比较少。

deque<int> mydeque(3, 100);

stack<int> first(mydeque);

first.empty();   //判断是否为空
int size = first.size();  //返回栈内元素个数
int n;
n = first.top();   //返回栈顶元素
first.pop();   //弹出栈顶元素

first.push(20);   //向栈内添加元素

 

栈的应用非常广，常见的的图深度优先搜索、表达式求职、走迷宫的，下面是利用栈来完成走迷宫的源代码。

//走迷宫求解
#include <iostream>
#include <stack>

using namespace std;


class Position
{
public:
    int row;   //行
    int col;   //列
    int dir;   //默认为0。 1~4：该点到下一点的方向，分别为右上左下
};

//迷宫大小
#define MAZE_ROWS    3   
#define MAZE_COLS    4

//在迷宫外部加一堵墙
#define NEW_MAZE_ROWS (MAZE_ROWS + 2)
#define NEW_MAZE_COLS (MAZE_COLS + 2)

//起点
#define ENTER_ROW 1
#define ENTER_COL 1

//终点
#define EXIT_ROW    3
#define EXIT_COL    4

//保存路径的栈
stack<Position> mazeStack;   

//迷宫地图
int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS]
= {
    1, 1, 1, 1, 1, 1,
    1, 0, 1, 0, 0, 1,
    1, 0, 0, 0, 1, 1,
    1, 0, 1, 0, 0, 1,
    1, 1, 1, 1, 1, 1
};

//记录地图上的某个位置是否已经被访问过，为1表示访问过
int mazeFlag[NEW_MAZE_ROWS][NEW_MAZE_COLS];  

//判断某个点是否被访问过以及是否可通过
bool pass(Position pos)
{
    if (maze[pos.row][pos.col] == 0 &&
        mazeFlag[pos.row][pos.col] == 0)
    {
        return true;
    }

    return false;
}


//当前点cur的下一个点pos，同时更新当前点到下一个点的方向
//按照上、右、下、左的顺序依次获取当前点的下一个点
bool next_position(Position & cur, Position & nextpos)
{
    nextpos = cur;
    nextpos.dir = 0;    

    //根据当前点到下一个点的方向（目前的方向）
    //来确定下一个点的方向，如果当前点到下一个点的方向已经是4(左)
    //则表明当前点没有路径，不应该选择
    switch (cur.dir)
    {
        case 0:
            nextpos.row -= 1;
            cur.dir = 1;
            break;
        case 1:
            nextpos.col += 1;
            cur.dir = 2;
            break;
        case 2:
            nextpos.row += 1;
            cur.dir = 3;
            break;
        case 3:
            nextpos.col -= 1;
            cur.dir = 4;
            break;
        case 4:
            cur.dir = -1;
            return false;
            break;
        case -1:
            return false;
            break;
    }

    return true;
}


//判断是否
int maze_solution()
{
    //起点坐标为(1, 1)


    Position pos;
    pos.row = 1;
    pos.col = 1;
    pos.dir = 0;
    mazeStack.push(pos);   //起点如栈

    int totalSteps = 0;    //总共走的步数
    while (!mazeStack.empty())  //只要栈不为空，则继续寻找
    {

        Position curPos = mazeStack.top();   
        Position nextPos;

        //寻找下一个可达的点，同时更新当前位置的方向
        if (next_position(curPos, nextPos))
        {
            //更新当前位置方向
            mazeStack.pop();
            mazeStack.push(curPos);

            if (pass(nextPos))
            {
                mazeFlag[curPos.row][curPos.col] = 1;    //入栈之前标记为已访问
                mazeStack.push(nextPos);
                totalSteps++;

                if (nextPos.row == EXIT_ROW && nextPos.col == EXIT_COL)
                {
                    //成功找到出口，返回
                    return totalSteps;
                }
            }
        }
        else
        {
            mazeStack.pop();
            totalSteps--;
        }
    }

    return totalSteps;

}


int main()
{

    memset(mazeFlag, 0, sizeof(mazeFlag));

    stack<Position> tmpStack;
    int steps = maze_solution();
    if (steps > 0)
    {
        while (!mazeStack.empty())
        {
            tmpStack.push(mazeStack.top());
            mazeStack.pop();
        }

        cout << "the total steps: " << steps << endl;
        while (!tmpStack.empty())
        {
            cout << tmpStack.top().row << " " << tmpStack.top().col << endl;
            tmpStack.pop();
        }

    }
    else
    {
        cout << "can not find the path.." << endl;
    }



    return 0;
}