C/C++编程:STL queue原理探究
概述queue是一种先进先出(FIFO)的数据结构,它有两个出口,如下图queue允许移除最前面元素、新增最后面元素,访问最前面和最后面的元素但是,除了可以移除最前面的元素,从最后面插入元素之外,没有其他任何反复可以存取deque的其他元素。也就是说,queue不允许有遍历行为实现缺省情况下,queue以deque作为底层容器,以实现FIFO的功能。由于queue是以底部容器完成其所有工作,而而具
·
概述
- queue是一种先进先出(FIFO)的数据结构,它有两个出口,如下图
- queue允许移除最前面元素、新增最后面元素,访问最前面和最后面的元素
- 但是,除了可以移除最前面的元素,从最后面插入元素之外,没有其他任何反复可以存取deque的其他元素。也就是说,queue不允许有遍历行为
理论
构造
- 缺省情况下,
queue
以deque
作为底层容器,以实现FIFO的功能。 - 由于
queue
是以底部容器完成其所有工作,而而具有这种修改某物接口,形成令一种风貌的性质者,叫做adapter(适配器)。因此,queue往往不被归类为容器(container),而是叫做容器适配器(container adapter)
其实现如下:
实现
成员函数
queue没有迭代器
queue所有元素的进出都必须符合”先进先出“的条件,只有deque顶端的元素,才有机会被外界取用。queue不提供遍历功能,也不提供迭代器。
实践
用户自定义queue
/* ************************************************************
* Queue.hpp
* - safer and more convenient queue class
* ************************************************************/
#ifndef QUEUE_HPP
#define QUEUE_HPP
#include <deque>
#include <exception>
template <typename T>
class Queue {
protected:
std::deque<T> c; // container for the elements
public:
// exception class for pop() and front() with empty queue
class ReadEmptyQueue : public std::exception {
public:
virtual const char* what() const throw() {
return "read empty queue";
}
};
// number of elements
typename std::deque<T>::size_type size() const {
return c.size();
}
// is queue empty?
bool empty() const {
return c.empty();
}
// insert element into the queue
void push (const T& elem) {
c.push_back(elem);
}
// remove next element from the queue and return its value
T pop () {
if (c.empty()) {
throw ReadEmptyQueue();
}
T elem(c.front());
c.pop_front();
return elem;
}
// return value of next element
T& front () {
if (c.empty()) {
throw ReadEmptyQueue();
}
return c.front();
}
};
#endif /* QUEUE_HPP */
#include <iostream>
#include <string>
#include <exception>
#include "Queue.hpp" // use special queue class
using namespace std;
int main()
{
try {
Queue<string> q;
// insert three elements into the queue
q.push("These ");
q.push("are ");
q.push("more than ");
// pop two elements from the queue and print their value
cout << q.pop();
cout << q.pop();
// push two new elements
q.push("four ");
q.push("words!");
// skip one element
q.pop();
// pop two elements from the queue and print their value
cout << q.pop();
cout << q.pop() << endl;
// print number of remaining elements
cout << "number of elements in the queue: " << q.size()
<< endl;
// read and print one element
cout << q.pop() << endl;
}
catch (const exception& e) {
cerr << "EXCEPTION: " << e.what() << endl;
}
}
以list作为queue的底层容器
除了deque之外,list也有双向开口的数据结构。而且queue使用的底层容器的函数有empty、size、back、push_back、pop_back…,list都具备。所以,可以指定list作为stack的底层容器
#include <iostream>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
int main()
{
std::queue<int, std::list<int>> queue;
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(7);
std::cout << queue.front() << ", " << queue.back() <<"\n";
queue.pop(); std::cout << queue.front() << ", " << queue.back() <<"\n";
queue.pop(); std::cout << queue.front() << ", " << queue.back() <<"\n";
}
成员函数
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
void main()
{
queue<int>s;
s.push(1);
s.push(2); //将val加入队列
s.push(3);
cout << "当前队列中的元素数目" << s.size() << endl;
cout << "返回队列第一个元素的引用" << s.front() << endl;
cout << "返回队列最后一个元素的引用" << s.back() << endl;
// 1 2 3
s.pop(); //删除队列的第一个元素,队列:先进先出
// 2 3
cout << "返回队列第一个元素的引用" << s.front() << endl;
cout << "返回队列最后一个元素的引用" << s.back() << endl;
if (s.empty()) cout << "Is empty" << endl; //队列为真返回空
else cout << "Is not empty" << endl;
system("pause");
}
如何清空队列
直接用空的队列对象赋值
queue<int> q1;
// process
// ...
q1 = queue<int>();
遍历出队列
while (!Q.empty()) Q.pop();
使用swap,这种是最高效的,定义clear,保持STL容器的标准
void clear(queue<int>& q) {
queue<int> empty;
swap(empty, q);
}
更多推荐
已为社区贡献3条内容
所有评论(0)