队列的顺序、链式表示与实现_1. 创建队列的接口。 2. 队列的顺序实现。 3. 队列的链式实现。 4. 用队列求解素

       上期说到栈，是一种“先进后出”的线性表，今天我们来剖析一下一种 “ 先进先出 ” 的数据结构：队列。

队列也有顺序表示和链式表示。

一、队列的顺序表示

1.队列的顺序存储结构

   队列同样需要用头（head）尾（tail）指针

#define MAXSIZE 100
typedef struct{
  qelemType *base;//循环队列存储的基地址
  int head;//头指针
  int tail;//尾指针
}sqQueue;

2.初始化

（1）为队列动态分配一个大小为MAXSIZE的数组空间

（2）base指向数据空间的首地址

（3）头尾指针置0

#define status int
#define qelemType int
status init_Queue(sqQueue &Q){
  Q.base=new qelemType[MAXSIZE];
  if(!Q.base)
     return 0;
  Q.head=Q.tail=0;
  return 1;
}

3.获得队列长度

（1）对于非循环队列，头尾指针差值即为长度

（2）对于循环队列，差值可能<0，故差值加上MAXSIZE后在对MAXSIZE求余

        Eg：head=5；tail=1；MAXSIZE=10；（head-tail）= -4；

               进行上述操作得：length=6

int queue_Length(sqQueue Q){
  return(Q.tail-Q.head+MAXSIZE)%MAXSIZE;
}

4.入队

（1）判断队列是否满队

（2）将新元素插入队尾

（3）队尾指针+1

status queue_Insert(sqQueue &Q,qelemType e){
  if((Q.tail+1)%MAXSIZE==Q.head)
     return 0;
  Q.base[Q.tail]=e;
  Q.tail=(Q.tail+1)%MAXSIZE;
  return 1;
}

5.出队

（1）判断队列是否满队

（2）保存队头（head）

（3）队头指针+1

status queue_Delete(sqQueue &Q,qelemType &e){
  if(Q.head==Q.tail)
     return 0;
  e=Q.base[Q.head];
  Q.head=(Q.head+1) %MAXSIZE;
  return 1;
}

6.取队头元素

（1）判断队列是否为空，若不为空，执行一下操作

         返回队头元素的值，头指针不变

#define selemType int
selemType get_Queue_Head(sqQueue Q){
  if(Q.head!=Q.tail)
     return Q.base[Q.head];
}

当用户无法提前获知队列的最大长度时，应采用队列的链式结构

二、队列的链式表示（通常用单链表表示）

注：与栈的链式存储表示不同的是，队列的链式表示需要两组指针

1.队列的链式存储结构

#define qelemType int
#define queuePointer int
typedef struct{
  qelemType data;//节点数据域
  struct QNode *next;//节点指针域
}QNode,*queuePointer;//queuePointer为指向qNode结构的指针类型
 
typedef struct{
  queuePointer head;//头指针
  queuePointer tail;//尾指针
}queueLink;

2.初始化

（1）生成一个新的节点作为头结点

（2）队头与队尾指向这个新节点

（3）头结点指针域置空

#define status int
status init_Link_Queue(queueLink &Q){
  Q.head=Q.tail=new QNode;
  Q.head->next=NULL;//置空
  return 1;
}

3.入队

（1）用指针p指向即将入队的元素 并 动态分配内存空间

（2）新节点的数据域置为e

（3）将新节点插入到队尾

（4）将队尾指针修改为p

status link_Queue_Insert(queueLink &Q,qelemType e){
  queueLink p=new QNode;
  p->data=e;
  p->next=NULL;
  Q.head->next=p;
  Q.head=p;
  return 1;
}

4.出队

（1）判断队列是否为空

（2）保存队头元素的内存空间

（3）修改头节点的指针域，使其指向像一个节点

（4）判断出队元素是否为最后一个，若是，将尾指针重新赋值并指向头结点；若否（5）

（5）释放保存的队头元素的内存空间

status link_Queue_Delete(queueLink &Q,qelemType &e){
  queueLink p;
  if(Q.head==Q.tail)
     return 0;
  p=Q.head->next;
  e=p->data;
  Q.head->next=p->next;
  if(Q.head==p)
     Q.head=Q.tail;
  delete p;
  retunr 1;
}

5.取队头元素

（1）判断队列是否为空，若否（2）

（2）返回当前队头元素的value，队头指针不变

#define selemType int
selemType get_Link_Queue_Head(queueLink Q){
  if(Q.head!=Q.tail)
     return Q.head->next->data;
}