C++ - STL中的stack

stack介绍

stack模板类的定义在<stack>头文件中。栈是一种容器适配器，特别为后入先出而（LIFO ）设计的一种数据结构

2-1P913101Q4T2.jpg

栈有两个参数。

template < class T, class Container = deque<T> > class stack;

参数：

• T: 元素类型
• Container: 被用于存储和访问元素的的类型

栈实现了容器适配器，这是用了一个封装了的类作为它的特定容器，提供了一组成员函数去访问他的元素，元素从栈的尾部插入和取出元素。基础的容器可能是任何标准的容器类，和一些其他特殊设计的模板类一样，必须提供一些基本的操作，如下

back() 
push_back() 
pop_back()

标准的容器类模板vector, deque 和list都满足这些要求，所以都可以使用，默认情况下，如果没有容器类被指定成为一个提别的stack类，标准的容器类模板就是deque队列。stack类定义如下：

namespace std
{
template <class T, class Container = deque<T>>
class stack
{
public:
    typedef Container                                container_type;
    typedef typename container_type::value_type      value_type;
    typedef typename container_type::reference       reference;
    typedef typename container_type::const_reference const_reference;
    typedef typename container_type::size_type       size_type;

protected:
    container_type c;

public:
    stack() = default;
    ~stack() = default;

    stack(const stack& q) = default;
    stack(stack&& q) = default;

    stack& operator=(const stack& q) = default;
    stack& operator=(stack&& q) = default;

    explicit stack(const container_type& c);
    explicit stack(container_type&& c);
    template <class Alloc> explicit stack(const Alloc& a);
    template <class Alloc> stack(const container_type& c, const Alloc& a);
    template <class Alloc> stack(container_type&& c, const Alloc& a);
    template <class Alloc> stack(const stack& c, const Alloc& a);
    template <class Alloc> stack(stack&& c, const Alloc& a);

    bool empty() const;
    size_type size() const;
    reference top();
    const_reference top() const;

    void push(const value_type& x);
    void push(value_type&& x);
    template <class... Args> reference emplace(Args&&... args); // reference in C++17
    void pop();

    void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>)
};

成员函数

• 构造函数

stack() = default; //  默认构造函数
stack(const stack& q) = default; // 默认复制构造函数
stack(stack&& q) = default;

explicit stack(const container_type& c); // Copy-constructs
explicit stack(container_type&& c);  // Move-constructs the underlying container c with std::move(cont)

 // Constructs the underlying container using alloc as allocator, as if by c(alloc).
template <class Alloc> explicit stack(const Alloc& a);
template <class Alloc> stack(const container_type& c, const Alloc& a);
template <class Alloc> stack(container_type&& c, const Alloc& a);
template <class Alloc> stack(const stack& c, const Alloc& a);
template <class Alloc> stack(stack&& c, const Alloc& a);

简单使用

#include <stack>
#include <deque>
#include <iostream>
 
int main()
{
    std::stack<int> c1;
    c1.push(5);
    std::cout << c1.size() << '\n';
 
    std::stack<int> c2(c1);
    std::cout << c2.size() << '\n';
 
    std::deque<int> deq {3, 1, 4, 1, 5};
    std::stack<int> c3(deq);
    std::cout << c3.size() << '\n';
}

输出

1
1
5

也可以提供提前声明使用命名空间std

#include <stack>
#include <deque>
#include <iostream>
using namespace std;
 
int main()
{
    stack<int> c1;
    c1.push(5);
    cout << c1.size() << '\n';
 
    stack<int> c2(c1);
    cout << c2.size() << '\n';
 
    deque<int> deq {3, 1, 4, 1, 5};
    stack<int> c3(deq);
    cout << c3.size() << '\n';
}

• 访问元素

std::stack<T,Container>::top

reference top(); // 顶元素
const_reference top() const;

bool empty() const; // 是否为空
size_type size() const; // 容器元素的个数

使用top()函数返回栈顶的元素，也可以理解为最近push的元素

#include <stack>
#include <iostream>
 
int main()
{
    std::stack<int>   s;
 
    s.push( 2 );
    s.push( 6 );
    s.push( 51 );

    std::cout << "empty: " << s.empty() << "\n";
    std::cout << s.size() << " elements on stack\n";
    std::cout << "Top element: "
          << s.top()         // Leaves element on stack
          << "\n";
    std::cout << s.size() << " elements on stack\n";
    s.pop();
    std::cout << s.size() << " elements on stack\n";
    std::cout << "Top element: " << s.top() << "\n";
 
    return 0;
}

运行输出

empty: 0
3 elements on stack
Top element: 51
3 elements on stack
2 elements on stack
Top element: 6

• 修改容器元素

void push(const value_type& x); // 入栈元素
void push(value_type&& x);

// This function is used to insert a new element into the stack container
// the new element is added on top of the stack.
template <class... Args> reference emplace(Args&&... args); // reference in C++17
void pop(); // 去除栈顶元素

void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>)

简单使用push和pop

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

int main(int argc, const char * argv[]) {
    stack<int> mystack;

    for (int i=0; i<5; ++i) mystack.push(i);

    cout<<"pop element:"<<endl;
    while (!mystack.empty())
    {
        cout << " " << mystack.top();
        mystack.pop();
    }
    cout << endl;

    return 0;
}

运行输出

pop element:
 4 3 2 1 0

使用emplace插入元素

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

int main() {
    stack<int> mystack;
    mystack.emplace(1);
    mystack.emplace(2);
    mystack.emplace(3);
    mystack.emplace(4);
    mystack.emplace(5);
    mystack.emplace(6);
    // stack becomes 1, 2, 3, 4, 5, 6

    // printing the stack
    cout << "mystack = ";
    while (!mystack.empty()) {
        cout << mystack.top() << " ";
        mystack.pop();
    }
    return 0;
} 

运行输出

mystack = 6 5 4 3 2 1

• 交换stack容器元素

// This function is used to swap the contents of one stack with another stack of same type and size.
void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>)

简单使用

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

int main()
{
    // stack container declaration
    stack<int> mystack1;
    stack<int> mystack2;

    // pushing elements into first stack
    mystack1.push(1);
    mystack1.push(2);
    mystack1.push(3);
    mystack1.push(4);

    // pushing elements into 2nd stack
    mystack2.push(3);
    mystack2.push(5);
    mystack2.push(7);
    mystack2.push(9);

    // using swap() function to swap elements of stacks
    mystack1.swap(mystack2);

    // printing the first stack
    cout<<"mystack1 = ";
    while (!mystack1.empty()) {
        cout<<mystack1.top()<<" ";
        mystack1.pop();
    }

    // printing the second stack
    cout<<endl<<"mystack2 = ";
    while (!mystack2.empty()) {
        cout<<mystack2.top()<<" ";
        mystack2.pop();
    }
    return 0;
}

运行输出

mystack1 = 9 7 5 3 
mystack2 = 4 3 2 1 

使用场景

• 删除指定位置元素

#include <iostream>
#include <stack>

using namespace std;

// Deletes middle of stack of size
// n. Curr is current item number
void deleteMid(stack<char> &st, int n,
               int curr=0)
{
    // If stack is empty or all items
    // are traversed
    if (st.empty() || curr == n)
        return;

    // Remove current item
    int x = st.top();
    st.pop();

    // Remove other items
    deleteMid(st, n, curr+1);

    // Put all items back except middle
    if (curr != (n - 1))
        st.push(x);
}

//Driver function to test above functions
int main()
{
    stack<char> st;

    //push elements into the stack
    st.push('1');
    st.push('2');
    st.push('3');
    st.push('4');
    st.push('5');
    st.push('6');
    st.push('7');

    deleteMid(st, 4);

    // Printing stack after deletion
    // of middle.
    while (!st.empty())
    {
        char p=st.top();
        st.pop();
        cout << p << " ";
    }
    return 0;
}

运行输出

7 6 5 3 2 1

更多内容可以参考stack-data-structure

参考

stack