提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

【C++修炼之路】12. stack && queue类

C++amp 12 Queue Stack 修炼
2023-06-13 09:17:43 时间

stack&&queue

一. stack的介绍和使用

1. stack的介绍

stack的文档介绍

  1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
    • empty：判空操作
    • back：获取尾部元素操作
    • push_back：尾部插入元素操作
    • pop_back：尾部删除元素操作
  4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

2. stack的使用

函数说明

接口说明

stack()

构造空的栈

empty()

检测stack是否为空

size()

返回stack中元素的个数

top()

返回栈顶元素的引用

push()

将元素val压入stack中

pop()

将stack中尾部的元素弹出

二. stack的模拟实现

在开始之前，我们需要知道什么是设计模式：设计模式概念 目前有23种。

我们现在接触的模式有两种：适配器模式、迭代器模式

对于迭代器模式，使我们所熟知的，因为对于vector和list的模拟实现，都涉及到迭代器模式，迭代器模式将内部复杂的数据结构进行了封装，从而在上层使用中更为便捷，即不暴露底层细节，封装后提供统一的方式访问容器；而对于适配器模式：现实生活中，被称为适配器的有电源等待，因此适配器本质是已有的东西，封装转换出你想要的东西。

对于stack的模拟实现，下面将用适配器转换,vector、list

stack.h

#pragma once
#include<vector>
#include<list>

//stack的模拟实现
namespace cfy
{
	template<class T, class Container = vector<T>>//适配器：调用一种结构实现另一种
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"Stack.h"

int main()
{
    cfy::stack<int, vector<int>> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    return 0;
}

当然，也可以用list替换vector,同时里面的函数也要改成list类的。

三. queue的介绍和使用

1. queue的介绍

queue的文档介绍

  1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
  2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
  3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
    • empty：检测队列是否为空
    • size：返回队列中有效元素的个数
    • front：返回队头元素的引用
    • back：返回队尾元素的引用
    • push_back：在队列尾部入队列
    • pop_front：在队列头部出队列
  4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2. queue的使用

函数声明

接口说明

queue()

构造空的队列

empty()

检测队列是否为空，是返回true，否则返回false

size()

返回队列中有效元素的个数

front()

返回队头元素的引用

back()

返回队尾元素的引用

push()

在队尾将元素val入队列

pop()

将队头元素出队列

四. queue的模拟实现

同stack，模拟实现也是采用适配器的方式，因为stack和queue都不存在迭代器。由于queue经常头删，用vector代价高，因此这里使用list的适配器。

queue.h

#pragma once
#include<vector>
#include<list>
//queue的模拟实现
namespace cfy
{
	template<class T, class Container = list<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();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"queue.h"

int main()
{
	cfy::queue<int, list<int>> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

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

当然，用vector也是可以的，同时需要将对应的函数改成vector类的。

五. deque的介绍和使用

1. deque的介绍

我们查文档发现，虽然stack用了适配器模式，但是其适配器并不是vector，而是deque作为缺省值，这也正对应了stack介绍的第四条，如果不传指定的适配器，stack就采用deque

那么deque是什么呢？——双端队列

deque的文档介绍

我们在C++上一篇list的结尾叙述了vector、list的优缺点：vector的头部中部插入效率低以及扩容消耗，list不支持随机访问，CPU高速缓存命中率低，而deque恰恰会与其互补。即deque双端队列兼具vector、list的优点，可以支持下标访问，头部尾部效率高。

2. deque的使用

deque支持头插尾插，头删尾删，下面就直接使用deque：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<deque>
using namespace std;

int main()
{
	deque<int> d;
	d.push_back(1);//支持尾插
	d.push_back(2);
	d.push_back(3);
	d.push_back(4);

	d.push_front(10);//支持头插
	d.push_front(20);
	for (size_t i = 0; i < d.size(); i++)//支持下标随机访问
	{
		cout << d[i] << " ";
	}
	cout << endl;
	return 0;
}

3. deque的缺陷

deque并没有想象的那么好，否则vector和list也不会存在，deque的使用效率不高，因为效率不如指定场景的vector和list。这一点可以用排序测试。

对于deque的原理，在STL源码剖析的143页：STL源码剖析电子版

相关文章