C++中的stack

在编程过程中，常常使用stack用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行出错。一般来说，程序的栈内存空间很小，对有些题目来说，如果用普通的函数来递归，一旦递归层数过深，则会导致程序运行崩溃。如果用栈来模拟递归算法的实现，则可以避免这一方面的问题。stack是一种先进后出的数据结构。要使用stack，必须包含头文件#include还有命名空间”using namespace std;”。

1、stack的定义:stack<typename> name;例如:

stack<int> name;

2、stack容器内元素的访问

#include<stdio.h>
#include<iostream>
#include<stack>
using namespace std;
int main(){
    stack<int> st;
    for(int i=1;i<=5;i++){
        st.push(i);//push(i)将i压入队列
    }
    cout<<st.top();//取栈顶元素
    return 0;
}

3、stack常用的函数

(1)push(x):将x进行入栈，时间复杂度为O(1)。
(2)pop():栈顶元素出栈，时间复杂度为O(1)。
(3)top():获得栈顶元素，时间复杂度为O(1)。
(4)empty():检测stack是否为空，时间复杂度为O(1)。
(5)size():返回stack内的元素个数，时间复杂度为O(1)。
(6)STL中没有实现栈的清空，如果需要实现栈的清空，可以用一个while循环反复pop出元素直到栈为空：
    while(!st.empty){
        st.pop();
    }