队列也是一种特殊的 “表”，使用队列时插入是在一端操作,而删除则是在另外一端
队列的基本操作是enqueue(入队)，它是在表的末端（称为队尾)插入--个元素;dequeue(出队)，它是删除（并返回)表的开头(叫作队头）的元素。下图显示了一个队列的抽象模型。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct Node{
int val;
Node* next;
Node(int v){
val = v;
next = NULL;
}
};
class Queue{
int size;
Node* head; //pointer to the font node
Node* back; //pointer to the least node
public:
Queue(){
size = 0;
head = back = NULL;
}
bool empty(){
return size == 0;
}
Node* front(){
return head;
}
Node* push_back(int v){
if (size == 0){
//note that head-next should give valuation after head
head->next = head = back = new Node(v);
}
else if (size == 1){
head->next = back = new Node(v);
}
else {
back->next = new Node(v);
back = back->next;
}
size++;
return back;
}
//delete the font node
void pop(){
if (empty()) return;
Node* temp = head;
head = head->next ;
delete temp;
size--;
}
};
void test_queue(){
Queue queue;
int n;
cin >> n;
for (int i = 0; i < n; i++){
int temp;
cin >> temp;
queue.push_back(temp);
}
//you have to judge if queue is empty before using this font node
while (queue.empty() == false){
cout << queue.front()->val << endl;
queue.pop();
}
return;
}
int main(){
test_queue();
return 0;
}
2.用数组实现
对于每一个队列数据结构，我们保留一个数组theArray以及位置front和back，它们代表队列的两端。我们还要记录实际存在于队列中的元素的个数currentsize。下图表示处于某个中间状态的一个队列。
操作应该是清楚的。要enqueue元素x，可将currentsize和 back增1，然后置theArray[back]=x。要dequeue一个元素，可以置返回值为theArray[front]，将currentsize减1，再将front增1。其他的方法也可以使用（将在后面讨论)。现在论述错误的检测。
这种实现存在一个潜在的问题。经过10次enqueue后，队列似乎是满了，因为back现在是数组的最后一个下标，而下一次执行enqueue就会是一个不存在的位置。然而，队列中也许只存在几个元素，因为若干元素可能已经出队了。像栈一样，即使在有许多操作的情况下队列也常常不是很大。
简单的解决方法是，只要front或back到达数组的尾端，就绕回到开头。下列图显示了在某些操作期间的队列情况。这称为循环数组(circular array）实现可以看成换环队列。
环形队列与普通队列的区别：
1.front头部指针
一般队列：front头部指针初始值为-1，从队列取数据时，该值依次递增，指向的元素即待取出的数据，而队列的头部数据所在的指针位置为front+1。当front=maxSize-1时，队列最后一个数据取出，此时队列为空。
环形队列：front头部指针初始值为0，指向的元素既是队列的头部数据也是待取出的数据。从队列取数据时，因逻辑上的闭环，指针可能再次回到前面的位置，不能单一递增处理，需通过取模来重新计算指针的值。
2.rear尾部指针
一般队列：rear尾部指针初始值为-1，队列添加数据时，该值依次递增，当rear=maxSize-1时，队列满，无法再添加数据。
环形队列：rear尾部指针初始值为0，指向待添加数据的位置，队列添加数据时，因逻辑上的闭环，指针可能再次回到前面的位置，不能单一递增处理，会出现角标越界异常，需通过取模来重新计算指针的值。
3.队列空的判断逻辑
一般队列：rear == front时，队列空。
环形队列：rear == front时，队列空。
4.队列满的判断逻辑
一般队列：rear = maxSize - 1时，队列满。
环形队列：(rear + 1) % maxSize == front时，队列满。
代码实现：
#include <iostream>
#include <cstdlib>
#include <memory.h>
class Ciclequeue
{
public:
//队列最大容量
int m_maxSize;
//队列头指针
int m_frontIdx;
//队列尾指针
int m_rearIdx;
//队列数组
int *m_queueArr;
public:
//构造函数
Ciclequeue(int tmpSize)
{
m_maxSize = tmpSize;
m_frontIdx = 0;
m_rearIdx = 0;
m_queueArr = new int[m_maxSize];
memset(m_queueArr, 0 , sizeof(int)*m_maxSize);
}
//析构函数
~Ciclequeue()
{
delete m_queueArr;
m_queueArr = NULL;
}
//入队
void enqueue(int datavalue)
{
if(isfull())
{
std::cout<<"Queue is full!"<<std::endl;
return;
}
m_queueArr[m_rearIdx] = datavalue;
m_rearIdx = (m_rearIdx + 1)%m_maxSize;
}
//出队
void dequeue()
{
if(isempty())
{
std::cout<<"Queue is empty!"<<std::endl;
return;
}
m_queueArr[m_frontIdx] = -1; //模拟出队列动作
m_frontIdx = (m_frontIdx + 1)%m_maxSize;
}
//检查队列是否已满
bool isfull()
{
if(m_maxSize == -1)
{
std::cout<<"Create queue error!"<<std::endl;
return false;
}
return (m_rearIdx + 1)%m_maxSize == m_frontIdx;
}
//检查队列是否为空
bool isempty()
{
if(m_maxSize == -1)
{
std::cout<<"Create queue error!"<<std::endl;
return false;
}
return m_rearIdx == m_frontIdx;
}
//当前队列元素各个数
int size()
{
return (m_rearIdx - m_frontIdx + m_maxSize) % m_maxSize;
}
//显示队列
void showqueue()
{
if(isempty())
{
return;
}
for(int i = m_frontIdx; i < m_frontIdx + size(); i++ )
{
std::cout<<m_queueArr[i]<<" "<<std::endl;
}
}
//显示队列头
void showqueuefront()
{
std::cout<<m_queueArr[m_frontIdx]<<std::endl;
}
};
int main(int argc, char **argv)
{
int tmpSize = std::atoi(argv[1]);
if(tmpSize <= 0)
{
std::cout<<"Set MaxSize Error!"<<std::endl;
return 0;
}
Ciclequeue *testqueue = new Ciclequeue(tmpSize);
testqueue->enqueue(3);
testqueue->enqueue(2);
testqueue->dequeue();
testqueue->enqueue(4);
testqueue->dequeue();
testqueue->enqueue(5);
testqueue->enqueue(66);
testqueue->enqueue(88);
testqueue->enqueue(1204);
testqueue->showqueue();
delete testqueue;
testqueue = NULL;
return 0;
}
关于计算机网络的。有许多种PC机的网络设置，其中磁盘是放一台叫作文件服务器(file server)的机器上的。使用其他计算机的用户是按照先到先使用的原则访问文件的,
因此其数据结构是一个队列
升级：
一个称为排队论(queuing theory)的数学分支用概率的方法处理--些诸如计算用户预计要排队等待的时间、等待的队伍能够排多长等类问题。问题的答案依赖于用户加入队列的频率以及-一旦用户得到服务时处理服务花费的时间。这两个参数作为概率分布函数给出。在一些简单的情况下，答案可以解析地算出。一种简单的例子是条电话线有一个接线员。如果接线员忙，打来的电话就被放到个等待队列中（这还与某个容许的最大限度有关)。这个问题在商业上很重要，因为研究表明，人们会很快挂上电话。如果有k个接线员，那么这个问题解决起来要困难得多。解析求解困难的问题往往使用模拟的方法求解。此时，需要使用一个队列来进行模拟。如果k很大，那么还需要其他一些数据结构来使得模拟更有效地进行。
关注我一起学！！！