一、简介

       stack是一种容器适配器(STL的容器分为顺序容器和关联容器,容器适配器,是对这两类容器进行包装得到的具有更强的约束力的容器),被设计来用于操作先进后出(FILO)结构的情景,在这种情况下, 元素的插入和删除都只能在容器的尾部进行。

       stack通过容器适配器来实现,是一种将特定的容器类作为其最底层的容器的类,它提供了一些特定的成员函数来访问自己的元素,元素只能在这个特定容器的后面,也就是栈的顶部,进行出栈和入栈操作。

       最底层的容器可以是任意一种标准的容器模板类,或者是一些有明确目的的容器类,他们应该支持以下操作:

  1. empty判断是否为空
  2. size 返回栈的元素个数
  3. back 返回栈顶元素
  4. push_back 入栈
  5. pop_back (出栈
       标准的容器类,比如 vector,deque,list,满足以上需求。如果没有明确指定需要使用的容器,默认情况下将会使用 deque

二、函数用法示例

1、构造与析构(C++11版本)

[cpp]  view plain  copy
  1. initialize (1)          explicit stack (const container_type& ctnr);  
  2.   
  3. move-initialize (2)     explicit stack (container_type&& ctnr = container_type());  
  4.   
  5. allocator (3)           template <class Alloc> explicit stack (const Alloc& alloc);  
  6.   
  7. init + allocator (4)    template <class Alloc> stack (const container_type& ctnr, const Alloc& alloc);  
  8.   
  9. move-init + allocator (5)  template <class Alloc> stack (container_type&& ctnr, const Alloc& alloc);  
  10.   
  11. copy + allocator (6)    template <class Alloc> stack (const stack& x, const Alloc& alloc);  
  12.   
  13. move + allocator (7)    template <class Alloc> stack (stack&& x, const Alloc& alloc);  
(1)初始化构造方式
         构造一个内部元素都是ctnr的拷贝的容器适配器

(2)move-initialization constructor
        构造一个内部元素都是通过移动方式获得ctnr的值的容器适配器

剩下几个带分配器的我还没有看懂,就不乱说了
cplusplus的例子:
[cpp]  view plain  copy
  1. // constructing stacks  
  2. #include <iostream>       // std::cout  
  3. #include <stack>          // std::stack  
  4. #include <vector>         // std::vector  
  5. #include <deque>          // std::deque  
  6.   
  7. int main ()  
  8. {  
  9.   std::deque<int> mydeque (3,100);          // deque with 3 elements  
  10.   std::vector<int> myvector (2,200);        // vector with 2 elements  
  11.   
  12.   std::stack<int> first;                    // empty stack  
  13.   std::stack<int> second (mydeque);         // stack initialized to copy of deque  
  14.   
  15.   std::stack<int,std::vector<int> > third;  // empty stack using vector  
  16.   std::stack<int,std::vector<int> > fourth (myvector);  
  17.   
  18.   std::cout << "size of first: " << first.size() << '\n';  
  19.   std::cout << "size of second: " << second.size() << '\n';  
  20.   std::cout << "size of third: " << third.size() << '\n';  
  21.   std::cout << "size of fourth: " << fourth.size() << '\n';  
  22.   
  23.   return 0;  
  24. }  


2、empty()

返回当前栈是否为空(当它的大小是0的时候),empty()函数并不能清空栈,只是一个返回bool型的const函数

[cpp]  view plain  copy
  1.     stack<int>s;  
  2.     s.push(1);  
  3.     s.push(2);  
  4.     cout << s.empty() << endl;   //输出0  

3、size()

返回容器中元素的个数,时间复杂度O(1),返回值类型是size_type,也就是unsigned intsize()函数不能改变栈的大小

例如上面的代码段应该输出 2

4、top()

返回栈顶元素的引用。
由于栈是一种先进后出的结构,所以最顶部的元素就是最后插入栈的元素。
C++11中会自动根据元素类型返回reference或者是const_reference,对一个空的栈调用top函数,会异常终止,所以应该使用empty()函数提前检查)
[cpp]  view plain  copy
  1. stack<int>s;  
  2. s.push(1);  
  3. s.push(2);  
  4. cout << s.top() << endl;    //输出2  
  5. s.top() += 3;               //引用可以作为左值  
  6. cout << s.top() << endl;    //输出5  

5、push() 和 emplace() (C++11)

push()函数和 emplace()都是在栈这个容器的顶部插入一个新的元素。
push(),实际上是调用的底层容器的 push_back()函数,新元素的值是 push函数参数的一个拷贝。
emplace(),实际上是调用的底层容器的 emplace_back()函数,新元素的值是在容器内部就地构造的,不需要移动或者拷贝。
stackemplace也可以用在普通的基本类型上。
[cpp]  view plain  copy
  1. struct Node  
  2. {  
  3.     Node(int x)  
  4.         :x(x){}  
  5.     int x;  
  6. };  
  7.   
  8. int main()  
  9. {  
  10.     stack<Node>s1;  
  11.     s1.emplace(1);  
  12.     s1.push(Node(2));  
  13.   
  14.     stack<int>s2;  
  15.     s2.emplace(1);   //OK  
  16.     return 0;  
  17. }  

6、pop()

删除最顶部的元素,使栈的大小减小

这个被删除的元素,是刚刚插入栈的元素,这个元素和top函数的返回值是一致的。这个函数会调用对象的析构函数(如果有的话),pop()实际上是用过底层容器的pop_back()函数实现的。

对一个空栈进行pop(),会导致程序异常终止,应该使用empty提前检查

[cpp]  view plain  copy
  1. stack<int>s;  
  2. s.push(1);  
  3. s.push(2);  
  4. s.push(3);  
  5.   
  6. cout << s.top() << endl;   //3  
  7. s.pop();  
  8. cout << s.top() << endl;   //2  

栈没有clear或者erase函数,如果想要清空一个栈,需要循环的调用出栈函数。

[cpp]  view plain  copy
  1. stack<int>s;  
  2. //s.erase(); //error  
  3. //s.clear(); //error  
  4. s.push(1);  
  5. s.push(2);  
  6. s.push(3);  
  7. cout << s.size() << endl;   //3  
  8. while(!s.empty())  
  9.     s.pop();  
  10. cout << s.size() << endl;    //0  

7、swap()

交换两个栈的内容(所有元素),这个函数通过非成员函数swap()来交换底层容器,时间复杂度O(1)

cplusplus的例子

[cpp]  view plain  copy
  1. // stack::swap  
  2. #include <iostream>       // std::cout  
  3. #include <stack>          // std::stack  
  4.   
  5. int main ()  
  6. {  
  7.   std::stack<int> foo,bar;  
  8.   foo.push (10); foo.push(20); foo.push(30);  
  9.   bar.push (111); bar.push(222);  
  10.   
  11.   foo.swap(bar);  
  12.   
  13.   std::cout << "size of foo: " << foo.size() << '\n';  
  14.   std::cout << "size of bar: " << bar.size() << '\n';  
  15.   
  16.   return 0;  
  17. }  

8、运算符重载

[cpp]  view plain  copy
  1. (1)==用于比较两个栈是否相等,首先判断大小是否相等,然后再通过operator ==判断元素之间是否相等,将会在第一个不相等的地方停止  
  2.   
  3. template <class T, class Container>  
  4.   bool operator== (const stack<T,Container>& lhs, const stack<T,Container>& rhs);  
  5. (2)!= 和==是相反的。只要大小不同或者有一个元素不一样就是不相等的    
  6.       
  7.   
  8.     template <class T, class Container>  
  9.   
  10.       bool operator!= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);  
  11.   
  12.       
  13.   
  14.     (3)从第一元素开始比较当发现大于或者等于时停止,如果一个栈是另一个栈的前缀,那么长的栈大。下同   
  15.   
  16.       
  17.   
  18.     template <class T, class Container>  
  19.   
  20.       bool operator<  (const stack<T,Container>& lhs, const stack<T,Container>& rhs);  
  21.   
  22.       
  23.   
  24.     (4)      
  25.   
  26.       
  27.   
  28.     template <class T, class Container>  
  29.   
  30.       bool operator<= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);  
  31.   
  32.       
  33.   
  34.     (5)      
  35.   
  36.       
  37.   
  38.     template <class T, class Container>  
  39.   
  40.       bool operator>  (const stack<T,Container>& lhs, const stack<T,Container>& rhs);  
  41.   
  42.       
  43.   
  44.     (6)      
  45.   
  46.       
  47.   
  48.     template <class T, class Container>  
  49.   
  50.       bool operator>= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);  
  51.   
  52.       
[cpp]  view plain  copy
  1.     stack<int>l1;  
  2.     l1.emplace(1);  
  3.     l1.emplace(2);  
  4.     l1.emplace(3);  
  5.     stack<int>l2;  
  6.     l2.emplace(1);  
  7.     l2.emplace(2);  
  8.     cout << boolalpha << (l1 > l2) << endl;   //T  
  9.     cout << boolalpha << (l1 == l2) << endl;   //F  
  10.     cout << boolalpha << (l1 != l2) << endl;   //T  

四、结语

栈是一种特别常用的数据结构,在各种编程语言或者是操作系统内部,都能见到。常见的DFS算法,递归算法;上下文切换,进程调度,以及寄存器本身。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐