逻辑结构:队列是一种操作受限的线性表,只允许从队尾入队,从队首出队。这个情形类型与排队
物理结构:分为顺序存储结构(一般通过循环队列实现),链式存储结构
1.队列的顺序存储
接下来主要介绍的是循环队列
1.1循环队列的初始化
typedef struct Queue
{
int data[MaxSize];
int front;//队首指针
int rear;//队尾指针
}SqQueue;
//初始化队列
void InitQueue(SqQueue* Q)
{
Q->front = Q->rear = 0;
}
1.2判断队空
//队列的判空
bool Empty(SqQueue* Q)
{
if (Q->front == Q->rear)
{
return true;
}
else
{
return false;
}
}
1.3入队
//入队
bool EnQueue(SqQueue* Q)
{
//判断队列是否满了
if ((Q->rear + 1) % MaxSize == Q->front)
{
printf("队列已经满了\n");
return false;
}
int x = 0;
printf("请输入要插入的值:");
scanf("%d", &x);
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxSize;
return true;
}
1.4出队
//出队
bool DeQueue(SqQueue* Q,int* x)
{
//判断队列是否为空
if (Q->front == Q->rear)
{
return false;
}
(*x) = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
return true;
}
1.5读出队首元素
//获取队首元素
bool GetQueue(SqQueue* Q,int* x)
{
//判断队列是否为空
if (Q->front == Q->rear)
{
return false;
}
(*x) = Q->data[Q->front];
return true;
}
1.6求队列元素个数
//求队列元素个数
int Length(SqQueue* Q)
{
int len = ((Q->rear + MaxSize) - Q->front) % MaxSize;
return len;
}
1.7循环队列整体代码
//顺序队列(也可以看做是循环队列)
typedef struct Queue
{
int data[MaxSize];
int front;//队首指针
int rear;//队尾指针
}SqQueue;
//初始化队列
void InitQueue(SqQueue* Q)
{
Q->front = Q->rear = 0;
}
//队列的判空
bool Empty(SqQueue* Q)
{
if (Q->front == Q->rear)
{
return true;
}
else
{
return false;
}
}
//入队
bool EnQueue(SqQueue* Q)
{
//判断队列是否满了
if ((Q->rear + 1) % MaxSize == Q->front)
{
printf("队列已经满了\n");
return false;
}
int x = 0;
printf("请输入要插入的值:");
scanf("%d", &x);
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxSize;
return true;
}
//出队
bool DeQueue(SqQueue* Q,int* x)
{
//判断队列是否为空
if (Q->front == Q->rear)
{
return false;
}
(*x) = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
return true;
}
//获取队首元素
bool GetQueue(SqQueue* Q,int* x)
{
//判断队列是否为空
if (Q->front == Q->rear)
{
return false;
}
(*x) = Q->data[Q->front];
return true;
}
//求队列元素个数
int Length(SqQueue* Q)
{
int len = ((Q->rear + MaxSize) - Q->front) % MaxSize;
return len;
}
int main()
{
SqQueue Q;
int x = 0;
//初始化顺序队列
InitQueue(&Q);
//入队,入队5个元素
int i = 0;
for (i = 0; i < 5; i++)
{
EnQueue(&Q);
}
//出队一个元素
DeQueue(&Q,&x);
printf("出队元素大小为%d\n", x);
//获取当前队头元素
GetQueue(&Q,&x);
printf("当前队头元素大小为%d\n", x);
return 0;
}
2.队列的链式存储
2.1队列的初始化
//队列节点
typedef struct LinkNode
{
int data;
struct LinkNode* next;
}LinkNode;
typedef struct
{
LinkNode* front;//队首指针
LinkNode* rear;//队尾指针,这两个都是指向节点的指针
}LinkQueue;//LinkQueue是包含两个节点指针的结构体的结构体类型
//队列的初始化,带头结点
void InitQueue(LinkQueue** Q)//传递的是队首指针和队尾指针
{
(*Q)->front = (*Q)->rear = (LinkNode*)calloc(1, sizeof(LinkNode));
(*Q)->front->next = NULL;
}
int main()
{
LinkQueue* Q=(LinkQueue*)malloc(sizeof(LinkQueue));
int x = 0;
InitQueue(&Q);
return 0;
}
2.2队列的判空
//队列的判空操作
bool Empty(LinkQueue** Q)
{
if ((*Q)->front == (*Q)->rear)//还可以是Q->front->next==NULL;
{
return true;
}
else
{
return false;
}
}
2.3入队操作
//入队
void EnQueue(LinkQueue** Q)
{
//链表不存在队列已经满了,不需要判断
// 创建新节点
LinkNode* s = (LinkNode*)calloc(1, sizeof(LinkNode));
if (s == NULL)
{
return;
}
int x = 0;
printf("请输入要插入的节点的数据:");
scanf("%d", &x);
s->data = x;
s->next = NULL;
(*Q)->rear->next = s;
(*Q)->rear = s;
}
2.4出队操作
// 出队
bool DeQueue(LinkQueue** Q,int* x)
{
//先判断队列是否为空
if ((*Q)->front == (*Q)->rear)
{
return false;
}
//出队从队首开始,也就是头结点
LinkNode* p = (*Q)->front->next;//这个就是除头指针外队首的第一个节点地址
(*x) = p->data;
(*Q)->front->next = p->next;
if ((*Q)->rear==p)//出队的是最后一个节点,修改队尾指针到头结点
{
(*Q)->rear = (*Q)->front;
}
free(p);//释放掉这一块空间
return true;
}
2.5整体代码
//队列节点
typedef struct LinkNode
{
int data;
struct LinkNode* next;
}LinkNode;
typedef struct
{
LinkNode* front;//队首指针
LinkNode* rear;//队尾指针,这两个都是指向节点的指针
}LinkQueue;//LinkQueue是包含两个节点指针的结构体的结构体类型
//队列的初始化,带头结点
void InitQueue(LinkQueue** Q)//传递的是队首指针和队尾指针
{
(*Q)->front = (*Q)->rear = (LinkNode*)calloc(1, sizeof(LinkNode));
(*Q)->front->next = NULL;
}
//队列的判空操作
bool Empty(LinkQueue** Q)
{
if ((*Q)->front == (*Q)->rear)//还可以是Q->front->next==NULL;
{
return true;
}
else
{
return false;
}
}
//入队
void EnQueue(LinkQueue** Q)
{
//链表不存在队列已经满了,不需要判断
// 创建新节点
LinkNode* s = (LinkNode*)calloc(1, sizeof(LinkNode));
if (s == NULL)
{
return;
}
int x = 0;
printf("请输入要插入的节点的数据:");
scanf("%d", &x);
s->data = x;
s->next = NULL;
(*Q)->rear->next = s;
(*Q)->rear = s;
}
// 出队
bool DeQueue(LinkQueue** Q,int* x)
{
//先判断队列是否为空
if ((*Q)->front == (*Q)->rear)
{
return false;
}
//出队从队首开始,也就是头结点
LinkNode* p = (*Q)->front->next;//这个就是除头指针外队首的第一个节点地址
(*x) = p->data;
(*Q)->front->next = p->next;
if ((*Q)->rear==p)//出队的是最后一个节点,修改队尾指针到头结点
{
(*Q)->rear = (*Q)->front;
}
free(p);//释放掉这一块空间
return true;
}
int main()
{
LinkQueue* Q=(LinkQueue*)malloc(sizeof(LinkQueue));
int x = 0;
InitQueue(&Q);
//入队 入队5个元素
int i = 0;
for (i = 0; i < 5; i++)
{
EnQueue(&Q);
}
//出队一个元素
DeQueue(&Q,&x);
printf("出队的元素是%d\n", x);
return 0;
}