《C++笔记第二部分数据结构及STL容器篇》第4章队列C++模板实现及STL容器

2022-08-12 13:13:21

4.1队列简介

4.1.1 队列的特点

队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：
队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构。
在队尾添加元素，在队头添加元素。

4.1.2 队列的相关概念

队头与队尾：允许元素插入的一端称为队尾，允许元素删除的一端称为队头。
入队：队列的插入操作。
出队：队列的删除操作。
例如我们有一个存储整型元素的队列，我们依次入队：{1，2，3}

图1

添加元素时，元素只能从队尾一端进入队列，也即是2只能跟在1后面，3只能跟在2后面。
如果队列中的元素要出队：

图2

元素只能从队首出队列，出队列的顺序为：1、2、3，与入队时的顺序一致，这就是所谓的“先进先出”。

4.1.3 队列的操作

入队：通常命名为push()
出队：通常命名为pop()
求队列中元素个数
判断队列是否为空
获取队首元素

4.1.4 队列的存储结构

队列与栈一样是一种线性结构，因此以常见的线性表如数组、链表作为底层的数据结构。本文中，我们以数组、链表为底层数据结构构建队列。

4.2队列实现

4.2.1队列C++模板实现

4.2.1.1基于数组的循环队列实现

以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作：

图3

可能有人说，把队首标志往后移动不就不用移动元素了吗？的确，但那样会造成数组空间的“流失”。
我们希望队列的插入与删除操作都是O(1)的时间复杂度，同时不会造成数组空间的浪费，我们应该使用循环队列。所谓的循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。

图4

那么我们如何判断队列是空队列还是已满呢？
栈空：队首标志=队尾标志时，表示栈空，即红绿两个标志在图中重叠时为栈空。
栈满 : 队尾+1 = 队首时，表示栈空。图三最下面的队列即为一个满队列。尽管还有一个空位，我们不存储元素。

循环队列的抽象数据类型

template <typename T>
class LoopQueue
{
public:
    LoopQueue(int c = 10);
    ~LoopQueue();
public:
    bool isEmpty();        //队列的判空
    int size();            //队列的大小
    bool push(T t);        //入队列
    bool pop();            //出队列
    T front();            //队首元素
 
private:
    int capacity;
    int begin;
    int end;
    T*  queue;
};

【注】
begin：队首标志
end：队尾标志
capacity：数组容量
queue：数组

队列的具体实现
队列的操作非常简单，这里不再多说。

template<typename T>
LoopQueue<T>::LoopQueue(int c = 10)
: capacity(c), begin(0), end(0), queue(nullptr)
{
    queue = new T[capacity];
};
 
template<typename T>
LoopQueue<T>::~LoopQueue()
{
    delete[]queue;
}
 
template <typename T>
bool LoopQueue<T>::isEmpty()
{
    if (begin == end)
        return true;
    return false;
};
 
template<typename T>
int LoopQueue<T>::size()
{
    return (end-begin+capacity)%capacity; //计算队列长度
};
 
template<typename T>
bool LoopQueue<T>::push(T t)
{
    if (end + 1 % capacity == begin) //判断队列是否已满
    {
        return false;
    }
    queue[end] = t;
    end = (end + 1) % capacity;
    return true;
};
 
template <typename T>
bool LoopQueue<T>::pop()
{
    if (end == begin) //判断队列是否为空
    {
        return false;
    }
    begin = (begin + 1) % capacity;
    return true;
};
 
template <typename T>
T LoopQueue<T>::front()
{
    if (end == begin)
    {
        return false;
    }
    return queue[begin];
};

完整代码

LoopQueue.h

# ifndef LOOP_QUEUE_HPP
# define LOPP_QUEUE_HPP
template <typename T>
class LoopQueue
{
public:
	LoopQueue(int c = 10);
	~LoopQueue();
public:
	bool isEmpty();		//队列的判空
	int size();			//队列的大小
	bool push(T t);		//入队列
	bool pop();			//出队列
	T front();			//队首元素

private:
	int capacity;
	int begin;
	int end;
	T*  queue;
};

template<typename T>
LoopQueue<T>::LoopQueue(int c = 10)
: capacity(c), begin(0), end(0), queue(nullptr)
{
	queue = new T[capacity];
};

template<typename T>
LoopQueue<T>::~LoopQueue()
{
	delete[]queue;
}

template <typename T>
bool LoopQueue<T>::isEmpty()
{
	if (begin == end)
		return true;
	return false;
};

template<typename T>
int LoopQueue<T>::size()
{
	return (end-begin+capacity)%capacity; //计算队列长度
};

template<typename T>
bool LoopQueue<T>::push(T t)
{
	if (end + 1 % capacity == begin) //判断队列是否已满
	{
		return false;
	}
	queue[end] = t;
	end = (end + 1) % capacity;
	return true;
};

template <typename T> 
bool LoopQueue<T>::pop()
{
	if (end == begin) //判断队列是否为空
	{
		return false;
	}
	begin = (begin + 1) % capacity;
	return true;
};

template <typename T>
T LoopQueue<T>::front()
{
	if (end == begin)
	{
		return false;
	}
	return queue[begin];
};

# endif

main.cpp

/**
  ******************************************************************************
  * @file    		main.cpp
  * @author  		BruceOu
  * @version 		V1.0
  * @date    		2019.03.07
  * @brief          LoopQueue
  ******************************************************************************
  */
/**Includes*********************************************************************/
#include <iostream>
#include <LoopQueue.h>
#include<string>

/**namespace********************************************************************/
using namespace std;

/**
  * @brief     ???
  * @param     argc
               argv
  * @retval    None
  */
int main(int argc, char *argv[])
{
	LoopQueue<string> queue(6);
	queue.push("one");
	queue.push("two");
	queue.push("three");
	queue.push("four");
	queue.push("five");
	cout << "????" << queue.size() << endl;
	while (!queue.isEmpty())
	{
		cout << queue.front() << endl;
		queue.pop();
	}

    return 0;
}

4.2.1.2链队列实现

链队列是基于链表实现的队列，它不存在数组的O（n）的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首，哪头做队尾。显然我们应该以链表头部为队首，链表尾部为队尾。存储一个指向队尾的指针，方便从链表尾插入元素；使用带头节点的链表，方便从链表头删除元素。

图5

链表节点

template<typename T>
struct Node
{
    Node(T t) :value(t), next(nullptr){}
    Node() = default;
 
    T value;
    Node<T> * next;
};

【注】
 vaule : 链表节点的值
 next : 指针，指向下一个节点

队列的抽象数据类型
链队列提供的接口与循环队列一致

template<typename T>
class LinkQueue
{
public:
    LinkQueue();
    ~LinkQueue();
 
    bool isEmpty();
    int size();
    bool pop();
    void push(T t);
    T front();
 
private:
    Node<T>* phead;
    Node<T>* pend;
    int count;
};

队列的具体实现

template<typename T>
LinkQueue<T>::LinkQueue()
    :phead(nullptr),pend(nullptr),count(0)
{
    phead = new Node<T>();
    pend = phead;
    count = 0;
};
 
template <typename T>
LinkQueue<T>::~LinkQueue()
{
    while (phead->next != nullptr)
    {
        Node<T> * pnode = phead;
        phead = phead->next;
    }
};
 
template <typename T>
bool LinkQueue<T>:: isEmpty()
{
    return count==0;
};
 
template <typename T>
int LinkQueue<T>::size()
{
    return count;
};
 
//在队尾插入
template <typename T>
void LinkQueue<T>::push(T t)
{
    Node<T>* pnode = new Node<T>(t);
    pend->next = pnode;
    pend = pnode;
    count++;
};
 
//在队首弹出
template <typename T>
bool LinkQueue<T>::pop()
{
    if (count == 0)
        return false;
    Node<T>* pnode = phead->next;
    phead->next = phead->next->next;
    delete pnode;
    count--;
    return true;
};
 
//获取队首元素
template<typename T>
T LinkQueue<T>::front()
{
    return phead->next->value;
};

完整代码

LinkQueue.h

# ifndef LINK_QUEUE_HPP
# define LINK_QUEUE_HPP
template<typename T>
struct Node
{
	Node(T t) :value(t), next(nullptr){}
	Node() = default;

	T value;
	Node<T> * next;
};
template<typename T>
class LinkQueue
{
public:
	LinkQueue();
	~LinkQueue();

	bool isEmpty();
	int size();
	bool pop();
	void push(T t);
	T front();

private:
	Node<T>* phead;
	Node<T>* pend;
	int count;
};

template<typename T>
LinkQueue<T>::LinkQueue()
	:phead(nullptr),pend(nullptr),count(0)
{
	phead = new Node<T>();
	pend = phead;
	count = 0;
};

template <typename T>
LinkQueue<T>::~LinkQueue()
{
	while (phead->next != nullptr)
	{
		Node<T> * pnode = phead;
		phead = phead->next;
	}
};

template <typename T>
bool LinkQueue<T>:: isEmpty()
{
	return count==0;
};

template <typename T>
int LinkQueue<T>::size()
{
	return count;
};

//在队尾插入
template <typename T>
void LinkQueue<T>::push(T t)
{
	Node<T>* pnode = new Node<T>(t);
	pend->next = pnode;
	pend = pnode;
	count++;
};

//在队首弹出
template <typename T>
bool LinkQueue<T>::pop()
{
	if (count == 0)
		return false;
	Node<T>* pnode = phead->next;
	phead->next = phead->next->next;
	delete pnode;
	count--;
	return true;
};

//获取队首元素
template<typename T>
T LinkQueue<T>::front()
{
	return phead->next->value;
};

# endif

main.cpp

/**
  ******************************************************************************
  * @file    		main.cpp
  * @author  		BruceOu
  * @version 		V1.0
  * @date    		2019.03.07
  * @brief          LinkQueue
  ******************************************************************************
  */
/**Includes*********************************************************************/
#include <iostream>
#include "LinkQueue.h"
#include <string>

/**namespace********************************************************************/
using namespace std;

/**
  * @brief     ???
  * @param     argc
               argv
  * @retval    None
  */
int main(int argc, char *argv[])
{
	LinkQueue<string> lqueue;
	lqueue.push("one");
	lqueue.push("two");
	lqueue.push("three");
	lqueue.push("four");
	lqueue.push("five");
	cout << "?????" << lqueue.size() << endl;
	while (!lqueue.isEmpty())
	{
		cout << lqueue.front() << endl;
		lqueue.pop();
	}

    return 0;
}

4.2.2 STL deque实现

底层数据结构

vector是单向开口的线性连续空间，deque则是一种双向开口的连续数据空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。当然vector也可以在头尾两端进行操作，但是其头部操作效果奇差，所以标准库没有为vector提供push_front或pop_front操作。与vector类似，deque支持元素的快速随机访问。deque的示意图如下：

图6

现在问题来了：如果deque以数组来实现，如何做到在头部的常数时间插入？如果是采用链表来实现，又如何做到快速随机访问？deque的内部数据结构到底如何？想必你已经猜到了，要实现如上需求，需要由一段一段的连续空间链接起来的数据结构才能满足。

内存分配策略

接着上面讲。deque由一段一段的连续空间所链接而成，一旦需要在deque的前端或尾端增加新空间，便配置一段定量的连续空间，并将该空间串接在deque的头部或尾部。deque复杂的迭代器架构，构建出了所有分段连续空间”整体连续“的假象。
既然deque是由一段一段定长的连续空间所构成，就需要有结构来管理这些连续空间。deque采用一块map（非STL中的map）作为主控，map是一块小的连续空间，其中每个元素都是指针，指向一块较大的线性连续空间，称为缓冲区。而缓冲区才是存储deque元素的空间主体。示例图：

图7

map本身也是一块固定大小的连续空间，当缓冲区数量增多，map容不下更多的指针时，deque会寻找一块新的空间来作为map。

deque的迭代器

为了使得这些分段的连续空间看起来像是一个整体，deque的迭代器必须有这样的能力：它必须能够指出分段连续空间在哪里，判断自己所指的位置是否位于某一个缓冲区的边缘，如果位于边缘，则执行operator-- 或operator++时要能够自动跳到下一个缓冲区。因此，尽管deque的迭代器也是Ramdon Access Iterator 迭代器，但它的实现要比vector的复杂太多。SGI版本的STL deque实现思路可以看侯捷的《STL源码剖析》。

迭代器失效问题

 在deque容器首部或者尾部插入元素不会使得任何迭代器失效。
 在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。
 在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

deque双端队列double-end queue，deque是在功能上合并了vector和list。
优点：
随机访问方便，即支持[ ]操作符和vector.at()；在内部方便的进行插入和删除操作可在两端进行push、pop。
缺点：
占用内存多。

使用区别：
 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
 如果你需要大量的插入和删除，而不关心随机存取，则应使用list
 如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque

/**
  ******************************************************************************
  * @file    		main.cpp
  * @author  		BruceOu
  * @version 		V1.0
  * @date    		2019.03.04
  * @brief          deque
  ******************************************************************************
  */
/**Includes*********************************************************************/
#include <iostream>
#include <deque>

/**namespace********************************************************************/
using namespace std;

void f1()
{
	deque<int> d(3);
	d.push_back(2);//后
	d.push_front(1);//前
	d.push_back(3);//后加
	// 1 0 0 0 2 3
	deque<int>::iterator it = d.begin();
	while (it != d.end())
	{
		cout << *it << endl;
		it++;
	}
	cout<<"============================\n";
	d.pop_front(); //删除第一个
	it = d.begin();
	while (it != d.end())
	{
		cout << *it << endl;
		it++;
	}
}

/**
  * @brief     主函数
  * @param     argc
               argv
  * @retval    None
  */
int main(int argc, char *argv[])
{
	f1();
	return 0;
}

码农公寓

4.1队列简介

4.1.1 队列的特点

4.1.2 队列的相关概念

4.1.3 队列的操作

4.1.4 队列的存储结构

4.2队列实现

4.2.1队列C++模板实现

4.2.1.1基于数组的循环队列实现

完整代码

4.2.1.2链队列实现

完整代码

4.2.2 STL deque实现

相关文章