STL 学习之deque

deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似，下面列出deque的常用成员函数：

 deque的实现比较复杂，内部会维护一个map（注意！不是STL中的map容器）即一小块连续的空间，该空间中每个元素都是指针，指向另一段（较大的）区域，这个区域称为缓冲区，缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》，当然此书中使用的SGI STL与VS2008所使用的PJ STL的实现方法还是有区别的。下面给出了deque的结构图：

 

//双向队列 deque
//by MoreWindows http://blog.csdn.net/morewindows
#include <deque>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
	deque<int> ideq(20); //Create a deque ideq with 20 elements of default value 0
	deque<int>::iterator pos;
	int i;

	//使用assign()赋值  assign在计算机中就是赋值的意思
	for (i = 0; i < 20; ++i)
		ideq[i] = i;
	
	//输出deque
	printf("输出deque中数据:\n");
	for (i = 0; i < 20; ++i)
		printf("%d ", ideq[i]);
	putchar('\n');

	//在头尾加入新数据
	printf("\n在头尾加入新数据...\n");
	ideq.push_back(100);
	ideq.push_front(i);

	//输出deque
	printf("\n输出deque中数据:\n");
	for (pos = ideq.begin(); pos != ideq.end(); pos++)
		printf("%d ", *pos);
	putchar('\n');

	//查找
	const int FINDNUMBER = 19;
	printf("\n查找%d\n", FINDNUMBER);
	pos = find(ideq.begin(), ideq.end(), FINDNUMBER);
	if (pos != ideq.end())
		printf("find %d success\n", *pos);
	else
		printf("find failed\n");

	//在头尾删除数据
	printf("\n在头尾删除数据...\n");
	ideq.pop_back();
	ideq.pop_front();

	//输出deque
	printf("\n输出deque中数据:\n");
	for (pos = ideq.begin(); pos != ideq.end(); pos++)
		printf("%d ", *pos);
	putchar('\n');
	return 0;
}

 以上内容均转之：http://blog.csdn.net/morewindows/article/details/6946811

 

关于面试中遇到优先队列的题目有以下：

 题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。

例如输入

     8
    /  \
   6   10
   /\     /\
 5  7  9  11

 

输出8   6   10   5   7   9   11。

 

我们从树的根结点开始分析。自然先应该打印根结点8，同时为了下次能够打印8的两个子结点，我们应该在遍历到8时把子结点6和10保存到一个数据容器中。现在数据容器中就有两个元素6 和10了。按照从左往右的要求，我们先取出6访问。打印6的同时要把6的两个子结点5和7放入数据容器中，此时数据容器中有三个元素10、5和7。接下来我们应该从数据容器中取出结点10访问了。注意10比5和7先放入容器，此时又比5和7先取出，就是我们通常说的先入先出。因此不难看出这个数据容器的类型应该是个队列。

既然已经确定数据容器是一个队列，现在的问题变成怎么实现队列了。实际上我们无需自己动手实现一个，因为STL已经为我们实现了一个很好的deque（两端都可以进出的队列），我们只需要拿过来用就可以了。

我们知道树是图的一种特殊退化形式。同时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解，将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在二元树上实现广度优先遍历。

代码如下：

#include <deque>
#include <iostream>
using namespace std;

struct BTreeNode // a node in the binary tree
{
	int         m_nValue; // value of node
	BTreeNode  *m_pLeft;  // left child of node
	BTreeNode  *m_pRight; // right child of node
};

///////////////////////////////////////////////////////////////////////
// Print a binary tree from top level to bottom level
// Input: pTreeRoot - the root of binary tree
///////////////////////////////////////////////////////////////////////
void PrintFromTopToBottom(BTreeNode *pTreeRoot)
{
	if(!pTreeRoot)
		return;

	// get a empty queue
	deque<BTreeNode *> dequeTreeNode;

	// insert the root at the tail of queue
	dequeTreeNode.push_back(pTreeRoot);

	while(dequeTreeNode.size())
	{
		// get a node from the head of queue
		BTreeNode *pNode = dequeTreeNode.front();
		dequeTreeNode.pop_front();

		// print the node
		cout << pNode->m_nValue << ' ';

		// print its left child sub-tree if it has
		if(pNode->m_pLeft)
			dequeTreeNode.push_back(pNode->m_pLeft);
		// print its right child sub-tree if it has
		if(pNode->m_pRight)
			dequeTreeNode.push_back(pNode->m_pRight);
	}
}
 PS：层序二叉树，用队列实现！