数据结构（C语言版）---队列

标签：队列的顺序存储   初始   链式存储   amp   als   判断   fine   int   计数   

1、队列：在表的一端插入，表的另一端删除，允许插入的一端为队尾，允许删除的一端为队头。先进先出FIFO。

2、队列的基本操作

InitQueue(&Q)：构造空队列

DestroyQueue(&Q)：销毁队列

ClearQueue(&Q)：清空队列

QueueEmpty(Q)：判断队列是否为空

QueueLength(Q)：求队列长度

GetHead(Q,&e)：用e返回队列的队头元素

EnQueue(&Q,e)：插入e作为队列的新队尾

DeQueue(&Q,&e)：删除队头元素，并用e返回

3、队列的顺序存储：连续的存储单元，附设两个指针front指示队头元素，rear指示队尾元素的下一个位置

1）循环队列：将顺序队列变成环状空间。

（1）初始化建空队列时：front=rear=0

（2）每当插入新的队列尾元素时，rear=(rear+1)%maxsize

（3）每当删除队头元素时，front=(front+1)%naxsize

（4）在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

（5）队列长度：(rear+maxsize-front)%maxsize

2）判别队列空间是“空”还是“满”。

（1）设一个标志位tag以区别队列是“空”还是“满”，初始tag=0，入队成功tag=1，出队成功tag=0。

         队空：因删除元素导致rear==front&&tag==0；队满：因插入元素导致rear==front&&tag==1

（2）少用一个元素空间，约定以“队列头指针在队列尾指针的下一个位置（指环状的下一个位置）上”作为队列“满”的标志。

         队空：rear==front；队满：(rear+1)%maxsize==front；队中元素的个数：(rear+maxsize-front)%maxsize

（3）设置计数器count，初始count=0，入队成功count+1，出队成功count-1。

          队空：count==0；队满：count>0&&rear==front

3）队列的顺序存储类型描述
#define Maxsize 50
typedef struct {
 int data[Maxsize];
 int front, rear;
 int tag = 0;//如果不需要设置标志位可以不声明。
}SqQueue;
初始状态（队空条件）：Q.front==Q.rear==0；进队操作：队不满时，插入队尾，队尾指针+1；出队操作：队不空时，取队头元素的值，头指针+1。
4）顺序存储时一些基本操作的实现

（1）初始化
void initqueue(SqQueue &Q)
{
 Q.rear = Q.front = 0;
}
（2）判断队列为空
bool queueempty(SqQueue Q)
{
 if (Q.rear == Q.front)
 {
  return true;
 }
 else
 {
  return false;
 }
}
（3）入队
bool enqueue(SqQueue & Q,int e)
{
 if ((Q.rear + 1) % Maxsize == Q.front)
 {
  return false;
 }
 Q.data[Q.rear] = e;
 Q.rear = (Q.rear + 1) % Maxsize;
 return true;
}
（4）设有tag标志的循环队列入队
bool enqueue2(SqQueue & Q, int e)
{
 if (Q.front == Q.rear&&Q.tag == 1)
 {
  return false;
 }
 Q.data[Q.rear] = e;
 Q.rear = (Q.rear + 1) % Maxsize;
 Q.tag = 1;
 return true;
}
（5）出队
bool dequeue(SqQueue &Q, int &e)
{
 if (Q.rear == Q.front)
 {
  return false;
 }
 e = Q.data[Q.front];
 Q.front = (Q.front + 1) % Maxsize;
 return true;
}
（6）设有tag标志的循环队列出队
bool dequeue2(SqQueue &Q, int &e)
{
 if (Q.front == Q.rear&&Q.tag == 0)
 {
  return false;
 }
 e = Q.data[Q.front];
 Q.front = (Q.front + 1) % Maxsize;
 Q.tag = 0;
 return true;
}

4、双端队列：限定插入和删除操作在表的两端进行的线性表。

1）输出受限的双端队列：一个端点允许插入和删除，另一个端点只允许插入。

2）输入受限的双端队列：一个端点允许插入和删除，另一个端点只允许删除。

5、队列的链式存储

1）链队列：用链表表示的队列，一个含有头指针（指向队头结点）和尾指针（指向队尾结点）的单链表。

2）当链队列有头结点时，当尾指针和头指针均指向头结点，则链队列尾空。

3）队列的链式存储类型描述
typedef struct {
 int data;
 struct Linkqueuenode *next;
}Linkqueuenode;
typedef struct {
 Linkqueuenode *front, *rear;
}Linkqueue;
//Q.front==null&&Q.rear==null，链式队列为空。
4）链式存储时一些基本操作的实现

（1）初始化
void initqueue(Linkqueue &Q)
{
 Q.front = Q.rear = (Linkqueuenode *)malloc(sizeof(Linkqueuenode));
 Q.front->next = NULL;
}
（2）判断队列是否为空
bool queueempty(Linkqueue Q)
{
 if (Q.rear == Q.front)
 {
  return true;
 }
 else
 {
  return false;
 }
}
（3）入队
void enqueue(Linkqueue &Q, int e)
{
 Linkqueuenode *s = (Linkqueuenode *)malloc(sizeof(Linkqueuenode));
 s->data = e;
 s->next = NULL;
 Q.rear->next = s->next;
 Q.rear = s;
}
（4）出队
bool dequeue(Linkqueue &Q, int &e)
{
 if (Q.front == Q.rear)
 {
  return false;
 }
 Linkqueuenode *p = Q.front;
 e = p->data;
 Q.front->next = p->next;
 if (Q.rear == p)
 {
  Q.rear = Q.front;
 }
 free(p);
 return true;
}

数据结构（C语言版）---队列

标签：队列的顺序存储   初始   链式存储   amp   als   判断   fine   int   计数   

原文地址：https://www.cnblogs.com/xqy1874/p/12746000.html