C++_STL_数据结构_stack_栈

清疚 2022-07-15 07:55 147阅读 0赞

栈（statck）这种[数据结构][Link 1]在计算机中是相当出名的。栈中的数据是先进后出的（First In Last Out, FILO）。栈只有一个出口，允许新增元素（只能在栈顶上增加）、移出元素（只能移出栈顶元素）、取得栈顶元素等操作。在STL中，栈是以别的容器作为底部结构，再将接口改变，使之符合栈的特性就可以了。因此实现非常的方便。下面就给出栈的函数列表和VS2008中栈的源代码，在STL中栈一共就5个常用操作函数（top()、push()、pop()、 size()、empty() ），很好记的。

![0_13208010984xk4.gif][]

**VS2008中栈的源代码**

友情提示：初次阅读时请注意其实现思想，不要在细节上浪费过多的时间。

**\[cpp\]** [view plain][] [copy][view plain]

1.  //VS2008中 stack的定义 MoreWindows整理(http://blog.csdn.net/MoreWindows)
2.  **template**<**class** \_Ty, **class** \_Container = deque<\_Ty> > 
3.  **class** stack 
4.  \{ // LIFO queue implemented with a container
5.  **public**: 
6.  **typedef** \_Container container\_type; 
7.  **typedef****typename** \_Container::value\_type value\_type; 
8.  **typedef****typename** \_Container::size\_type size\_type; 
9.  **typedef****typename** \_Container::reference reference; 
10. **typedef****typename** \_Container::const\_reference const\_reference; 
11. 
12.  stack() : c() 
13.  \{ // construct with empty container
14.  \} 
15. 
16. **explicit** stack(**const** \_Container& \_Cont) : c(\_Cont) 
17.  \{ // construct by copying specified container
18.  \} 
19. 
20. **bool** empty() **const**
21.  \{ // test if stack is empty
22. **return** (c.empty()); 
23.  \} 
24. 
25.  size\_type size() **const**
26.  \{ // test length of stack
27. **return** (c.size()); 
28.  \} 
29. 
30.  reference top() 
31.  \{ // return last element of mutable stack
32. **return** (c.back()); 
33.  \} 
34. 
35.  const\_reference top() **const**
36.  \{ // return last element of nonmutable stack
37. **return** (c.back()); 
38.  \} 
39. 
40. **void** push(**const** value\_type& \_Val) 
41.  \{ // insert element at end
42.  c.push\_back(\_Val); 
43.  \} 
44. 
45. **void** pop() 
46.  \{ // erase last element
47.  c.pop\_back(); 
48.  \} 
49. 
50. **const** \_Container& \_Get\_container() **const**
51.  \{ // get reference to container
52. **return** (c); 
53.  \} 
54. 
55. **protected**: 
56.  \_Container c; // the underlying container
57. \};

可以看出，由于栈只是进一步封装别的数据结构，并提供自己的接口，所以代码非常简洁，如果不指定容器，默认是用deque来作为其底层数据结构的（对deque不是很了解？可以参阅[《STL系列之一 deque双向队列》][STL_ deque]）。下面给出栈的使用范例：

**\[cpp\]** [view plain][] [copy][view plain]

1.  //栈 stack支持 empty() size() top() push() pop()
2.  // by MoreWindows(http://blog.csdn.net/MoreWindows)
3.  \#include <stack>
4.  \#include <vector>
5.  \#include <list>
6.  \#include <cstdio>
7.  **using****namespace** std; 
8.  **int** main() 
9.  \{ 
10. //可以使用list或vector作为栈的容器，默认是使用deque的。
11.  stack<**int**, list<**int**>> a; 
12.  stack<**int**, vector<**int**>> b; 
13. **int** i; 
14. 
15. //压入数据
16. **for** (i = 0; i < 10; i++) 
17.  \{ 
18.  a.push(i); 
19.  b.push(i); 
20.  \} 
21. 
22. //栈的大小
23.  printf("%d %d\\n", a.size(), b.size()); 
24. 
25. //取栈项数据并将数据弹出栈
26. **while** (!a.empty()) 
27.  \{ 
28.  printf("%d ", a.top()); 
29.  a.pop(); 
30.  \} 
31.  putchar('\\n'); 
32. 
33. **while** (!b.empty()) 
34.  \{ 
35.  printf("%d ", b.top()); 
36.  b.pop(); 
37.  \} 
38.  putchar('\\n'); 
39. **return** 0; 
40. \}

![save_snippets.png][]

[Link 1]: http://lib.csdn.net/base/datastructure
[0_13208010984xk4.gif]: /images/20220715/4a8ff2872ef34429990ad6ad4ce1fb64.png
[view plain]: http://blog.csdn.net/morewindows/article/details/6950881/#
[STL_ deque]: http://blog.csdn.net/morewindows/article/details/6946811
[save_snippets.png]: /images/20220715/2701619668d142418ec0a05bb0d8d9e1.png