队列

1、队列的定义
队列（Queue）是一种先进先出的线性表（First In Frist Out，简称FIFO）。只允许在表的一端（front）进行删除，另一端（rear）进行插入。
队首（front）：只允许进行删除的一端
队尾（rear）：只允许进行插入的一端
队列中没有元素的时候成为空队列。在空队列中依次加入元素a1,a2,...,an之后，a1是队首元素，an是队尾元素。所以退出队列的次序是a1,a2,...,an，按照先进先出的原则进行。

队列.jpg
2.队列的主要操作
（1）清空队列
（2）判断是否为空
（3）元素的个数
（4）入队列
（5）出队列
（6）取队头元素
3.顺序实现队列
队列数组实现.png
存在问题
设数组长度为M,则：
当front=0，rear=M，再有元素入队时发生溢出----真溢出
当front!=0，rear=M，再有元素入队时发生溢出----假溢出
解决方案
循环队列：把队列设想成环形，让sq[0]接在sq[m-1]之后，若rear+1==M，则令rear=0。
循环队列.png
顺序实现队列
（1）

struct DATA{
 string name;
 int age;
};
struct SQType
{
 DATA data[QUEUELEN];//队列数组
 int head;//队头
 int tail;//队尾
};

定义了队列结构的最大长度是QUEUELEN，队列结构的数据元素类型DATA，队列结构的数据结构类型SQType。在数据结构SQType中，data为数据元素，head是队首序号，tail是队尾序号。当head=0时，队列为空，当tail=QUEUELEN时表示队列满。

（2）初始化队列数据
<1>按符号常量QUEUELEN指定的大小申请一段内存空间，用来保存队列中的数据。
<2>设置head=0和tail=0，表示一个空栈。

SQType *SQTypeInit()
{
 SQType *q;
 if(q = new SQType)//申请队列的内存空间
 {
   q -> head = 0;//队首
   q -> tail = 0;//队尾
   return q;
 }
 else
 {
   return NULL;//返回空
 }
}

（3）判断空队列
判断空队列是判断一个队列结构是否为空。如果是空，此时队列可以进行入队操作，不可以进行出队操作。

int SQTypeIsEmpty(SQType *q)
{
 return(q -> head == q -> tail);
}

（4）判断满队列
判断满队列就是判断一个队列结构是否为满。满队列不可以进行入队操作，可以进行出队操作

int SQTypeIsFull(SQType *q)
{
 return(q -> tail == QUEUELEN);
}

（5）清空队列

void SQTypeClear(SQType *q)
{
 q -> head =0;
 q -> tail =0;
}

（6）释放空间
释放空间是释放队列结构所占用的内存空间，前面用new关键字分配的内存单元，可以用delete释放。

void SQTypeFree(SQType *q)
{
 if(q != NULL) delete q;
}

（7）入队列
<1>判断队尾，如果tail等于QUEUELEN，队列满不能插入数据。
<2>设置tail=tail+1
<3>将入队元素保存到tail指向的位置

int InSQType(SQType *q,DATA data)
{
 if(q -> tail == QUEUELEN)
  {
    cout<<"队列已满，操作失败！！"<<endl;
  }
 else
 {
    q -> data[q -> tail++] = data;
     return 1;
 }
}

（8）出队列
<1>判断队首head，如果head等于tail，则表示队列为空
<2>从队列首部取出队头元素（实际返回队头元素的指针）
<3>修改队首head的序号，指向后一个元素

DATA *OutSQType(SQType *q)
{
  if(q -> tail == q -> head)
    {
      cout<<"队列已空！操作失败！"<<endl;
      exit(0);
    }
  else
  {
    return &(q -> data[q -> head++]);
  }
}

（9）读节点数据
读节点数据就是读队头的数据

DATA *PeekSQType(SQType *q)
{
  if(SQTypeIsEmpty(q))
  {
    cout<<"空对列"<<endl;
    return NULL;
  }
  else
  {
    return &(q -> data[q -> head]);
  }
}

（10）计算队列长度
计算队列长度就是计算该队列中数据节点的个数。用队尾序号减去队首序号。

int SQTypeLen(SQType *q)
{
  return(q -> tail - q -> head);
}

源代码：http://pan.baidu.com/s/1qYKZG76
截图：

结果.png

4.链表实现队列

#include <stdio.h>
#include <stdlib.h>

#define Error(str) FatalError(str)
#define FatalError(str) fprintf(stderr, "%s\n", str),exit(1)

typedef int ElementType;
#define MAXQUEUE 10

typedef struct node
{
  ElementType data;
  struct node* nextNode;
}Node;

typedef struct queue
{
  Node* front; //队首指针
  Node* rear;//队尾指针
  int items;//队列中项目个数
}*ptrQueue;

typedef ptrQueue Queue;
int IsEmpty(Queue q);
int IsFull(Queue q);
Queue CreateQueue(void);
void DisposeQueue(Queue q);
void MakeEmpty(Queue q);
void Enqueue(ElementType x, Queue q);
ElementType Front(Queue q);
void Dequeue(Queue q);
ElementType FrontAndDequeue(Queue q);

int main(void)
{
  Queue sqQueue;
  
  sqQueue = CreateQueue();
  if(IsEmpty(sqQueue))
    printf("创建一个空队列");
  
  int value = 0;
  printf("队列中的数据为（front -> rear）: \n");
  while(!IsFull(sqQueue))
  {
    Enqueue(value*value, sqQueue);//入队
    printf("%d", value*value);
    value++;
  }
  printf("队列已满\n");

  ElementType frontQueue;
  frontQueue = Front(sqQueue);
  printf("对头元素为： %d\n",frontQueue);
  
  Dequeue(sqQueue);
  frontQueue = Front(sqQueue);
  printf("执行出队操作Dequeue之后，对头元素是： %d\n",frontQueue);
  DisposeQueue(sqQueue);
  return 0;
}

/***是否为空***/
int IsEmpty(Queue q)
{
  return q -> items == 0;
}

/***是否已满***/
int IsFull(Queue q)
{
  return q -> items == MAXQUEUE;
}

/***创建队列***/
Queue CreateQueue(void)
{
  Queue q;
  
  q = (Queue)malloc(sizeof(struct queue));
  if(NULL == q)
    Error("空间不足，队列分配内存失败！");

  q -> front = (Node*)malloc(sizeof(Node));
  if(NULL == q -> front)
    Error("空间不足，队列首节点内存分配失败！");
  
  q -> rear = (Node*)malloc(sizeof(Node));
  if(NULL == q -> rear)
    Error("空间不足，队列尾节点内存分配失败！");

  q -> items = 0;

  return q;
}

/***释放队列***/
void DisposeQueue(Queue q)
{
  MakeEmpty(q);
  free(q);
}

/***使队列为空***/
void MakeEmpty(Queue  q)
{
  if(q == NULL)
    Error("必须先使用CreateQueue创建队列！");

  while(IsEmpty(q))
    Dequeue(q);
}

/***入队***/
void Enqueue(ElementType x, Queue q)
{
  if(IsFull(q))
    Error("队列已满");
  
  Node* pnode;
  pnode = (Node*)malloc(sizeof(Node));
  if(NULL == pnode)
    Error("新节点分配内存失败！");

  pnode -> data = x;
  pnode -> nextNode = NULL;
  if(IsEmpty(q))
    q -> front = pnode;//队列为空数据插入队首位置
  else
    q -> rear -> next = pnode;//队列不为空，元素放在队尾指针的下一个位置
  q -> rear = pnode;//队列尾指针指向pnode节点
  q -> items++;//队列项目数加1

  return;
}

/***出队***/
void Dequeue(Queue q)
{
  if(IsEmpty(q))
    Error("队列本身为空");

  Node* pnode;
  pnode = q -> rear;
  q -> front = q -> front -> nextNode;
  free(pnode);

  q -> items--;
  if(q -> items == 0)
    q -> rear = NULL;

  return;
}

/***返回队列头元素***/
ElementType Front(Queue q)
{
  if(!IsEmpty(q))
    return q -> front -> data;
  Error("队列为空\n");

  return 0;
}

/***返回对头元素并使对头元素出队***/
ElementType FrontAndDequeue(Queue q)
{
  ElementType x;
  
  if(IsEmpty(q))
    Error("队列为空\n");
  else
  {
    q -> items--;
     x =q -> front -> data;
     q -> front = q -> front -> nextNode;
  }
  
  return x;
}

源代码：http://pan.baidu.com/s/1o8jkZcI
截图：

单链表实现队列.png
3.不使用动态创建内存（malloc）而是申请固定地址来实现队列

typedef struct qq_link_struct
{
  struct qq_link_struct *ptr;//相当于nextNode下一个节点
}qq_link_type;

typedef struct qq_struct
{
  qq_link_type head;//队列头指针
  qq_link_type tail;//队列尾指针
   int cnt;//记录队列数据个数
}qq_type;

（1）初始化队列

qq_type* qq_init(qq_type *q_ptr)
{
  q_ptr -> head.ptr = &q_ptr -> head;//
  q_ptr -> tail.ptr = &q_ptr -> head;//初始时队列为空，q_ptr的头指针。尾指针都指向head
  q_ptr -> cnt = 0;
  return q_ptr;
}

（2）插入数据

/***队列尾部只能进行插入**/
void qq_put(qq_type *q_ptr,qq_link_type * link_ptr)
{
  link_ptr -> ptr = &q_ptr -> head;//link指向插入数据
  q_ptr -> tail.ptr -> ptr = link_ptr;//队列尾部插入数据
  q_ptr -> tail.ptr = link_ptr;//改变队列尾指针
  q_ptr -> cnt++;
}

（3）取出数据

/***队列头部只能取数据***/
void* qq_get(qq_type * q_ptr)
{
  qq_link_type *ret_ptr = 0;
  if(q_ptr -> cnt > 0 )//cnt大于0队列才有数据可以取出来
  {
    ret_ptr = q_ptr -> head.ptr;//存放取出的数据
    q_ptr -> head.ptr = ret_ptr -> ptr;//改变队列头指针
    q_ptr -> cnt--;
    if(q_ptr -> cnt ==0)
    {
      q_ptr -> tail.ptr = &q_ptr -> head;//当队列中没有数据尾指针指向队列头
    }
  }
}