九乡新闻网麦乐购公司:(数据结构复习)链队列和动态数组队列以及STL中的deque双端队列和Queue普通队列,堆排序队列priority_queue
来源：百度文库 编辑：九乡新闻网 时间：2024/04/27 13:33:49
队列
队列的定义：队列是一种只能在表的尾端进行插入操作，在首端进行删除操作的线性数据结构。它是先进先出（FIFO）的线性表。 队列的存储结构：有顺序队列—循环队列，设有首指针和尾指针；链队列—一般在单循环链表上实现，只设尾指针，不设首指针称循环链队列。
队列的操作：初始化队列、进队、出队，通过队列的首指针front和尾指针rear实现操作
教学目的： 掌握队列的类型定义,掌握链队列的表示与实现方法
教学重点： 链队列的表示与实现
教学难点： 链队列的表示与实现
授课内容：
一、队列的定义:
队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。
在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。
抽象数据类型队列:
ADT Queue{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={ | ai-1,ai(- D,i=2,...,n}
基本操作：
InitQueue(&Q) 构造一个空队列Q
Destroyqueue(&Q) 队列Q存在则销毁Q
ClearQueue(&Q) 队列Q存在则将Q清为空队列
QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT Queue
二、链队列－队列的链式表示和实现
用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。
Q.front -> |
\|/
1 | 队头
\|/
2 |
\|/
3 |
\|/
\|/
Q.rear -> 9 /\ 队尾
Q.front -> |
\|/
1 | 队头
\|/
2 |
\|/
3 |
\|/
\|/
Q.rear -> 9 /\ 队尾
链队列表示和实现：
//存储表示
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//操作说明
Status InitQueue(LinkQueue &Q)
//构造一个空队列Q
Status Destroyqueue(LinkQueue &Q)
//队列Q存在则销毁Q
Status ClearQueue(LinkQueue &Q)
//队列Q存在则将Q清为空队列
Status QueueEmpty(LinkQueue Q)
// 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
Status QueueLenght(LinkQueue Q)
// 队列Q存在,返回Q的元素个数,即队列的长度
Status GetHead(LinkQueue Q,QElemType &e)
//Q为非空队列,用e返回Q的队头元素
Status EnQueue(LinkQueue &Q,QElemType e)
//队列Q存在,插入元素e为Q的队尾元素
Status DeQueue(LinkQueue &Q,QElemType &e)
//Q为非空队列,删除Q的队头元素,并用e返回其值
Status QueueTraverse(LinkQueue Q,QElemType vivsit())
//Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
//操作的实现
Status InitQueue(LinkQueue &Q) {
//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;}
Status Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;}
Status EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
Status DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;}
三、总结
链队列的存储表示
链队列的操作及实现
#include
#include
// 链表队列
typedef struct Qnode{
int data;
struct Qnode *next;
}Qnode,*QueuePtr;//创建链
typedef struct {
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;//创建队列
void EnQueue(LinkQueue &Q,int e)
{
QueuePtr p=(QueuePtr)malloc(sizeof(Qnode));
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}//插入e为队尾元素
void DeQueue(LinkQueue &Q, int &e)
{
if(Q.front==Q.rear) printf("error\n");
QueuePtr p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
}//删除队头元素
int QueueEmpty(LinkQueue Q)
{
if(Q.front==Q.rear) return 1;
else return 0;
}//判断链栈是否为空
void InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));
Q.front->next=NULL;
printf("输入6个队列元素：");
for(int i=0;i<6;i++)
{
int a;
scanf("%d",&a);
EnQueue(Q,a);//向队列中插元素
}
}//初始化栈
void Print(LinkQueue Q)
{
while(!QueueEmpty(Q))
{
int e;
DeQueue(Q,e);
printf("%d ",e);
}
}//输出栈元素
void DestroyQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
}//销毁链队列
int QueueLength(LinkQueue Q)
{
int j=0;
while(Q.front->next)
{
Q.front=Q.front->next;
j++;
}
return j;
}//求链栈长度
main()
{
int a;//存储链队列长度
LinkQueue Q;
InitQueue(Q);
a=QueueLength( Q);
Print (Q);
printf("链队列长%d",a);
return 0;
}
// 动态数组队列
#include
#include
using namespace std;
template
class Queue
{
private:
int rear,front;//队尾与队头指针
Type *elements;//顺序栈数组
int maxSize;//最大元素
int count;//元素个数
public:
Queue(int=10);//constructor
~Queue()
{
delete []elements;
}
void EnQueue(const Type&item);
Type DeQueue();
Type GetTop();
bool IsEmpty()
{
return count == 0;
//return rear==front;
}
bool IsFull()
{
//return (rear+1)%maxSize==front;
return count == maxSize;
}
void MakeEmpty()
{
front = 0;
rear = 0;
count = 0；
}
int Length()
{
//return (rear-front+maxSize)%maxSize;
return count;
}
};
template Queue::Queue(int s):rear(0),front(0),maxSize(s),count(0)
{
elements=new Type[maxSize];
assert(elements!=0);
}
template void Queue::EnQueue(const Type&item)
{
//assert(!IsFull());
if(IsFull())
{
Type * temp = new Type[100];
int n = count;
Type * src = elements;
Type * dec = temp;
while(n--)
{
*dec++ = *src++;
}
delete [] elements;
elements = NULL;
elements = temp;
maxSize = 100;
rear = count;
elements[rear]=item;
rear=(rear+1)%maxSize;
count++;
}
else
{
count++;
elements[rear]=item;
rear=(rear+1)%maxSize;
}
/*
rear=(rear+1)%maxSize;
elements[rear]=item;
*/
}
template Type Queue::DeQueue()
{
assert( !IsEmpty() );//非空时候执行
count--;
Type temp = elements[front];
front=(front+1)%maxSize;
return temp;
/*
front=(front+1)%maxSize;
return elements[front];
*/
}
template Type Queue::GetTop()
{
assert( !IsEmpty() );
return elements[front];
/*
int t=(front+1)%maxSize;
return elements[t];
*/
}
int main()
{
Queue a;
for(int i=0;i<11;i++)
{
a.EnQueue(i);
}
cout<for( int i=0;i<11;i++)
{
cout<a.DeQueue();
}
cout<return 0;
}
“vector是单向开口的连续线性空间，deque则是一种双向开口的连续空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。vector当然也可以在头尾两端进行操作（从技术观点），但是其头部操作效率奇差，无法被接受。”
“deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入和移除操作，二在于deque没有所谓容量（capacity）概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样因为空间不足而重新分配一块更大空间然后复制元素，再释放就空间这样的事情在deque是不会发生的。”
“虽然deque也提供了Ramdon Acces Iterator，但它的迭代器并不是普通指针，其复杂度和vector也不是一个数量级上的，这当然也会影响到运算的各个层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector，将vector（利用STL Sort算法），再复制回deque。”
--以上摘自 侯捷 《STL源码剖析》 p143
deque，意为double ended queue（双端队列），常读作deck。其用法和大家熟知的vector类似，接口基本和vector雷同。至于二者的不同之处和孰优孰劣，上面摘录的侯大师书里说的也很明白。容器本身没有绝对的好坏，关键看应用环境和需要。
成员函数表如下：
函数
描述
assign(beg,end)
assign(n,elem)
将[beg; end) 区间中的数据赋值
将n个elem 的拷贝赋值
at(idx)
传回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range
back()
传回最后一个数据，不检查这个数据是否存在
begin()
传回迭代器重的可一个数据
clear()
移除容器中所有数据
deque c1(c2)
deque c(n)
deque c(n, elem)
deque c(beg,end)
~deque()
复制一个deque
创建一个deque,含有n个数据,数据均已缺省构造产生
创建一个含有n个elem 拷贝的 deque
创建一个以[beg;end)区间的 deque
销毁所有数据，释放内存
empty()
判断容器是否为空
end()
指向迭代器中的最后一个数据地址
erase(pos)
erase(beg,end)
删除pos位置的数据，传回下一个数据的位置
删除[beg,end)区间的数据,传回下一个数据的位置
front()
传回地一个数据
get_allocator
使用构造函数返回一个拷贝
insert(pos,elem)
insert(pos,n,elem)
insert(pos,beg,end)
在pos位置插入一个elem拷贝,传回新数据位置
在pos位置插入n 个elem数据,无返回值
在pos位置插入在[beg,end)区间的数据,无返回值
max_size()
返回容器中最大数据的数量
pop_back()
删除最后一个数据
pop_front()
删除头部数据
push_back(elem)
在尾部加入一个数据
push_front(elem)
在头部插入一个数据
rbegin()
传回一个逆向队列的第一个数据
rend()
传回一个逆向队列的最后一个数据的下一个位置
resize(num)
重新指定队列的长度
size()
返回容器中实际数据的个数
c1.swap(c2)
swap(c1,c2)
将 c1 和 c2 元素互换
同上操作
operator []
返回容器中指定位置的一个引用
延伸阅读：
（1）今天找到一个不得不用deque的理由 （无论是否赞同作者的观点，至少对理解deque是有益的）
（2）深入研究 C++中的 STL Deque 容器
#include
#include
using namespace std;
typedef deque CHARDEQUE;
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with 3 A's
CHARDEQUE a(3,'A');
//create b with 4 B's.
CHARDEQUE b(4,'B');
//print out the contents
print_contents (a,"a");
print_contents (b,"b");
//swap a and b
a.swap(b);
print_contents (a,"a");
print_contents (b,"b");
//swap it back
a.swap(b);
print_contents (a,"a");
print_contents (b,"b");
//assign the contents of b to a
a.assign(b.begin(),b.end());
print_contents (a,"a");
//assign the first two items of b to a
a.assign(b.begin(),b.begin()+2);
print_contents (a,"a");
//assign 3 'Z's to a
a.assign(3,'Z');
print_contents (a,"a");
}
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout <<"The contents of "<< name <<" : ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<}
#include
#include
using namespace std;
typedef deque CHARDEQUE;
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with A, B, C and D
CHARDEQUE a;
a.push_back('A');
a.push_back('B');
a.push_back('C');
a.push_back('D');
//print out the contents
print_contents (a,"a");
cout <<"The first element of a is " <cout <<"The last element of a is " <// modify first and last elements using reference, front, and back
CHARDEQUE::reference reffront=a.front();
CHARDEQUE::reference refback=a.back();
reffront='X';
refback='Y';
print_contents (a,"a");
}
// print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout << "The contents of " << name << ":";
for (pdeque = deque.begin(); pdeque != deque.end(); pdeque++)
cout << " " << *pdeque;
cout<} 
Copy Code
The contents of a: A B C D The first element of a is A The last element of a is D The contents of a: X B C Y
#include
#include
using namespace std;
typedef deque INTDEQUE;
int main()
{
// Create A and fill it with elements 1,2,3,4 and 5
// using push_back function
INTDEQUE A;
A.push_back(1);
A.push_back(2);
A.push_back(3);
A.push_back(4);
A.push_back(5);
// Print the contents of A using iterator
// and functions begin() and end()
INTDEQUE::iterator pi;
for(pi= A.begin(); pi !=A.end(); pi++)
{
cout << *pi <<" " ;
}
cout<}
Output
1 2 3 4 5
#include
#include
using namespace std;
typedef deque INTDEQUE;
void print_contents (INTDEQUE deque);
int main()
{
// create a and with elements 1,2,3,4 and 5
INTDEQUE a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
//print the contents
print_contents (a);
// erase the second element
a.erase(a.begin()+1);
print_contents (a);
//erase the last two elements
a.erase(a.end()-2,a.end());
print_contents (a);
//clear a
a.clear();
print_contents (a);
}
void print_contents (INTDEQUE deque) {
INTDEQUE::iterator pdeque;
cout <<"The output is: ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<} Copy Code
The output is: 1 2 3 4 5 The output is: 1 3 4 5 The output is: 1 3 The output is:
#include
#include
int main( )
{
using namespace std;
deque::iterator c1_Iter, c2_Iter, c3_Iter, c4_Iter, c5_Iter, c6_Iter;
// Create an empty deque c0
deque c0;
// Create a deque c1 with 3 elements of default value 0
deque c1( 3 );
// Create a deque c2 with 5 elements of value 2
deque c2( 5, 2 );
// Create a deque c3 with 3 elements of value 1 and with the
// allocator of deque c2
deque c3( 3, 1, c2.get_allocator( ) );
// Create a copy, deque c4, of deque c2
deque c4( c2 );
// Create a deque c5 by copying the range c4[_First, _Last)
c4_Iter = c4.begin( );
c4_Iter++;
c4_Iter++;
deque c5( c4.begin( ), c4_Iter );
// Create a deque c6 by copying the range c4[_First, _Last) and
// c2 with the allocator of deque
c4_Iter = c4.begin( );
c4_Iter++;
c4_Iter++;
c4_Iter++;
deque c6( c4.begin( ), c4_Iter, c2.get_allocator( ) );
cout << "c1 = ";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout << *c1_Iter << " ";
cout << endl;
cout << "c2 = ";
for ( c2_Iter = c2.begin( ); c2_Iter != c2.end( ); c2_Iter++ )
cout << *c2_Iter << " ";
cout << endl;
cout << "c3 = ";
for ( c3_Iter = c3.begin( ); c3_Iter != c3.end( ); c3_Iter++ )
cout << *c3_Iter << " ";
cout << endl;
cout << "c4 = ";
for ( c4_Iter = c4.begin( ); c4_Iter != c4.end( ); c4_Iter++ )
cout << *c4_Iter << " ";
cout << endl;
cout << "c5 = ";
for ( c5_Iter = c5.begin( ); c5_Iter != c5.end( ); c5_Iter++ )
cout << *c5_Iter << " ";
cout << endl;
cout << "c6 = ";
for ( c6_Iter = c6.begin( ); c6_Iter != c6.end( ); c6_Iter++ )
cout << *c6_Iter << " ";
cout << endl;
}Output
c1 = 0 0 0 c2 = 2 2 2 2 2 c3 = 1 1 1 c4 = 2 2 2 2 2 c5 = 2 2 c6 = 2 2 2
#include
#include
using namespace std;
typedef deque CHARDEQUE;
void print_contents (CHARDEQUE deque);
int main()
{
//create a with 3 A's
CHARDEQUE a(3,'A');
//create b with 2 B's.
CHARDEQUE b(2,'B');
//print out the contents
print_contents (a);
print_contents (b);
//insert 'X' to the beginning of a
a.insert(a.begin(),'X');
print_contents (a);
//insert 'Y' to the end of a
a.insert(a.end(),'Y');
print_contents (a);
//inset 3 'Z's to one item before the end of a
a.insert(a.end()-1,3,'Z');
print_contents (a);
//insert to the end of a from b
a.insert(a.end(),b.begin(),b.end());
print_contents (a);
}
//function to print the contents of deque
void print_contents (CHARDEQUE deque)
{
CHARDEQUE::iterator pdeque;
cout <<"The output is: ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<}Output
The output is: A A A The output is: B B The output is: X A A A The output is: X A A A Y The output is: X A A A Z Z Z Y The output is: X A A A Z Z Z Y B B
#include
#include
using namespace std;
typedef deque CHARDEQUE;
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create an empty deque a
CHARDEQUE a;
//check whether it is empty
if(a.empty())
cout<<"a is empty"<else
cout<<"a is not empty"<//inset A, B, C and D to a
a.push_back('A');
a.push_back('B');
a.push_back('C');
a.push_back('D');
//check again whether a is empty
if(a.empty())
cout<<"a is empty"<else
cout<<"a is not empty"<//print out the contents
print_contents (a,"a");
cout <<"The first element of a is " <cout <<"The first element of a is " <cout <<"The last element of a is " <cout <<"The last element of a is " <}
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout <<"The contents of "<< name <<" :";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout <<" " << *pdeque;
}
cout<} Copy Code
a is empty a is not empty The contents of a : A B C D The first element of a is A The first element of a is A The last element of a is D The last element of a is D
#include
#include
using namespace std;
typedef deque CHARDEQUE;
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with 3 A's
CHARDEQUE a(3,'A');
a.push_front('C');
//create b with 4 B's.
CHARDEQUE b(6,'B');
//print out the contents
print_contents (a,"a");
print_contents (b,"b");
//compare a and b
if (a==b)
cout <<"a is equal to b"<else if(acout <<"a is less than b"<else
cout <<"a is greater than b" <//assign the contents of b to a
a.assign(b.begin(),b.end());
print_contents (a,"a");
print_contents (b,"b");
//compare a and b again
if (a==b)
cout <<"a is equal to b"<else if(acout <<"a is less than b"<else
cout <<"a is greater than b" <}
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout <<"The contents of "<< name <<" : ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<}Output
The contents of a : C A A A The contents of b : B B B B B B a is greater than b The contents of a : B B B B B B The contents of b : B B B B B B a is equal to b
#include
#include
using namespace std;
typedef deque INTDEQUE;
void printcontents (INTDEQUE deque);
int main()
{
INTDEQUE dequetest;
dequetest.push_back(1);
dequetest.push_back(2);
dequetest.push_back(3);
printcontents (dequetest);
dequetest.pop_back();
printcontents (dequetest);
dequetest.pop_back();
printcontents (dequetest);
}
//function to print the contents of deque
void printcontents (INTDEQUE deque)
{
INTDEQUE::iterator pdeque;
cout <<"The output is:"<for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <}
}Output
The output is: 1 2 3 The output is: 1 2 The output is: 1
#include
#include
using namespace std;
typedef deque INTDEQUE;
void printcontents (INTDEQUE deque);
int main()
{
INTDEQUE dequetest;
dequetest.push_front(1);
dequetest.push_front(2);
dequetest.push_front(3);
printcontents (dequetest);
dequetest.pop_front();
printcontents (dequetest);
dequetest.pop_front();
printcontents (dequetest);
}
//function to print the contents of deque
void printcontents (INTDEQUE deque)
{
INTDEQUE::iterator pdeque;
cout <<"The output is:"<for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <}
}Output
The output is: 3 2 1 The output is: 2 1 The output is: 1
#include
#include
using namespace std;
typedef deque INTDEQUE;
int main()
{
// Create A and fill it with elements 1,2,3,4 and 5
// using push_back function
INTDEQUE A;
A.push_back(1);
A.push_back(2);
A.push_back(3);
A.push_back(4);
A.push_back(5);
// Now print the contents in reverse order using reverse_iterator
// and functions rbegin() and rend()
INTDEQUE::reverse_iterator rpi;
cout << "Contents in reverse order:";
for(rpi= A.rbegin(); rpi !=A.rend(); rpi++)
cout << " " << *rpi;
cout<}Output
Contents in reverse order: 5 4 3 2 1
#include
#include
using namespace std;
typedef deque CHARDEQUE;
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with A, B, C and D
CHARDEQUE a;
a.push_back('A');
a.push_back('B');
a.push_back('C');
a.push_back('D');
//print out the contents
print_contents (a,"a");
cout <<"max_size of a is " <cout <<"size of a is " <//let us increase the size to 10
// and set the new elements to be 'X'
a.resize(10,'X');
print_contents (a,"a");
cout <<"size of a is " <//let us resize it to 5
a.resize(5);
print_contents (a,"a");
cout <<"size of a is " <cout <<"max_size of a is still " <}
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout << "The contents of " << name << " :";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << " " << *pdeque ;
}
cout<}Sample Output
The following output is for x86.
Copy Code
The contents of a : A B C D max_size of a is 4294967295 size of a is 4 The contents of a : A B C D X X X X X X size of a is 10 The contents of a : A B C D X size of a is 5 max_size of a is still 4294967295
queue普通队列以deque双端队列为底层架构，成员函数表如下：Constructors
queue
Constructs a queue that is empty or that is a copy of a base container object.
Typedefs
container_type
A type that provides the base container to be adapted by the queue.
size_type
An unsigned integer type that can represent the number of elements in a queue.
value_type
A type that represents the type of object stored as an element in a queue.
Member Functions
back
Returns a reference to the last and most recently added element at the back of the queue.
empty
Tests if the queue is empty.
front
Returns a reference to the first element at the front of the queue.
pop
Removes an element from the front of the queue.
push
Adds an element to the back of the queue.
size
Returns the number of elements in the queue.
#include
#include
using namespace std;
void main()
{
queue q;
queue> q1;
q.push(3);
q.push(19);
while(!q.empty())
{
cout<q.pop();
}
if(q1.size() < 50)
{
q1.push(45);
q1.push(68);
}
while(!q1.empty())
{
cout<q1.pop();
}
}
priority_queue队列，以Vector为架构，用堆排序的方式实现队列元素的有序（默认从高到低）// Functions:
// priority_queue::push(), priority_queue::pop(),
// priority_queue::empty(), priority_queue::top(), queue::size()
#include
#include
#include
#include
#include
using namespace std ;
// Using priority_queue with deque
// Use of function less sorts the items in ascending order
typedef deque INTDQU;
typedef priority_queue > INTPRQUE;
// Using priority_queue with vector
// Use of function greater sorts the items in descending order
typedef vector CHVECTOR;
typedef priority_queue > CHPRQUE;
int main(void)
{
size_t size_q;
INTPRQUE q;
CHPRQUE p;
// Insert items in the priority_queue(uses deque)
q.push(42);
q.push(100);
q.push(49);
q.push(201);
// Output the item at the top using top()
cout << q.top() << endl;
// Output the size of priority_queue
size_q = q.size();
cout << "size of q is:" << size_q << endl;
// Output items in priority_queue using top()
// and use pop() to get to next item until
// priority_queue is empty
while (!q.empty())
{
cout << q.top() << endl;
q.pop();
}
// Insert items in the priority_queue(uses vector)
p.push('c');
p.push('a');
p.push('d');
p.push('m');
p.push('h');
// Output the item at the top using top()
cout << p.top() << endl;
// Output the size of priority_queue
size_q = p.size();
cout << "size of p is:" << size_q << endl;
// Output items in priority_queue using top()
// and use pop() to get to next item until
// priority_queue is empty
while (!p.empty())
{
cout << p.top() << endl;
p.pop();
}
}Output
201 size of q is:4 201 100 49 42 a size of p is:5 a c d h m
队列的定义：队列是一种只能在表的尾端进行插入操作，在首端进行删除操作的线性数据结构。它是先进先出（FIFO）的线性表。 队列的存储结构：有顺序队列—循环队列，设有首指针和尾指针；链队列—一般在单循环链表上实现，只设尾指针，不设首指针称循环链队列。
队列的操作：初始化队列、进队、出队，通过队列的首指针front和尾指针rear实现操作
教学目的： 掌握队列的类型定义,掌握链队列的表示与实现方法
教学重点： 链队列的表示与实现
教学难点： 链队列的表示与实现
授课内容：
一、队列的定义:
队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。
在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。
抽象数据类型队列:
ADT Queue{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={
基本操作：
InitQueue(&Q) 构造一个空队列Q
Destroyqueue(&Q) 队列Q存在则销毁Q
ClearQueue(&Q) 队列Q存在则将Q清为空队列
QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT Queue
二、链队列－队列的链式表示和实现
用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。
Q.front -> |
\|/
1 | 队头
\|/
2 |
\|/
3 |
\|/
\|/
Q.rear -> 9 /\ 队尾
Q.front -> |
\|/
1 | 队头
\|/
2 |
\|/
3 |
\|/
\|/
Q.rear -> 9 /\ 队尾
链队列表示和实现：
//存储表示
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//操作说明
Status InitQueue(LinkQueue &Q)
//构造一个空队列Q
Status Destroyqueue(LinkQueue &Q)
//队列Q存在则销毁Q
Status ClearQueue(LinkQueue &Q)
//队列Q存在则将Q清为空队列
Status QueueEmpty(LinkQueue Q)
// 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
Status QueueLenght(LinkQueue Q)
// 队列Q存在,返回Q的元素个数,即队列的长度
Status GetHead(LinkQueue Q,QElemType &e)
//Q为非空队列,用e返回Q的队头元素
Status EnQueue(LinkQueue &Q,QElemType e)
//队列Q存在,插入元素e为Q的队尾元素
Status DeQueue(LinkQueue &Q,QElemType &e)
//Q为非空队列,删除Q的队头元素,并用e返回其值
Status QueueTraverse(LinkQueue Q,QElemType vivsit())
//Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
//操作的实现
Status InitQueue(LinkQueue &Q) {
//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;}
Status Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;}
Status EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
Status DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;}
三、总结
链队列的存储表示
链队列的操作及实现
#include
#include
// 链表队列
typedef struct Qnode{
int data;
struct Qnode *next;
}Qnode,*QueuePtr;//创建链
typedef struct {
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;//创建队列
void EnQueue(LinkQueue &Q,int e)
{
QueuePtr p=(QueuePtr)malloc(sizeof(Qnode));
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}//插入e为队尾元素
void DeQueue(LinkQueue &Q, int &e)
{
if(Q.front==Q.rear) printf("error\n");
QueuePtr p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
}//删除队头元素
int QueueEmpty(LinkQueue Q)
{
if(Q.front==Q.rear) return 1;
else return 0;
}//判断链栈是否为空
void InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));
Q.front->next=NULL;
printf("输入6个队列元素：");
for(int i=0;i<6;i++)
{
int a;
scanf("%d",&a);
EnQueue(Q,a);//向队列中插元素
}
}//初始化栈
void Print(LinkQueue Q)
{
while(!QueueEmpty(Q))
{
int e;
DeQueue(Q,e);
printf("%d ",e);
}
}//输出栈元素
void DestroyQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
}//销毁链队列
int QueueLength(LinkQueue Q)
{
int j=0;
while(Q.front->next)
{
Q.front=Q.front->next;
j++;
}
return j;
}//求链栈长度
main()
{
int a;//存储链队列长度
LinkQueue Q;
InitQueue(Q);
a=QueueLength( Q);
Print (Q);
printf("链队列长%d",a);
return 0;
}
// 动态数组队列
#include
#include
using namespace std;
template
class Queue
{
private:
int rear,front;//队尾与队头指针
Type *elements;//顺序栈数组
int maxSize;//最大元素
int count;//元素个数
public:
Queue(int=10);//constructor
~Queue()
{
delete []elements;
}
void EnQueue(const Type&item);
Type DeQueue();
Type GetTop();
bool IsEmpty()
{
return count == 0;
//return rear==front;
}
bool IsFull()
{
//return (rear+1)%maxSize==front;
return count == maxSize;
}
void MakeEmpty()
{
front = 0;
rear = 0;
count = 0；
}
int Length()
{
//return (rear-front+maxSize)%maxSize;
return count;
}
};
template
{
elements=new Type[maxSize];
assert(elements!=0);
}
template
{
//assert(!IsFull());
if(IsFull())
{
Type * temp = new Type[100];
int n = count;
Type * src = elements;
Type * dec = temp;
while(n--)
{
*dec++ = *src++;
}
delete [] elements;
elements = NULL;
elements = temp;
maxSize = 100;
rear = count;
elements[rear]=item;
rear=(rear+1)%maxSize;
count++;
}
else
{
count++;
elements[rear]=item;
rear=(rear+1)%maxSize;
}
/*
rear=(rear+1)%maxSize;
elements[rear]=item;
*/
}
template
{
assert( !IsEmpty() );//非空时候执行
count--;
Type temp = elements[front];
front=(front+1)%maxSize;
return temp;
/*
front=(front+1)%maxSize;
return elements[front];
*/
}
template
{
assert( !IsEmpty() );
return elements[front];
/*
int t=(front+1)%maxSize;
return elements[t];
*/
}
int main()
{
Queue
for(int i=0;i<11;i++)
{
a.EnQueue(i);
}
cout<
{
cout<
}
cout<
}
“vector是单向开口的连续线性空间，deque则是一种双向开口的连续空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。vector当然也可以在头尾两端进行操作（从技术观点），但是其头部操作效率奇差，无法被接受。”
“deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入和移除操作，二在于deque没有所谓容量（capacity）概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样因为空间不足而重新分配一块更大空间然后复制元素，再释放就空间这样的事情在deque是不会发生的。”
“虽然deque也提供了Ramdon Acces Iterator，但它的迭代器并不是普通指针，其复杂度和vector也不是一个数量级上的，这当然也会影响到运算的各个层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector，将vector（利用STL Sort算法），再复制回deque。”
--以上摘自 侯捷 《STL源码剖析》 p143
deque，意为double ended queue（双端队列），常读作deck。其用法和大家熟知的vector类似，接口基本和vector雷同。至于二者的不同之处和孰优孰劣，上面摘录的侯大师书里说的也很明白。容器本身没有绝对的好坏，关键看应用环境和需要。
成员函数表如下：
函数
描述
assign(beg,end)
assign(n,elem)
将[beg; end) 区间中的数据赋值
将n个elem 的拷贝赋值
at(idx)
传回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range
back()
传回最后一个数据，不检查这个数据是否存在
begin()
传回迭代器重的可一个数据
clear()
移除容器中所有数据
deque c1(c2)
deque c(n)
deque c(n, elem)
deque c(beg,end)
~deque()
复制一个deque
创建一个deque,含有n个数据,数据均已缺省构造产生
创建一个含有n个elem 拷贝的 deque
创建一个以[beg;end)区间的 deque
销毁所有数据，释放内存
empty()
判断容器是否为空
end()
指向迭代器中的最后一个数据地址
erase(pos)
erase(beg,end)
删除pos位置的数据，传回下一个数据的位置
删除[beg,end)区间的数据,传回下一个数据的位置
front()
传回地一个数据
get_allocator
使用构造函数返回一个拷贝
insert(pos,elem)
insert(pos,n,elem)
insert(pos,beg,end)
在pos位置插入一个elem拷贝,传回新数据位置
在pos位置插入n 个elem数据,无返回值
在pos位置插入在[beg,end)区间的数据,无返回值
max_size()
返回容器中最大数据的数量
pop_back()
删除最后一个数据
pop_front()
删除头部数据
push_back(elem)
在尾部加入一个数据
push_front(elem)
在头部插入一个数据
rbegin()
传回一个逆向队列的第一个数据
rend()
传回一个逆向队列的最后一个数据的下一个位置
resize(num)
重新指定队列的长度
size()
返回容器中实际数据的个数
c1.swap(c2)
swap(c1,c2)
将 c1 和 c2 元素互换
同上操作
operator []
返回容器中指定位置的一个引用
延伸阅读：
（1）今天找到一个不得不用deque的理由 （无论是否赞同作者的观点，至少对理解deque是有益的）
（2）深入研究 C++中的 STL Deque 容器
#include
#include
using namespace std;
typedef deque
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with 3 A's
CHARDEQUE a(3,'A');
//create b with 4 B's.
CHARDEQUE b(4,'B');
//print out the contents
print_contents (a,"a");
print_contents (b,"b");
//swap a and b
a.swap(b);
print_contents (a,"a");
print_contents (b,"b");
//swap it back
a.swap(b);
print_contents (a,"a");
print_contents (b,"b");
//assign the contents of b to a
a.assign(b.begin(),b.end());
print_contents (a,"a");
//assign the first two items of b to a
a.assign(b.begin(),b.begin()+2);
print_contents (a,"a");
//assign 3 'Z's to a
a.assign(3,'Z');
print_contents (a,"a");
}
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout <<"The contents of "<< name <<" : ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<
#include
#include
using namespace std;
typedef deque
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with A, B, C and D
CHARDEQUE a;
a.push_back('A');
a.push_back('B');
a.push_back('C');
a.push_back('D');
//print out the contents
print_contents (a,"a");
cout <<"The first element of a is " <
CHARDEQUE::reference reffront=a.front();
CHARDEQUE::reference refback=a.back();
reffront='X';
refback='Y';
print_contents (a,"a");
}
// print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout << "The contents of " << name << ":";
for (pdeque = deque.begin(); pdeque != deque.end(); pdeque++)
cout << " " << *pdeque;
cout<
Copy CodeThe contents of a: A B C D The first element of a is A The last element of a is D The contents of a: X B C Y
#include
#include
using namespace std;
typedef deque
int main()
{
// Create A and fill it with elements 1,2,3,4 and 5
// using push_back function
INTDEQUE A;
A.push_back(1);
A.push_back(2);
A.push_back(3);
A.push_back(4);
A.push_back(5);
// Print the contents of A using iterator
// and functions begin() and end()
INTDEQUE::iterator pi;
for(pi= A.begin(); pi !=A.end(); pi++)
{
cout << *pi <<" " ;
}
cout<
Output1 2 3 4 5
#include
#include
using namespace std;
typedef deque
void print_contents (INTDEQUE deque);
int main()
{
// create a and with elements 1,2,3,4 and 5
INTDEQUE a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
//print the contents
print_contents (a);
// erase the second element
a.erase(a.begin()+1);
print_contents (a);
//erase the last two elements
a.erase(a.end()-2,a.end());
print_contents (a);
//clear a
a.clear();
print_contents (a);
}
void print_contents (INTDEQUE deque) {
INTDEQUE::iterator pdeque;
cout <<"The output is: ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<
Copy CodeThe output is: 1 2 3 4 5 The output is: 1 3 4 5 The output is: 1 3 The output is:
#include
#include
int main( )
{
using namespace std;
deque
// Create an empty deque c0
deque
// Create a deque c1 with 3 elements of default value 0
deque
// Create a deque c2 with 5 elements of value 2
deque
// Create a deque c3 with 3 elements of value 1 and with the
// allocator of deque c2
deque
// Create a copy, deque c4, of deque c2
deque
// Create a deque c5 by copying the range c4[_First, _Last)
c4_Iter = c4.begin( );
c4_Iter++;
c4_Iter++;
deque
// Create a deque c6 by copying the range c4[_First, _Last) and
// c2 with the allocator of deque
c4_Iter = c4.begin( );
c4_Iter++;
c4_Iter++;
c4_Iter++;
deque
cout << "c1 = ";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout << *c1_Iter << " ";
cout << endl;
cout << "c2 = ";
for ( c2_Iter = c2.begin( ); c2_Iter != c2.end( ); c2_Iter++ )
cout << *c2_Iter << " ";
cout << endl;
cout << "c3 = ";
for ( c3_Iter = c3.begin( ); c3_Iter != c3.end( ); c3_Iter++ )
cout << *c3_Iter << " ";
cout << endl;
cout << "c4 = ";
for ( c4_Iter = c4.begin( ); c4_Iter != c4.end( ); c4_Iter++ )
cout << *c4_Iter << " ";
cout << endl;
cout << "c5 = ";
for ( c5_Iter = c5.begin( ); c5_Iter != c5.end( ); c5_Iter++ )
cout << *c5_Iter << " ";
cout << endl;
cout << "c6 = ";
for ( c6_Iter = c6.begin( ); c6_Iter != c6.end( ); c6_Iter++ )
cout << *c6_Iter << " ";
cout << endl;
}
Outputc1 = 0 0 0 c2 = 2 2 2 2 2 c3 = 1 1 1 c4 = 2 2 2 2 2 c5 = 2 2 c6 = 2 2 2
#include
#include
using namespace std;
typedef deque
void print_contents (CHARDEQUE deque);
int main()
{
//create a with 3 A's
CHARDEQUE a(3,'A');
//create b with 2 B's.
CHARDEQUE b(2,'B');
//print out the contents
print_contents (a);
print_contents (b);
//insert 'X' to the beginning of a
a.insert(a.begin(),'X');
print_contents (a);
//insert 'Y' to the end of a
a.insert(a.end(),'Y');
print_contents (a);
//inset 3 'Z's to one item before the end of a
a.insert(a.end()-1,3,'Z');
print_contents (a);
//insert to the end of a from b
a.insert(a.end(),b.begin(),b.end());
print_contents (a);
}
//function to print the contents of deque
void print_contents (CHARDEQUE deque)
{
CHARDEQUE::iterator pdeque;
cout <<"The output is: ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<
OutputThe output is: A A A The output is: B B The output is: X A A A The output is: X A A A Y The output is: X A A A Z Z Z Y The output is: X A A A Z Z Z Y B B
#include
#include
using namespace std;
typedef deque
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create an empty deque a
CHARDEQUE a;
//check whether it is empty
if(a.empty())
cout<<"a is empty"<
cout<<"a is not empty"<
a.push_back('A');
a.push_back('B');
a.push_back('C');
a.push_back('D');
//check again whether a is empty
if(a.empty())
cout<<"a is empty"<
cout<<"a is not empty"<
print_contents (a,"a");
cout <<"The first element of a is " <
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout <<"The contents of "<< name <<" :";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout <<" " << *pdeque;
}
cout<
Copy Codea is empty a is not empty The contents of a : A B C D The first element of a is A The first element of a is A The last element of a is D The last element of a is D
#include
#include
using namespace std;
typedef deque
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with 3 A's
CHARDEQUE a(3,'A');
a.push_front('C');
//create b with 4 B's.
CHARDEQUE b(6,'B');
//print out the contents
print_contents (a,"a");
print_contents (b,"b");
//compare a and b
if (a==b)
cout <<"a is equal to b"<
cout <<"a is greater than b" <
a.assign(b.begin(),b.end());
print_contents (a,"a");
print_contents (b,"b");
//compare a and b again
if (a==b)
cout <<"a is equal to b"<
cout <<"a is greater than b" <
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout <<"The contents of "<< name <<" : ";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <<" " ;
}
cout<
OutputThe contents of a : C A A A The contents of b : B B B B B B a is greater than b The contents of a : B B B B B B The contents of b : B B B B B B a is equal to b
#include
#include
using namespace std;
typedef deque
void printcontents (INTDEQUE deque);
int main()
{
INTDEQUE dequetest;
dequetest.push_back(1);
dequetest.push_back(2);
dequetest.push_back(3);
printcontents (dequetest);
dequetest.pop_back();
printcontents (dequetest);
dequetest.pop_back();
printcontents (dequetest);
}
//function to print the contents of deque
void printcontents (INTDEQUE deque)
{
INTDEQUE::iterator pdeque;
cout <<"The output is:"<
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <
}
OutputThe output is: 1 2 3 The output is: 1 2 The output is: 1
#include
#include
using namespace std;
typedef deque
void printcontents (INTDEQUE deque);
int main()
{
INTDEQUE dequetest;
dequetest.push_front(1);
dequetest.push_front(2);
dequetest.push_front(3);
printcontents (dequetest);
dequetest.pop_front();
printcontents (dequetest);
dequetest.pop_front();
printcontents (dequetest);
}
//function to print the contents of deque
void printcontents (INTDEQUE deque)
{
INTDEQUE::iterator pdeque;
cout <<"The output is:"<
pdeque != deque.end();
pdeque++)
{
cout << *pdeque <
}
OutputThe output is: 3 2 1 The output is: 2 1 The output is: 1
#include
#include
using namespace std;
typedef deque
int main()
{
// Create A and fill it with elements 1,2,3,4 and 5
// using push_back function
INTDEQUE A;
A.push_back(1);
A.push_back(2);
A.push_back(3);
A.push_back(4);
A.push_back(5);
// Now print the contents in reverse order using reverse_iterator
// and functions rbegin() and rend()
INTDEQUE::reverse_iterator rpi;
cout << "Contents in reverse order:";
for(rpi= A.rbegin(); rpi !=A.rend(); rpi++)
cout << " " << *rpi;
cout<
OutputContents in reverse order: 5 4 3 2 1
#include
#include
using namespace std;
typedef deque
void print_contents (CHARDEQUE deque, char*);
int main()
{
//create a with A, B, C and D
CHARDEQUE a;
a.push_back('A');
a.push_back('B');
a.push_back('C');
a.push_back('D');
//print out the contents
print_contents (a,"a");
cout <<"max_size of a is " <
// and set the new elements to be 'X'
a.resize(10,'X');
print_contents (a,"a");
cout <<"size of a is " <
a.resize(5);
print_contents (a,"a");
cout <<"size of a is " <
//function to print the contents of deque
void print_contents (CHARDEQUE deque, char *name)
{
CHARDEQUE::iterator pdeque;
cout << "The contents of " << name << " :";
for(pdeque = deque.begin();
pdeque != deque.end();
pdeque++)
{
cout << " " << *pdeque ;
}
cout<
Sample OutputThe following output is for x86.
Copy CodeThe contents of a : A B C D max_size of a is 4294967295 size of a is 4 The contents of a : A B C D X X X X X X size of a is 10 The contents of a : A B C D X size of a is 5 max_size of a is still 4294967295
queue普通队列以deque双端队列为底层架构，成员函数表如下：Constructors
queue
Constructs a queue that is empty or that is a copy of a base container object.
Typedefscontainer_type
A type that provides the base container to be adapted by the queue.
size_type
An unsigned integer type that can represent the number of elements in a queue.
value_type
A type that represents the type of object stored as an element in a queue.
Member Functionsback
Returns a reference to the last and most recently added element at the back of the queue.
empty
Tests if the queue is empty.
front
Returns a reference to the first element at the front of the queue.
pop
Removes an element from the front of the queue.
push
Adds an element to the back of the queue.
size
Returns the number of elements in the queue.
#include
#include
using namespace std;
void main()
{
queue
queue
q.push(3);
q.push(19);
while(!q.empty())
{
cout<
}
if(q1.size() < 50)
{
q1.push(45);
q1.push(68);
}
while(!q1.empty())
{
cout<
}
}
priority_queue队列，以Vector为架构，用堆排序的方式实现队列元素的有序（默认从高到低）// Functions:
// priority_queue::push(), priority_queue::pop(),
// priority_queue::empty(), priority_queue::top(), queue::size()
#include
#include
#include
#include
#include
using namespace std ;
// Using priority_queue with deque
// Use of function less sorts the items in ascending order
typedef deque
typedef priority_queue
// Using priority_queue with vector
// Use of function greater sorts the items in descending order
typedef vector
typedef priority_queue
int main(void)
{
size_t size_q;
INTPRQUE q;
CHPRQUE p;
// Insert items in the priority_queue(uses deque)
q.push(42);
q.push(100);
q.push(49);
q.push(201);
// Output the item at the top using top()
cout << q.top() << endl;
// Output the size of priority_queue
size_q = q.size();
cout << "size of q is:" << size_q << endl;
// Output items in priority_queue using top()
// and use pop() to get to next item until
// priority_queue is empty
while (!q.empty())
{
cout << q.top() << endl;
q.pop();
}
// Insert items in the priority_queue(uses vector)
p.push('c');
p.push('a');
p.push('d');
p.push('m');
p.push('h');
// Output the item at the top using top()
cout << p.top() << endl;
// Output the size of priority_queue
size_q = p.size();
cout << "size of p is:" << size_q << endl;
// Output items in priority_queue using top()
// and use pop() to get to next item until
// priority_queue is empty
while (!p.empty())
{
cout << p.top() << endl;
p.pop();
}
}
Output201 size of q is:4 201 100 49 42 a size of p is:5 a c d h m
(数据结构复习)链队列和动态数组队列以及STL中的deque双端队列和Queue普通队列,堆排序队列priority_queue
Deque双端队列界面
中国人民解放军队列
队列条令
消息队列的使用
linux消息队列操作
关于等待队列和信号量的好文章
Qt子线程“信号队列”
来点儿队列操练如何
linux进程的休眠（等待队列）
中国人民解放军队列条令(全文) - 中国网
中国人民解放军队列条令(全文) 1- 中国网
中国人民解放军队列条令(全文) 2- 中国网
linux消息队列与共享内存编程 [
中国人民解放军三大条令之队列条令
Linux内核中等待队列的几种用法
解放军仪仗队列亮相委内瑞拉将列庆典第一方阵
超级震撼！放生的鱼集体做队列表演谢恩！
Java 理论与实践: 线程池与工作队列
【转】linux的消息队列与共享内存编程
标题: 实时SIGIO队列与sigwaitinfo的结合使用（提高socket服务能力）
超级震撼！中秋放生的鱼集体做队列表演谢恩 - 在线视频 - 蒲公英光之维度
超级震撼：放生的鱼集体做殊胜的队列表演谢恩！
超级震撼！中秋放生的鱼集体做队列表演谢恩 - 在线视频