【C++ STL】详解栈(stack)、队列(queue)的使用和模拟_c++stl模拟栈和自带的栈

一、栈的介绍

  栈(stack)又称堆栈，是一种被限定仅在表尾进行插入和删除操作的线性表。
  对于栈来说，能进行插入和删除操作的一段称为栈顶(top)，另一端称为栈底(bottom)，且栈的修改操作是按照“后进先出”(Last In First Out, LIFO)的原则进行的。栈的示意图如下所示：

  与vector和list不同的是，stack是一种容器适配器。

二、栈的使用

2.1 stack的构造

  比较常用的有两种构造，一是构造空栈，二是用已经定义好的其他容器来构造。
stack的构造使用代码演示：

void TestStack1()
{
    deque<int> mydeque(3, 100);
    vector<int> myvector(2, 200);
    stack<int> first;                //空栈
    stack<int> second(mydeque);      //堆栈初始化为双端队列的副本

    stack<int, vector<int>> third;   //使用vector适配
    stack<int, vector<int>> fourth(myvector);
}
1
2
3
4
5
6
7
8
9
10

2.2 stack的修改

  栈的使用接口是非常少的，比较常用的是在栈顶push和pop。
stack的修改使用代码演示：

void TestStack2()
{
    stack<int> mystack;

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

    cout << "Popping out elements...";
    while (!mystack.empty())
    {
        cout << ' ' << mystack.top();
        mystack.pop();
    }
    cout << endl;;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行结果：

三、栈的模拟实现

  栈的模拟实现非常简单，它不需要写迭代器。

template<class T, class Con = deque<T>>
class stack
{
public:
    void push(const T& x)
    {
        _c.push_back(x);
    }

    void pop()
    {
        _c.pop_back();
    }

    T& top()
    {
        return _c.back();
    }

    const T& top() const
    {
        return _c.back();
    }

    size_t size() const
    {
        return _c.size();
    }

    bool empty() const
    {
        return _c.empty();
    }

private:
    Con _c;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

四、队列的介绍

  有了栈的介绍后，队列就很好理解了。它只允许在队尾插入，队头删除，即“先进先出”(First In First Out, FIFO)的原则，它的示意图如下所示：

五、队列的使用

5.1 队列的构造

void TestQueue1()
{
    deque<int> mydeck(3, 100);
    list<int> mylist(2, 200);

    queue<int> first;                           // 空队列
    queue<int> second(mydeck);       // 队列初始化为双端队列的副本

    queue<int, list<int>> third;         // 以链表作为基础容器的空队列
    queue<int, list<int>> fourth(mylist);
}
1
2
3
4
5
6
7
8
9
10
11

5.2 队列的修改

void TestQueue2()
{
    queue<int> myqueue;
    int myint;

    cout << "Please enter some integers (enter 0 to end):\n";

    do {
        cin >> myint;
        myqueue.push(myint);
    } while (myint);

    cout << "myqueue contains: ";
    while (!myqueue.empty())
    {
        cout << ' ' << myqueue.front();
        myqueue.pop();
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行结果：

六、队列的模拟实现

template<class T, class Con = deque<T>>
class queue
{
public:
    void push(const T& x)
    {
        _c.push_back(x);
    }

    void pop()
    {
        _c.pop_front();
    }

    T& back()
    {
        return _c.back();
    }

    const T& back() const
    {
        return _c.back();
    }

    T& front()
    {
        return _c.front();
    }

    const T& front() const
    {
        return _c.front();
    }

    size_t size() const
    {
        return _c.size();
    }

    bool empty() const
    {
        return _c.empty();
    }

private:
    Con _c;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

七、deque（双端队列）

  上面我们介绍了stack和queue两种容器适配器，他们的底层容器默认都是deque，那么deque到底是什么东西，下面我们简单了解一下。

7.1 deque的原理介绍

  deque是一种支持在序列的两端进行高效的插入和删除操作的容器，为了实现这一点，它在底层采用了分段存储的方式。下面是deque的底层结构示意图：

+---+    +---+    +---+    +---+    +---+
|   | -> | B | -> | C | -> | D | -> | E |
+---+    +---+    +---+    +---+    +---+
 map       |        |        |        |
           V        V        V        V
       +-------+ +-------+ +-------+ +-------+
       |  A0   | |  B0   | |  C0   | |  D0   |
       |  A1   | |  B1   | |  C1   | |  D1   |
       |  A2   | |  B2   | |  C2   | |  D2   |
       |  A3   | |  B3   | |  C3   | |  D3   |
       |  A4   | |  B4   | |  C4   | |  D4   |
       +-------+ +-------+ +-------+ +-------+

1
2
3
4
5
6
7
8
9
10
11
12
13

在这个示意图中：

• map：表示指针数组，其中每个元素指向一个缓冲区。
• 缓冲区（A、B、C、D）：每个缓冲区包含若干个元素（A0, A1, A2, …， B0, B1, …）。
• 指针：map中的每个指针指向相应的缓冲区。

7.2 deque的工作机制

• 插入和删除：
    deque允许在两端高效地进行插入和删除操作。当在前端插入元素时，如果前一个缓冲区已满，会分配一个新的缓冲区并更新map。在后端插入元素时，同样的机制适用。
• 访问元素：
    通过索引访问元素时，deque首先计算元素所在的缓冲区，然后访问缓冲区中的具体位置。这使得它能够在常数时间内访问任意元素。
• 内存管理：
    deque根据需要动态分配和释放缓冲区。内存管理由标准库处理，用户无需手动干预。

7.3 deque的优点和缺点

优点：

• 在两端的插入和删除操作都非常高效。
• 随机访问任意元素的时间复杂度为常数时间 O(1)。
  缺点
• 比单纯的动态数组或链表实现更为复杂。
• 内存使用可能比vector更多，因为它需要管理多个缓冲区。
    由此可知STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因为stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。