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 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#includeusing namespace std;

void print_top_element(stacks) {
    if (!s.empty()) {
        cout << "Size:" << s.size() << " Stack Top Element : " << s.top() << endl;
    } else {
        cout << "Size:" << s.size() << endl;
    }
}

int main() {
    stacks;

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