(40)4.30数据结构（队列）

1.队列的基本概念

2.队列的顺序

#define MaxSize 10
#define ElemType int
typedef struct
{
   ElemType data[MaxSize];
   int front, rear;
}SqQueue;
//1.初始化操作
void InitQueue(SqQueue& Q)
{
   //初始化队头，队尾指针指向0
   Q.rear = Q.front = 0;
}
//判断为空
bool QueueEmpty(SqQueue Q)
{
   if (Q.rear = Q.front) //队空条件
       return true;
   else
       return false;
}
void testQueue()
{
   SqQueue Q;
   InitQueue(Q);
   //..后续操作。。//
}
//2.入队
bool EnQueue(SqQueue& Q, ElemType x)
{
   if ((Q.rear + 1) % MaxSize == Q.front)
       return false; //队满则报错
   Q.data[Q.rear] = x; //新元素插入队尾
   Q.rear = (Q.rear + 1) % MaxSize;//队尾指针加1取模
   return true;
}
//3.出队(删除一个队头元素，并用x返回)
bool DEQueue(SqQueue& Q, ElemType& x)
{
   if (Q.rear == Q.front)
       return false;
   x = Q.data[Q.front];
   Q.front = (Q.front + 1) % MaxSize;
   return true;
}
//获得队头的元素值，用下返回
bool DEQueue(SqQueue& Q, ElemType& x)
{
   if (Q.rear == Q.front)
       return false; //队空则报错
   x = Q.data[Q.front];
   return true;
}

//队列元素个数：
//（rear+MaxSize-front)%MaxSize
//方案二判断队列已满/已空
typedef struct
{
   ElemType data[MaxSize];
   int front, rear;
   int size; //初始化时 rear=front=0; size=0;
}SqQueue;
//插入成功size++
//插入失败size--
//方案三判断队列已满/已空
typedef struct
{
   ElemType data[MaxSize];
   int front, rear;
   int tag;//最近进行的是删除/插入
}SqQueue;
//每次删除操作成功时，都令tag=0；
//每次删除操作失败时，都令tag=1；
//只有删除成功才能导致队空；
//只有插入成功才能导致队满；

//队满条件：
//front==rear&&tag==1;
//队空条件
//front==rear&&tag==0;

//其他出题方法
//指向尾指针元素指向的方向

4.在做题的时候要注意rear指针指向的位置

知识点小结

3.队列的链式实现

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

#define ElemType int

typedef struct LinkNode //链式队列结点
{
ElemType data;
struct LinkNode* next;
}LinkNode;

typedef struct //链式队列
{
LinkNode* front, * rear;//队列的队头和队尾指针

}LinkQueue;
//1.初始化（带头结点）
void InitQueue(LinkQueue& Q)
{
   //初始化front,rear 都指向头结点
   Q.rear = Q.front = (LinkNode*)malloc(sizeof(LinkNode));
   Q.front->next = NULL;
}

void testLinkQueue()
{
   LinkQueue Q; //声明一个队列
   InitQueue(Q); //初始化队列
   //。。。后续操作/
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{
   if (Q.rear = Q.front) //队空条件
       return true;
   else
       return false;
}
//初始化队列（不带头结点）
void InitQueue(LinkQueue& Q)
{
   //初始化 front rear 都指向NULL
   Q.rear = NULL;
   Q.front= NULL;
}
bool IsEmpty(LinkQueue Q)
{
   if (Q.front ==NULL)
       return true;
   else
       return false;
}
//2.入队（带头结点）
void EnQueue(LinkQueue& Q, ElemType x)
{
   LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
   s->data = x;
   s->next = NULL;
   Q.rear->next = s;
   Q.rear = s;
}
//入队（不带头结点）
void EnQueue(LinkQueue& Q, ElemType x)
{
   LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
   s->data = x;
   s->next = NULL;
   if (Q.front == NULL)//在空队列中插入第一个元素
   {
       Q.front = s; //修改队头尾指针
       Q.rear = s;
   }
   else
   {
       Q.rear->next = s; //新节点插入到rear 结点之后
       Q.rear = s; //修改rear 指针
   }
}
//出队（带头结点）

bool DeQueue(LinkQueue& Q, ElemType& x)
{
   if (Q.front == Q.rear)
       return false; //空队
   LinkNode* p = Q.front->next;
   x = p->data; //用变量x返回队头元素
   Q.front->next = p->next; //修改头结点的next指针
   if (Q.rear == p) //此次是最后一个结点出队
       Q.rear = Q.front; //修改rear指针
   free(p); //释放空间
   return true;
}
//队头元素出队（不带头结点）
bool DeQueue(LinkQueue& Q, ElemType& x)
{
   if (Q.front == NULL)
       return false; //空队
   LinkNode* p = Q.front; //p指向此次出队的结点
   x = p->data; //用变量x返回队头元素
   Q.front = p->next; //修改头结点的front指针
   if (Q.rear == p) //此次是最后一个结点出队
   {
       Q.rear = NULL; //front 指向 NULL
       Q.rear = NULL; //rear 指向NULL
   }
   free(p); //释放空间
   return true;
}