stack介紹

stack模板類的定義在<stack>頭文件中。棧是一種容器適配器，特別為后入先出而（LIFO ）設(shè)計的一種數(shù)據(jù)結(jié)構(gòu)

2-1P913101Q4T2.jpg

棧有兩個參數(shù)。

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

參數(shù)：

• T: 元素類型
• Container: 被用于存儲和訪問元素的的類型

棧實現(xiàn)了容器適配器，這是用了一個封裝了的類作為它的特定容器，提供了一組成員函數(shù)去訪問他的元素，元素從棧的尾部插入和取出元素?；A(chǔ)的容器可能是任何標準的容器類，和一些其他特殊設(shè)計的模板類一樣，必須提供一些基本的操作，如下

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>)
};

成員函數(shù)

• 構(gòu)造函數(shù)

stack() = default; //  默認構(gòu)造函數(shù)
stack(const stack& q) = default; // 默認復制構(gòu)造函數(shù)
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; // 容器元素的個數(shù)

使用top()函數(shù)返回棧頂?shù)脑?，也可以理解為最?code>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

更多內(nèi)容可以參考stack-data-structure

參考

stack