【初阶与进阶C++详解】第十一篇：stack和queue

🏆个人主页：企鹅不叫的博客

​ 🌈专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》
• Linux

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步💙系列文章💙

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

【初阶与进阶C++详解】第九篇：vector

【初阶与进阶C++详解】第十篇：list

---

---

💎一、stack和queue使用

🏆1.stack使用

数据结构栈(stack)和队列(queue)介绍

stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

void Testatack()
{
	stack<int> s;

	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

🏆2.queue使用

queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队列中第一个元素
back()	返回队列中最后一个元素
push()	在队尾将元素val入队列
pop()	在队尾将元素val出队列

void Testqueue()
{
	queue<int> q;

	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

💎二、容器适配器（deque）

适配器是一种设计模拟，将一个类的接口转化成另一个类的接口

//std::stack
template <class T, class Container = deque<T>> class stack;
//std::queue
template <class T, class Container = deque<T>> class queue;
1
2
3
4

以上使用了容器适配器，默认使用的是deque。

deque(双端队列)：是一种双开口底部总体不连续空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

底层结构不是一段连续的空间，而是由多个小空间组成，相等于一个动态二维数组，但与vector和list相比又会有差异。

deque的优点：

1.相比于vector，deque可以进行头插和头删，且时间复杂度是O(1)，扩容是也不需要大量挪动数据，因此效率是比vector高的。
2.相比于list，deque底层是是连续的空间（单底层不是连续空间），空间利用率高,，也支持随机访问（相比较list而言），但没有vector那么高。
3.总的来说，deque是一种同时具有vector和list两个容器的优点的容器，有一种替代二者的作用，但不是完全替代。

deque的缺点：

1.不适合遍历，因为在遍历是，deque的迭代器要频繁地去检测是否运动到其某段小空间的边界，所以导致效率低下。
2.deque的随机访问的效率是比vector低很多的，实际中，线性结构大多数先考虑vector和list。

💎三、stack和queue模拟实现

🏆1.stack模拟实现

创建一个Container的对象 _con，再借助对象完成封装，默认使用的是deque，其实也可以使用vector

template<class T, class Container = deque<T>>
    class stack 
    {
        public:
        size_t size()
        {
            return _con.size();
        }

        const T& top() 
        {
            return _con.back();
        }
        void push(const T& val) 
        {
            _con.push_back(val);
        }
        void pop() 
        {
            _con.pop_back();
        }
        bool empty() 
        {
            return _con.empty();
        }

        private:
        Container _con;
    };

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

stack使用

void test_stack()
{
    stack<int, vector<int>> s;

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);

    while (!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🏆2.queue模拟实现

注意：queue不能使用vector作为容器，vector头插效率很低，我们可以用list作为容器

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

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

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

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

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

        bool empty()
        {
            return _con.empty();
        }
        private:
        Container _con;
    };
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

queue使用

void test_queue()
{
    queue<int, list<int>> q;
    //queue> q; // 不行,头插效率低

    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);

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

💎四、priority_queue (优先级队列)

🏆1.priority_queue介绍和使用

和queue一样都是属于头文件< queue >，底层采用vector容器作为底层数据结构

template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> >
class priority_queue;

1
2
3

优先级队列就是一个堆，默认是大堆，有关堆知识的传送门

priority_queue()/priority_queue(first, last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回 false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

void test_priority_queue()
{
	priority_queue<int, vector<int>> pq;

	pq.push(5);
	pq.push(7);
	pq.push(4);
	pq.push(2);
	pq.push(6);

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

🏆2.priority_queue模拟实现

2.1priority_queue框架

模拟实现需要用到堆的知识，C++有关堆的其实有相关函数，传送门

模板中有第三个参数Compare(仿函数，类)，明确优先级队列是升序还是降序的

//优先级队列-大堆(<), 小堆(>)
template<class T, class Container = vector<T>, class Compare = less<T>>//默认是大堆
    class priority_queue
    {
        public:
        private:
        Container _con;//利用适配器控制优先级队列
    };
1
2
3
4
5
6
7
8

2.2仿函数

注意，由于仿函数是个类，所以我们在使用时要重载(),使得可以像函数一样使用，仿函数是模板函数，速度比一般函数慢，但本质上简化了代码。

template<class T>
    //小于
    struct less
    {
        bool operator()(const T& x, const T&  y) const
        {
            return x < y;
        }
    };
//大于
template<class T>
    struct greater
    {
        bool operator()(const T& x, const T&  y) const
        {
            return x > y;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

仿函数就是用一个类封装一个成员函数operator()，使得这个类的对象可以像函数一样去调用。

less<int> le;
cout << le(2, 3) << endl;// 该类实例化出的对象可以具有函数行为
1
2

库函数中less和greater存放在< functional >头文件中

2.3priority_queue模拟实现

void AdjustUp(int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        //if (_con[child] > _con[parent])  //<  建小堆  > 建大堆
        if (_comFunc(_con[parent], _con[child]))
        {
            swap(_con[parent], _con[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void AdjustDown(int parent)
{
    size_t child = parent * 2 + 1;
    while (child < _con.size())
    {
        //if (child+1 < _con.size() && _con[child] < _con[child+1])  
        if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
        {
            ++child;
        }

        //if (_con[parent] < _con[child]) //建大堆
        if (_comFunc(_con[parent], _con[child]))
        {
            swap(_con[parent], _con[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//先将顶部元素和队尾元素交换，在删除队尾元素，在向下调整建立大堆或者小堆
void pop()
{
    assert(!_con.empty());
    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    AdjustDown(0);
}
//先在队尾插入数据，然后向上调整建大堆或者小堆
void push(const T& x)
{
    _con.push_back(x);
    AdjustUp(_con.size() - 1);
}
const T& top()
{
    return _con[0];
}

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

bool empty()
{
    return _con.empty();
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

---