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

stack(栈)

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

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

构造函数
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
    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是一种操作受限制的线性结构,所有的操作只能是在栈顶,因此其内部函数也比较少。
```c
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); //向栈内添加元素
```

 

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

```c
//走迷宫求解
#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;
}
  • 版权声明: 本博客所有文章,未经许可,任何单位及个人不得做营利性使用!转载请标明出处!如有侵权请联系作者。
  • Copyrights © 2015-2020 翟天野

请我喝杯咖啡吧~