C++基础：STL之栈stack

这篇文章介绍一下STL中stack的基本使用方法。

---

栈stack

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

• 元素需满足FILO：First In Last Out

• 最后元素保存的位置称为栈顶（top），最早元素保存的位置称为栈底（bottom）

• 可以使用数组或者链表来存储数据

• 操作主要有压栈（push）和弹栈（pop）

• 只能在栈底进行数据插入数据和删除

• 关于栈的说明内容可参看：https://blog.csdn.net/liumiaocn/article/details/108091698

头文件和命名空间

#include <stack>
using namespace std;

常用的成员函数

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

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

stack vs vector

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

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

注：可以看到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的实现中也有很多限制，比如没有迭代器的支持等。