layout: post
title: "队列实现"
date: 2020-09-01
author: "王玉松"
header-img: ""
categories: Data Structure
tags:
- 队列
- 顺序
- 链式

队列实现

队列的实现也采用顺序形式和链式
顺序形式中, 选择的实现方式是空出一个存储空间用于区分队空和队满状态.
链式中, 选择不带头结点的创建方式,
在判断队空, 首个元素入队, 最后元素出队等方面与顺序不同.

一、基本数据结构

顺序队列与顺序栈的定义相似, 采用循环队列的形式, 舍弃一个存储单元
链队定义中使用之前的 Node 定义, 链队 LQueue 简单定义为包含两个 Node 指针类型
分别指向队首和队尾.
与栈相似, 链队也不存在队满的判断.

#define MAXSIZE 6

//empty one storage to judge empty or full
typedef struct queue
{
  int front, rear;
  int data[MAXSIZE];
}Queue;

//LinkQueue
typedef struct Node
{
  int data;
  Node *next;
}Node;

typedef struct LQueue
{
  Node *front;
  Node *rear;
}LQueue;

二、基本的数据结构操作

//顺序队列

//设置队首, 队尾的位置, 并初始化数组
void InitQueue(Queue *Q);

//判断队列是否为空, 只需判断队首队尾是否相等
int Empty(Queue *Q);

//判断队列是否满, 使用数学上的等式 front == (rear+1)%MAXSIZE
int Full(Queue *Q);

//返回队列长度, 分 3 种情况
//队空, 队满, 未满
//未满情况下, rear 可能比 front 下, 因此相减是需要加上模(MAXSIZE), 结果仍取模
//(MAXSIZE + Q->rear - Q->front)%MAXSIZE
void QueueLength(Queue *Q, int *value);

//元素入队, 入队后 rear 调整, 由于循环队列, 结果取模
void Offer(Queue *Q, int value);

//获得队首保存的元素
void GetFront(Queue *Q, int *value);

//元素出队, 若对空, 返回-1
//出队后 front 调整, 结果取模
void Poll(Queue *Q, int *value);

//顺序输出队列中包含的所有元素
void Display(Queue *Q);



//链栈

//初始化链栈, 采用不带头结点的队列, 则 front = rear = NULL
void InitQueue(LQueue *Q);

//判断队列是否为空
int EmptyLQueue(LQueue *Q);

//元素入队, 对于首个元素的入队操作特殊, front rear 同时指向一个 Node 
void Offer(LQueue *Q, int value);

//元素出队, 对于最后一个元素的出队操作特殊
//在删除 Node 之前, 需要调整 rear , 使其不再指向将要删除的结点
void Poll(LQueue *Q, int *value);

//获得队首元素
void Peek(LQueue *Q, int *value);

//返回队列的长度, 使用计数器, 遍历链表完成计数 
void LQueueLength(LQueue *Q, int *value);

//顺序输出队列中包含的所有元素
void DisplayLQueue(LQueue *Q);

三、从中获得的关于编写C代码的知识

1. 实现顺序队列的过程中, 有三种实现方式
   a. 牺牲一个存储单元
   b. 链队中增设一个元素个数的数据成员
   c. 链队中增设一个状态成员, 用于区分队满和队空状态

2. 在链队的入队, 出队操作中, 涉及首个元素入队和最后一个元素出队
   整体初始状态的改变和回归需要特别注意.

3. 在链队中首次使用基于自定义类型的类型定义, LQueue 中包含两个 Node 型指针
   完成链队的基本定义.

4. 关于指针的操作较为复杂, 在链队的遍历过程中, 使用函数内部的局部指针变量
   替代原指针进行操作, 指针参数科直接对原数据进行改动, 可以改变原指针的位置.

四、相关代码

1. 队列实现