C++中stack和queue的用法及說明

更新時間：2025年10月10日 10:10:36 作者：一只沒有感情的bug

這篇文章主要介紹了C++中stack和queue的用法及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

前言

在 C++ 中，stack（棧）和 queue（隊列）是兩種常用的容器適配器，分別用于管理數(shù)據(jù)的后進先出（LIFO）和先進先出（FIFO）訪問模式。

本文將詳細介紹這兩種數(shù)據(jù)結(jié)構(gòu)的基本概念、常見操作及其在 C++ 中的實現(xiàn)，并探討與其相關(guān)的設(shè)計模式。

1.stack的介紹和實現(xiàn)

1.1 Stack 的基本概念

Stack 是一種后進先出（LIFO, Last In First Out）的數(shù)據(jù)結(jié)構(gòu)。這意味著最新添加的元素最先被移除。

常見的操作包括：

函數(shù)說明	接口說明
stack()	構(gòu)造空的棧
empty()	檢測stack是否為空
size()	返回stack中元素的個數(shù)
top()	返回棧頂元素的引用
push()	將元素val壓入stack中
pop()	將stack中尾部的元素彈出

1.2 Stack 的模擬實現(xiàn)

以下是一個基于 C++ 模板的棧實現(xiàn)，默認情況下使用 deque 作為底層容器。通過模板參數(shù)，用戶可以指定其他支持相同操作的容器類型（如 vector）。

template <class T, class Container = deque<T>>	// 缺省值
class MyStack
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

	void pop()			// 不支持 第二個參數(shù)是vectot<T>的原因是它沒有pop_front(),但仍可以變向的實現(xiàn)
	{
		// 這樣就可以支持vector了，但效率就很低了
		// _con.erase(bebin());
		_con.pop_back();
	}

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

	bool empty()
	{
		return _con.empty();
	}

	size_t size()
	{
		return _con.size();
	}
private:
	Container _con;
};

1.3 自定義 Stack 的使用

#include "stack_queue.h"

int main()
{
	// 棧:
	cout << "STACK :" << endl;
	bit::MyStack <int, list<int >> st1;
	bit::MyStack <int, deque<int >> st2;

	st1.push(1);
	st1.push(2);
	st1.push(3);

	st2.push(4);
	st2.push(5);
	st2.push(6);

	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl;

	while (!st2.empty())
	{
		cout << st2.top() << " ";
		st2.pop();
	}
	cout << endl;

輸出：

STACK :
3 2 1
6 5 4

OJ上的使用

最小棧

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

棧的壓入、彈出序列

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        if (pushV.size() != popV.size()) return false;

        stack<int> stk;
        int popIndex = 0;

        for (int i = 0; i < pushV.size(); ++i) {
            stk.push(pushV[i]);

            while (!stk.empty() && stk.top() == popV[popIndex]) {
                stk.pop();
                ++popIndex;
            }
        }

        return stk.empty();
    }
};

逆波蘭表達式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (size_t i = 0; i < tokens.size(); ++i) {
            string& str = tokens[i];
            // str為數(shù)字
            if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
                s.push(atoi(str.c_str()));
            } else {
                // str為操作符
                int right = s.top();
                s.pop();
                int left = s.top();
                s.pop();
                switch (str[0]) {
                case '+':
                    s.push(left + right);
                    break;
                case '-':
                    s.push(left - right);
                    break;
                case '*':
                    s.push(left * right);
                    break;
                case '/':
                    // 題目說明了不存在除數(shù)為0的情況
                    s.push(left / right);
                    break;
                }
            }
        }
        return s.top();
    }
};

用兩個棧實現(xiàn)隊列

#include <stack>
using namespace std;

class MyQueue {
private:
    stack<int> A; // 棧 A，用于存儲新加入的元素
    stack<int> B; // 棧 B，用于反轉(zhuǎn) A 中的元素以實現(xiàn)隊列的 FIFO 特性

public:
    // 初始化數(shù)據(jù)結(jié)構(gòu) 
    MyQueue() {}

    // 將元素 x 推到隊列的末尾 
    void push(int x) {
        A.push(x); // 直接將元素壓入棧 A
    }

    // 從隊列前端移除元素并返回該元素 
    int pop() {
        int peek = this->peek(); // 獲取隊列前端的元素
        B.pop(); // 從棧 B 中移除該元素
        return peek; // 返回被移除的元素
    }

    // 獲取隊列前端的元素
    int peek() {
        // 如果棧 B 非空，直接返回棧 B 的棧頂元素
        if (!B.empty())
            return B.top();
        // 如果棧 A 也為空，返回 -1 表示隊列為空
        if (A.empty())
            return -1;
        // 將棧 A 中的所有元素移動到棧 B 中，以反轉(zhuǎn)元素順序
        while (!A.empty()) {
            B.push(A.top());
            A.pop();
        }
        // 返回棧 B 的棧頂元素，即隊列前端的元素
        return B.top();
    }

    // 返回隊列是否為空
    bool empty() {
        // 如果棧 A 和棧 B 都為空，表示隊列為空
        return A.empty() && B.empty();
    }
};

2.queue的介紹和實現(xiàn)

2.1 Queue 的基本概念

Queue 是一種先進先出（FIFO, First In First Out）的數(shù)據(jù)結(jié)構(gòu)。這意味著最先添加的元素最先被移除。

常見的操作包括：

函數(shù)聲明	接口說明
queue()	構(gòu)造空的隊列
empty()	檢測隊列是否為空，是返回true，否則返回false
size()	返回隊列中有效元素的個數(shù)
front()	返回隊頭元素的引用
back()	返回隊尾元素的引用
push()	在隊尾將元素val入隊列
pop()	將隊頭元素出隊列

2.2 Queue 的模擬實現(xiàn)

以下是一個基于 C++ 模板的隊列實現(xiàn)，默認情況下使用 deque 作為底層容器。通過模板參數(shù)，用戶可以指定其他支持相同操作的容器類型（如 list）。

// 隊列的實現(xiàn)：
template <class T, class Container = deque<T>>	// 缺省值
class MyQueue
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

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

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

	bool empty()
	{
		return _con.empty();
	}

	size_t size()
	{
		return _con.size();
	}

private:
	Container _con;
};

2.3 自定義 Queue 的使用

#include "stack_queue.h"

int main()
{
	// 隊列:
	cout << "QUEUE :" << endl;
	bit::MyQueue <int, list<int >> q1;
	bit::MyQueue <int, deque<int >> q2;

	q1.push(1);
	q1.push(2);
	q1.push(3);

	q2.push(4);
	q2.push(5);
	q2.push(6);

	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}

	cout << endl;

	while (!q2.empty())
	{
		cout << q2.front() << " ";
		q2.pop();
	}
	
	return 0;
}

輸出：

QUEUE :
1 2 3
4 5 6

OJ上的使用

用兩個隊列實現(xiàn)棧

#include <queue>
using namespace std;

class MyStack {
public:
    queue<int> queue1; // 主隊列，用于存儲棧中的元素
    queue<int> queue2; // 輔助隊列，用于幫助元素的重新排列

    // 初始化數(shù)據(jù)結(jié)構(gòu) 
    MyStack() {}

    // 將元素 x 壓入棧 
    void push(int x) {
        // 將新元素壓入輔助隊列
        queue2.push(x);
        // 將主隊列中的所有元素移到輔助隊列中
        while (!queue1.empty()) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        // 交換主隊列和輔助隊列
        swap(queue1, queue2);
    }

    // 移除并返回棧頂元素
    int pop() {
        int r = queue1.front(); // 獲取棧頂元素
        queue1.pop(); // 移除棧頂元素
        return r; // 返回棧頂元素
    }

    // 獲取棧頂元素
    int top() {
        return queue1.front(); // 返回棧頂元素
    }

    // 判斷棧是否為空 
    bool empty() {
        return queue1.empty(); // 返回主隊列是否為空
    }
};

3. 設(shè)計模式

設(shè)計模式

常見的設(shè)計模式共有 23 種。

適配器模式 -- 封裝轉(zhuǎn)換

適配器模式是一種結(jié)構(gòu)型設(shè)計模式，它允許接口不兼容的對象協(xié)同工作。
棧和隊列的實現(xiàn)正是通過適配器模式來封裝不同的底層容器（如 deque、vector 等），提供統(tǒng)一的接口。

迭代器模式 -- 統(tǒng)一訪問方式（數(shù)據(jù)結(jié)構(gòu)訪問都可以用）

迭代器模式是一種行為型設(shè)計模式，它提供一種方法順序訪問一個聚合對象中的各個元素，而不需要暴露該對象的內(nèi)部表示。
在棧和隊列的實現(xiàn)中，雖然沒有直接使用迭代器模式，但它們的底層容器（如 deque）本身支持迭代器，這使得我們可以通過迭代器訪問容器中的元素。

4.priority_queue的介紹和實現(xiàn)

通過對priority_queue的底層結(jié)構(gòu)就是堆，因此此處只需對對進行通用的封裝即可。

4.1 priority_queue的使用

使用priority_queue的關(guān)鍵點

默認大頂堆：priority_queue<int>，使用默認的 less<int> 比較函數(shù)，因此它是一個大頂堆。
小頂堆：priority_queue<int, vector<int>, greater<int>>，通過傳遞 greater<int> 作為比較函數(shù)，使其成為小頂堆。
需要指定容器類型：當(dāng)指定比較函數(shù)（如 greater<int> 或 less<int>）時，也必須顯式指定底層容器類型（通常是 vector<int>）。

4.1.1 C++ 標(biāo)準(zhǔn)庫中

代碼：

// 庫中優(yōu)先隊列的使用
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
	// 優(yōu)先隊列（堆）
	/*
	priority_queue<int> q1;
	for (auto e : v)
		q1.push(e);
	*/

	// priority_queue<int> q1(v.begin(), v.end());

	int a[] = { 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int, vector<int>, greater<int>> q1(a, a + sizeof(a) / sizeof(int));//小堆

	priority_queue<int, vector<int>, less<int>> q2(a, a + sizeof(a) / sizeof(int));//大堆

	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();// 刪除堆頂元素
	}
	cout << endl;
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();// 刪除堆頂元素
	}
	return 0;
}

輸出：

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

4.1.2 自定義優(yōu)先隊列

PriorityQueue.h

#pragma once
#include <vector>
#include <algorithm> // for std::swap

using namespace std;

namespace bit
{
    template<class T>
    struct myless
    {
        bool operator()(const T& x, const T& y) const
        {
            return x < y;
        }
    };

    template<class T>
    struct mygreater
    {
        bool operator()(const T& x, const T& y) const
        {
            return x > y;
        }
    };

    template<class T, class Container = vector<T>, class Compare = mygreater<T>>
    class priority_queue
    {
    public:

        priority_queue() = default;

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                _con.push_back(*first);
                ++first;
            }
            // 建堆
            for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
            {
                adjust_down(i);
            }
        }

        void adjust_up(int child)
        {
            Compare comfunc;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (comfunc(_con[child], _con[parent]))
                {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void push(const T& x)
        {
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }

        void adjust_down(int parent)
        {
            Compare comfunc;
            int size = _con.size();
            int child = 2 * parent + 1;
            while (child < size)
            {
                if (child + 1 < size && comfunc(_con[child + 1], _con[child]))
                {
                    child++;
                }
                if (comfunc(_con[child], _con[parent]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = 2 * parent + 1;
                }
                else
                {
                    break;
                }
            }
        }

        const T& top() const
        {
            return _con.front();
        }

        void pop()
        {
            if (!_con.empty())
            {
                swap(_con.front(), _con.back());
                _con.pop_back();
                if (!_con.empty())
                {
                    adjust_down(0);
                }
            }
        }

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

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

    private:
        Container _con;
    };
}

test.cpp

#include "PriorityQueue.h"

#include <iostream>
#include <queue>

using namespace std;

class Date
{
public:
	// 默認構(gòu)造函數(shù)，使用初始化列表初始化年、月、日
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year), _month(month), _day(day)
	{}

	// 重載小于運算符
	bool operator<(const Date& d) const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}

	// 重載大于運算符
	bool operator>(const Date& d) const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}

	// 重載等于運算符
	bool operator==(const Date& d) const
	{
		return _year == d._year && _month == d._month && _day == d._day;
	}

	// 重載不等于運算符
	bool operator!=(const Date& d) const
	{
		return !(*this == d);
	}

	// 輸出日期
	friend std::ostream& operator<<(std::ostream& os, const Date& d)
	{
		os << d._year << "-" << d._month << "-" << d._day;
		return os;
	}

private:
	int _year;
	int _month;
	int _day;
};

// 庫中的priority_queue使用
void TestPriorityQueue1()
{
	Date date1(2023, 6, 9);
	Date date2(2024, 1, 1);
	Date date3(2018, 9, 10);

	priority_queue<Date> q;// 默認大堆
	q.push(date1);
	q.push(date2);
	q.push(date3);

	while (!q.empty())
	{
		cout << q.top() << endl;
		q.pop();
	}

}

class PDateLess
{
public:
	bool operator()(Date* p1, Date* p2)
	{
		return *p1 < *p2;
	}
};

void TestPriorityQueue2()
{
	bit::priority_queue<Date*, vector<Date*>, PDateLess> q;
	q.push(new Date(2023, 6, 9));
	q.push(new Date(2024, 1, 1));
	q.push(new Date(2018, 9, 10));

	while (!q.empty())
	{
		cout << *q.top() << endl;
		q.pop();
	}

}

int main()
{
	// 大堆，需要用戶在自定義類型中提供比較的重載
	// priority_queue<Date*, vector<Date*>, PDateLess> q1;

	TestPriorityQueue1();
	cout << "-----------------------" << endl;
	TestPriorityQueue2();

	return 0;
}

輸出：

2024-1-1
2023-6-9
2018-9-10
-----------------------
2018-9-10
2023-6-9
2024-1-1

5. STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque，比如：

6. deque的簡單介紹

deque（雙端隊列）是一種雙開口的“連續(xù)”空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復(fù)雜度為 O(1)。

與 vector 比較，deque 在頭部插入時效率更高，因為不需要搬移元素；與 list 比較，deque 的空間利用率更高。

deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實際deque類似于一個動態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：

雙端隊列底層是一段假象的連續(xù)空間，實際是分段連續(xù)的，為了維護其“整體連續(xù)”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計就比較復(fù)雜，如下圖所示：

那deque是如何借助其迭代器維護其假想連續(xù)的結(jié)構(gòu)呢？

deque 的缺陷

deque 有一個致命缺陷：不適合遍歷，因為在遍歷時，deque 的迭代器要頻繁地檢測是否移動到某段小空間的邊界，導(dǎo)致效率低下。

而在序列式場景中，可能需要經(jīng)常遍歷。

因此在實際中，需要線性結(jié)構(gòu)時，大多數(shù)情況下優(yōu)先考慮 vector 和 list，deque 的應(yīng)用并不多。

而目前能看到的一個應(yīng)用就是，STL 用其作為 stack 和 queue 的底層數(shù)據(jù)結(jié)構(gòu)。

以下通過對大量數(shù)據(jù)排序來證明遍歷 queue 導(dǎo)致的效率很低

遍歷queue的性能比較

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	// vector與deque的性能對比（相同的結(jié)構(gòu)，相同的訪問）
	srand(time(0));
	deque<int> dq1;
	deque<int> dq2;

	int N = 1000000;

	for (int i = 0;i < N;++i)
	{
		auto e = rand() + i;
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	sort(dq1.begin(), dq1.end());
	int end1 = clock();

	int begin2 = clock();
	//拷貝到vector
	vector<int> v(dq1.begin(), dq1.end());
	sort(v.begin(), v.end());
	//拷貝回deque
	dq2.assign(v.begin(), v.end());	// 迭代區(qū)間賦值
	int end2 = clock();

	cout << "deque sort: " << end1 - begin1 << endl;
	cout << "deque copy vector sort, copy back deque: " << end2 - begin2 << endl;
	return 0;
}

輸出：

deque sort: 1456
deque copy vector sort, copy back deque: 198

對于大規(guī)模數(shù)據(jù)的訪問，顯然 deque 效率落入下風(fēng)。

總結(jié)

盡管 deque 在某些方面具有優(yōu)勢，但由于其遍歷性能較低和內(nèi)存管理復(fù)雜等缺陷，在需要頻繁遍歷或要求高效隨機訪問的場景中，vector 和 list 通常是更好的選擇。因此，在實際應(yīng)用中，deque 的使用相對較少，主要用于特定場景，如 stack 和 queue 的底層數(shù)據(jù)結(jié)構(gòu)。

為什么選擇 deque 作為 stack 和 queue 的底層默認容器?

stack 是一種后進先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要具有 push_back() 和 pop_back() 操作的線性結(jié)構(gòu)，都可以作為 stack 的底層容器，比如 vector 和 list 都可以；queue 是先進先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有 push_back() 和 pop_front() 操作的線性結(jié)構(gòu)，都可以作為 queue 的底層容器，比如 list。

選擇 deque 作為 stack 和 queue 的底層默認容器主要是由于 deque 的特性能夠很好地滿足這兩種數(shù)據(jù)結(jié)構(gòu)的需求。以下是詳細的原因：

1. 只需要在固定的一端或兩端進行操作

stack 和 queue 主要在固定的一端或兩端進行操作：

stack：后進先出（LIFO），主要在末端進行插入和刪除操作。
queue：先進先出（FIFO），在前端刪除，在末端插入。

由于 deque（雙端隊列）支持在兩端進行高效的插入和刪除操作，因此非常適合用于實現(xiàn) stack 和 queue。

2. 擴展效率

deque vs vector：

當(dāng) deque 擴展時，不需要像 vector 那樣搬移整個數(shù)組。deque 是分段存儲的，擴展時只需增加新的塊，而不是搬移整個容器中的元素。
這使得 deque 在元素增長時具有更高的效率，因為 deque 避免了大量的內(nèi)存復(fù)制。

3. 內(nèi)存使用效率

deque vs list：

list 是鏈表結(jié)構(gòu)，雖然在插入和刪除時也很高效，但它的節(jié)點需要額外的內(nèi)存來存儲指針，并且每次操作都需要動態(tài)分配內(nèi)存，導(dǎo)致內(nèi)存利用率較低。
deque 是基于分段的動態(tài)數(shù)組，內(nèi)存利用率更高，因為每個塊的內(nèi)存分配是連續(xù)的，且不需要額外的指針開銷。

4. CPU 緩存命中率

連續(xù)內(nèi)存塊帶來的優(yōu)勢：

deque 的每個塊都是連續(xù)的內(nèi)存，盡管整個 deque 是分段存儲的。
這種設(shè)計相比于鏈表，具有更高的 CPU 緩存命中率，因為訪問同一個塊中的元素時，能更好地利用 CPU 緩存。

7. 雙端隊列的模擬實現(xiàn)

1. 主類Deque

這是 deque 的主類，用于實現(xiàn)雙端隊列的基本操作和管理。

template <typename T>
class Deque {
public:
    class Iterator;

    Deque();  // 構(gòu)造函數(shù)
    void push_back(const T& value);  // 在尾部插入元素
    void push_front(const T& value);  // 在頭部插入元素
    void pop_back();  // 刪除尾部元素
    void pop_front();  // 刪除頭部元素
    Iterator begin() const;  // 返回雙端隊列的開始迭代器
    Iterator end() const;  // 返回雙端隊列的結(jié)束迭代器
    bool isEmpty() const;  // 判斷雙端隊列是否為空

private:
    T** map;  // 指向塊的指針數(shù)組
    size_t map_size;  // 中控數(shù)組的大小
    Iterator start;  // 開始迭代器
    Iterator finish;  // 結(jié)束迭代器

    void allocateBlock(bool atFront = false);  // 分配新的塊
};

2. 迭代器類Iterator

這是 deque 的迭代器類，用于實現(xiàn)遍歷雙端隊列中的元素。

template <typename T>
class Iterator {
public:
    T* cur;  // 當(dāng)前元素的指針
    T* first;  // 當(dāng)前塊的起始位置的指針
    T* last;  // 當(dāng)前塊的結(jié)束位置的指針
    T** node;  // 指向中控數(shù)組中當(dāng)前塊的指針

    Iterator();  // 默認構(gòu)造函數(shù)
    Iterator(T* cur, T* first, T* last, T** node);  // 帶參數(shù)的構(gòu)造函數(shù)
    T& operator*() const;  // 解引用操作符
    Iterator& operator++();  // 前置自增操作符
    Iterator operator++(int);  // 后置自增操作符
    Iterator& operator--();  // 前置自減操作符
    Iterator operator--(int);  // 后置自減操作符
    bool operator==(const Iterator& other) const;  // 相等比較操作符
    bool operator!=(const Iterator& other) const;  // 不等比較操作符
};

因為 Iterator 類的操作會更新指針成員 cur、start 等，確保它們始終指向有效的內(nèi)存區(qū)域，因此不會出現(xiàn)釋放內(nèi)存導(dǎo)致懸空指針的情況。

在 Deque 類中，Iterator 對象的生命周期受到 Deque 對象的控制，在 Deque 的生命周期內(nèi)，Iterator 對象的指針成員都是有效的。

3. 構(gòu)造函數(shù)和常規(guī)操作

// 前向聲明 Iterator 類
class Iterator;     
// 默認構(gòu)造
Deque() : map(nullptr), map_size(0)     
{
    allocateBlock();
    start.node = finish.node = map;
    start.cur = finish.cur = *start.node + BLOCK_SIZE / 2;
    start.first = finish.first = *start.node;
    start.last = finish.last = *start.node + BLOCK_SIZE;
}
// 尾插
void push_back(const T& value) 
{
    if (finish.cur == finish.last)
    {
        allocateBlock();
        ++finish.node;
        finish.first = *finish.node;
        finish.last = finish.first + BLOCK_SIZE;
        finish.cur = finish.first;
    }
    *finish.cur = value;
    ++finish.cur;
}
// 頭插
void push_front(const T& value) 
{
    if (start.cur == start.first) 
    {
        allocateBlock(true);
        --start.node;
        start.first = *start.node;
        start.last = start.first + BLOCK_SIZE;
        start.cur = start.last;
    }
    --start.cur;
    *start.cur = value;
}
// 尾刪
void pop_back() {
    if (isEmpty()) {
        throw std::out_of_range("Deque is empty");  // 異常處理
    }
    if (finish.cur == finish.first) {
        --finish.node;
        finish.first = *finish.node;
        finish.last = finish.first + BLOCK_SIZE;
        finish.cur = finish.last;
    }
    --finish.cur;
}
// 頭刪
void pop_front()
{
    if (isEmpty()) 
    {
        throw std::out_of_range("Deque is empty");  // 異常處理
    }
    if (start.cur == start.last) 
    {
        ++start.node;
        start.first = *start.node;
        start.last = start.first + BLOCK_SIZE;
        start.cur = start.first;
    }
    ++start.cur;
}

Iterator begin() const 
{
    return start;
}

Iterator end() const 
{
    return finish;
}

bool isEmpty() const 
{
    return start == finish;
}

后面我們包裝在主類dqeue中，便于管理

4. 內(nèi)部實現(xiàn)和輔助函數(shù)

void allocateBlock(bool atFront = false)    // 分配新的塊
{  
    T** new_map = new T * [map_size + 1];   // 中控數(shù)組的空間大小+1，存放增加的塊
    for (size_t i = 0; i < map_size; ++i) 
    {
        new_map[i + (atFront ? 1 : 0)] = map[i];    // 如果 atFront 為 false，則 map 中的內(nèi)容保持原位置
    }
    new_map[atFront ? 0 : map_size] = new T[BLOCK_SIZE];// 為新的塊分配空間
    delete[] map;                // 釋放舊的 map 內(nèi)存。
    map = new_map;               // map 指向新的指針數(shù)組 new_map。
    ++map_size;
    if (atFront)                 // 如果在前端分配新的塊，調(diào)整 start 和 finish 迭代器的 node 指針，確保它們指向正確的位置。
    {                            //這一步是必要的，因為在 map 前端插入新的塊后，這將導(dǎo)致原本的所有塊指針都需要向后移動一位。
        ++start.node;
        ++finish.node;
    }
}

8. 完整代碼及演示

deque.h

#pragma once

#include <iostream>
#include <stdexcept>    // 提供了標(biāo)準(zhǔn)化的方式來報告和處理錯誤
#include <vector>

const size_t BLOCK_SIZE = 8;    // 塊的大小

template <typename T>
class Deque {
public:
    // 前向聲明 Iterator 類
    class Iterator;     
    // 默認構(gòu)造
    Deque() : map(nullptr), map_size(0)     
    {
        allocateBlock();
        start.node = finish.node = map;
        start.cur = finish.cur = *start.node + BLOCK_SIZE / 2;
        start.first = finish.first = *start.node;
        start.last = finish.last = *start.node + BLOCK_SIZE;
    }
    // 尾插
    void push_back(const T& value) 
    {
        if (finish.cur == finish.last)
        {
            allocateBlock();
            ++finish.node;
            finish.first = *finish.node;
            finish.last = finish.first + BLOCK_SIZE;
            finish.cur = finish.first;
        }
        *finish.cur = value;
        ++finish.cur;
    }
    // 頭插
    void push_front(const T& value) 
    {
        if (start.cur == start.first) 
        {
            allocateBlock(true);
            --start.node;
            start.first = *start.node;
            start.last = start.first + BLOCK_SIZE;
            start.cur = start.last;
        }
        --start.cur;
        *start.cur = value;
    }
    // 尾刪
    void pop_back() {
        if (isEmpty()) {
            throw std::out_of_range("Deque is empty");  // 異常處理
        }
        if (finish.cur == finish.first) {
            --finish.node;
            finish.first = *finish.node;
            finish.last = finish.first + BLOCK_SIZE;
            finish.cur = finish.last;
        }
        --finish.cur;
    }
    // 頭刪
    void pop_front()
    {
        if (isEmpty()) 
        {
            throw std::out_of_range("Deque is empty");  // 異常處理
        }
        if (start.cur == start.last) 
        {
            ++start.node;
            start.first = *start.node;
            start.last = start.first + BLOCK_SIZE;
            start.cur = start.first;
        }
        ++start.cur;
    }

    Iterator begin() const 
    {
        return start;
    }

    Iterator end() const 
    {
        return finish;
    }

    bool isEmpty() const 
    {
        return start == finish;
    }

    class Iterator {
    public:
        T* cur;     // 當(dāng)前元素的指針
        T* first;   // 當(dāng)前塊的起始位置的指針
        T* last;    // 當(dāng)前塊的結(jié)束位置的指針
        T** node;   // 指向中控數(shù)組中當(dāng)前塊的指針
        // 默認構(gòu)造函數(shù)
        Iterator()                                      
            : cur(nullptr), first(nullptr), last(nullptr), node(nullptr) 
        {}
        // 帶參數(shù)的構(gòu)造函數(shù)
        Iterator(T* cur, T* first, T* last, T** node)   
            : cur(cur), first(first), last(last), node(node) 
        {}

        T& operator*() const                // 解引用操作符
        {
            return *cur;
        }

        Iterator& operator++()              // 前置自增操作符
        {
            ++cur;
            if (cur == last) 
            {
                ++node;
                first = *node;
                last = first + BLOCK_SIZE;
                cur = first;
            }
            return *this;
        }

        Iterator operator++(int)            // 后置自增操作符
        {          
            Iterator temp = *this;
            ++(*this);
            return temp;
        }


        Iterator& operator--()              // 前置自減操作符
        {   
            if (cur == first) 
            {
                --node;
                first = *node;
                last = first + BLOCK_SIZE;
                cur = last;
            }
            --cur;
            return *this;
        }

        Iterator operator--(int)            // 后置自減操作符
        {  
            Iterator temp = *this;
            --(*this);
            return temp;
        }

        bool operator==(const Iterator& other) const // 相等比較操作符
        {
            return cur == other.cur;
        }

        bool operator!=(const Iterator& other) const // 不等比較操作符
        {
            return !(*this == other);
        }
    };

private:
    T** map;  // 指向塊的指針數(shù)組
    size_t map_size;  // 中控數(shù)組的大小
    Iterator start;  // 開始迭代器
    Iterator finish;  // 結(jié)束迭代器

    void allocateBlock(bool atFront = false)    // 分配新的塊
    {  
        T** new_map = new T * [map_size + 1];   // 中控數(shù)組的空間大小+1，存放增加的塊
        for (size_t i = 0; i < map_size; ++i) 
        {
            new_map[i + (atFront ? 1 : 0)] = map[i];    // 如果 atFront 為 false，則 map 中的內(nèi)容保持原位置
        }
        new_map[atFront ? 0 : map_size] = new T[BLOCK_SIZE];// 為新的塊分配空間
        delete[] map;                // 釋放舊的 map 內(nèi)存。
        map = new_map;               // map 指向新的指針數(shù)組 new_map。
        ++map_size;
        if (atFront)                 // 如果在前端分配新的塊，調(diào)整 start 和 finish 迭代器的 node 指針，確保它們指向正確的位置。
        {                            //這一步是必要的，因為在 map 前端插入新的塊后，這將導(dǎo)致原本的所有塊指針都需要向后移動一位。
            ++start.node;
            ++finish.node;
        }
    }
};

test.cpp

#include "deque.h"

using namespace std;

int main() {
	Deque<int> dq;
	dq.push_back(1);
	dq.push_back(2);
	dq.push_back(3);
	dq.push_front(0);
	dq.push_front(-1);

	for (Deque<int>::Iterator it = dq.begin(); it != dq.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	dq.pop_back();
	dq.pop_front();
	dq.pop_front();
	dq.pop_front();
	dq.pop_front();
	dq.pop_front(); //	拋異常
	

	for (Deque<int>::Iterator it = dq.begin(); it != dq.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	return 0;
}

輸出