C++基础：STL之栈stack

一时失言乱红尘 2022-12-18 02:56 192阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
这篇文章介绍一下STL中stack的基本使用方法。

### 目录 ###

*  栈stack
 *  头文件和命名空间
 *  常用的成员函数
 *  stack vs vector
 *  代码使用示例
 *  示例执行结果
 *  总结

--------------------

# 栈stack #

栈也是最为常见的一种数据结构，队列中的元素满足FILO（先进后出）

*  元素需满足FILO：First In Last Out
 *  最后元素保存的位置称为栈顶（top），最早元素保存的位置称为栈底（bottom）
 *  可以使用数组或者链表来存储数据
 *  操作主要有压栈（push）和弹栈（pop）
 *  只能在栈底进行数据插入数据和删除
 *  关于栈的说明内容可参看：[https://blog.csdn.net/liumiaocn/article/details/108091698][https_blog.csdn.net_liumiaocn_article_details_108091698]

# 头文件和命名空间 #

> \#include <stack>  
> using namespace std;

# 常用的成员函数 #

<table> 
 <thead> 
  <tr> 
   <th>stack函数名</th> 
   <th>用途</th> 
   <th>功能说明</th> 
   <th>时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size()</td> 
   <td>查询遍历</td> 
   <td>获取元素个数</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>top()</td> 
   <td>查询遍历</td> 
   <td>获取指向第一个元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>push</td> 
   <td>插入</td> 
   <td>在末尾插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop</td> 
   <td>删除</td> 
   <td>删除最后一个元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>删除</td> 
   <td>删除所有元素</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

> 注：stack的成员函数主要包括插入和删除，实际对应着栈操作的入栈和出栈两个操作，然后就是获取元素个数和栈定元素的操作，都是负载度为O (1)的操作。

# stack vs vector #

本身实际上没有什么可比较的地方的，但是关于相类似的成员函数vector的如下所示

<table> 
 <thead> 
  <tr> 
   <th>stack函数名</th> 
   <th>vector函数名</th> 
   <th>用途</th> 
   <th>功能说明</th> 
   <th>时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size()</td> 
   <td>size()</td> 
   <td>查询遍历</td> 
   <td>获取元素个数</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>top()</td> 
   <td>begin()</td> 
   <td>查询遍历</td> 
   <td>获取指向第一个元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>-</td> 
   <td>end()</td> 
   <td>查询遍历</td> 
   <td>获取末尾的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>-</td> 
   <td>insert(position,x)</td> 
   <td>插入</td> 
   <td>在position位置插入数据x</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>-</td> 
   <td>erase(position)</td> 
   <td>删除</td> 
   <td>删除position位置上的元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>push</td> 
   <td>push_back(x)</td> 
   <td>插入</td> 
   <td>在末尾插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop</td> 
   <td>pop_back()</td> 
   <td>删除</td> 
   <td>删除最后一个元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>clear()</td> 
   <td>删除</td> 
   <td>删除所有元素</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

> 注：可以看到vector基本上包含所有的stack的操作，实际上也非常容易理解，使用数组将一端固定，只从另外一端插入删除就是栈的实现，所以可以看到栈是没有在指定位置执行插入和删除的操作的，因为实现完毕之后就是vector了。

--------------------

# 代码使用示例 #

#include <iostream>
    #include <stack>
    using namespace std;
    
    void print_top_element(stack <char> s) {
        if (!s.empty()) {
            cout << "Size:" << s.size() << " Stack Top Element : " << s.top() << endl;
        } else {
            cout << "Size:" << s.size() << endl;
        }
    }
    
    int main() {
        stack <char> s;
    
        cout << "Stack Element In " << endl;
        print_top_element(s);
        s.push('L');
        print_top_element(s);
        s.push('i');
        print_top_element(s);
        s.push('u');
        print_top_element(s);
    
        cout << endl << "Stack Element Out " << endl;
        s.pop();
        print_top_element(s);
        s.pop();
        print_top_element(s);
    }

# 示例执行结果 #

Stack Element In 
    Size:0
    Size:1 Stack Top Element : L
    Size:2 Stack Top Element : i
    Size:3 Stack Top Element : u
    
    Stack Element Out 
    Size:2 Stack Top Element : i
    Size:1 Stack Top Element : L
    
    Process finished with exit code 0

# 总结 #

变长支持、泛化类型、常用功能函数内嵌、可以使用其他多种STL的函数、使用简单等，都是stack被使用的原因，但是栈本身是一种非常简单的数据结构，在STL的实现中也有很多限制，比如没有迭代器的支持等。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/60e49f4d2984433f9b8476b031f47aa7.png
[https_blog.csdn.net_liumiaocn_article_details_108091698]: https://blog.csdn.net/liumiaocn/article/details/108091698