C++笔记2 | 队列

队列的基本概念

队列的基本概念——队列的定义

先进先出 (First In First Out) 限制访问点的线性表 按照到达的顺序来释放元素。所有的插入在表的一端进行，所有的删除都在表的另一端进行

•主要元素
队头 (front)
队尾 (rear)
队列(Queue)：具有一定操作约束的线性表
插入和删除操作：只能在一端插入，而在另一端删除。

队列的基本概念——队列的基本操作

创建队列、入队操作、计算队列的长度、出队操作、判断队列是否为空

队列的基本概念——队列的抽象数据类型

template <class T> 
class Queue 
{ 
        public:
          void clear(); 
          bool enQueue(const T item) ; 
          bool deQueue(T & item) ; 
           bool getFront(T & item); 
           bool isEmpty(); 
           bool isFull(); 
}; 

队列的基本概念——队列的实现方式

顺序队列
队列的顺序存储实现。
通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
关键是如何防止假溢出
固定的存储空间

链式队列
队列的链式存储结构。
可以用一个单链表实现。插入和删除操作分别在链表的两头进行，队列中每个元素对于链表中的一个结点
可以满足大小无法估计的情况

用数组模拟普通队列

设两个指针front，rear：
rear指示队尾元素位置
front指示对头元素位置
初值front=rear=0
空队列条件：
front==rear
入队列：q[rear++]=x;
出队列：x=q[front++];

用数组模拟队列——练习

#include<iostream>
using namespace std;
int main()
{
 int n,m,i,j,a[10000],front=0,rear=0;
 cin>>n>>m;
 for(i=0;i<n;i++)
 {  a[rear++]=i+1; } 
 while(front<rear)
 { 	j=m;
	while(j>1)
	{	a[rear++]=a[front++];
		j--;	}
 	front++; }
 cout<<a[rear-1]<<endl;//rear指针指向可插入新元素的位置，因此剩下的数字存储在rear-1中 
 return 0;
}

模拟环形队列

#include<iostream>
using namespace std;
int main()
{ int n,m,i,x,a[10000],front=0,rear=0,ans;
 cin>>n>>m;
 for(i=0;i<n;i++)
 {  a[i]=i+1; } 
 rear=n;
 while(rear!=front)
 {
 	for(int i=1;i<m;i++)
 	{	x=a[front];//对于报数不是m的，插到队尾，指针下移
 		front=(front+1)%n; //当指针移满一圈后，重新开始编号 
 		a[rear]=x;
 		rear=(rear+1)%n;//当指针移满一圈后，重新开始编号	}
	 ans=a[front];
	 front=(front+1)%n;
}
 cout<<ans<<endl;//rear指针指向可插入新元素的位置，因此剩下的数字存储在rear-1中 
 return 0;}

STL模板库中队列的基本操作

queueq：创建一个空队列。
q.size()：返回q队列中元素的个数，即队列的长度。
q.push(x)：插入元素x为新的队尾元素。
q.pop()：删除q队列的队首元素。
q.empty()：判断队列是否为空，为空返回true，否则返回false。
q.front()：获取队首元素的值。
q.back()：获取队尾元素的值。