线性结构_队列

线性结构 - 队列的顺序存储表示及其操作

结构 QNode - PtrToQNode - Queue

1. 数组Data存放元素，循环存放实现循环队列
2. 设置队头front与rear队尾两个指针
3. 队列的最大容量

创建

1. 动态申请队列Queue的空间
2. 动态申请队列中数组Data的空间,
3. 最大长度为MaxSize
4. 初始化队头front与队尾rear指针为0

是否为空

1. 队头front与队尾rear相等，则为空队列

是否已满

1. 队尾rear+1模以容量等于队头front，则队列已满

入列 - 队尾rear

1. 判断队列是否已满
2. 找到队列尾rear指针，在原指针加1后模以容量，以防在最队尾，重回队头
3. 在队列的数组Data的第rear个位置插入元素item

出列 - 队头front

1. 判断队列是否为空
2. 找到队头指针front,在原有指针上加1模以容量，如果在最末位，则重返数组第1位
3. 返回队头front指针的元素

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

typedef int ElementType;
typedef struct QNode *PtrToQNode;

struct QNode{
    // 1.数组Data存放元素，循环存放实现循环队列
   ElementType *Data;
   // 2.设置队头front与rear队尾两个指针
   int front, rear;
   // 3.队列的最大容量
   int MaxSize;
};
typedef PtrToQNode Queue;

// 创建
Queue CreateQueue(int MaxSize){
   Queue queue;
   // 1.动态申请队列Queue的空间
   queue = (Queue)malloc(sizeof(struct QNode));
   // 2.动态申请队列中数组Data的空间,
   queue->Data = (ElementType *)malloc(sizeof(ElementType)*MaxSize);
   // 3.最大长度为MaxSize
   queue->MaxSize = MaxSize;
   // 4.初始化队头front与队尾rear指针为0
   queue->front = 0;
   queue->rear = 0;
   return queue;
}

// 是否为空
bool isEmpty(Queue queue){
    // 1. 队头front与队尾rear相等，则为空队列
   return queue->rear == queue->front;
}

// 是否已满
bool isFull(Queue queue) {
    // 1.队尾rear+1模以容量等于队头front，则队列已满
   return (queue->rear + 1)%queue->MaxSize == queue->front;
}

// 入列 - 队尾rear
bool add(Queue queue, ElementType item){
    // 1. 判断队列是否已满
   bool isFull(Queue queue);
   if (isFull(queue)) {
       printf("queue is full!");
       return false;
   }
   // 2.找到队列尾rear指针，在原指针加1后模以容量，以防在最队尾，重回队头
   queue->rear = (queue->rear + 1)%queue->MaxSize;
   // 3.在队列的数组Data的第rear个位置插入元素item
   queue->Data[queue->rear] = item;
   return true;
}

//出列 - 队头front
ElementType Delete(Queue queue){
    // 1.判断队列是否为空
   bool isEmpty(Queue queue);
   if (isEmpty(queue)) {
       printf("queue is empty!");
       return -1;
   }
   // 2.找到队头指针front,在原有指针上加1模以容量，如果在最末位，则重返数组第1位
   queue->front = (queue->front +1)%queue->MaxSize;
   // 3.返回队头front指针的元素
   return queue->Data[queue->front];
}

线性结构 - 队列的链式存储表示及其操作

结构 邻结点Node - PtrToNode - Position 头结点QNode - Queue

链表邻结点Node

1. 链表邻结点
2. 下一个结点Next

队列链表头结点

1. 链表队列的头Front、尾结Rear点作为指针
2. 队列容量、长度

创建

1. 动态申请队列Queue空间
2. 初始化队列队头Front、队尾Rear指针为NULL

是否为空

1. 判断队头指针Front是否为NULL

入列 - 队尾

1. 动态申请邻结点Node空间
2. 将新插入的值item赋值给新结点node,并初始化Next为NULL
3. 如果队列为空，则Front和Rear都指向该结点,否则Rear指向该结点

出列 - 队头

1. 判断队列是否为空
2. 根据队头指针找到头结点FrontCell及其数据
3. 如果队列中只有一个元素，队头Front、队尾Rear指针置为NULL，
4. 否则将头结点Front指向头结点的下一个结点(第二个结点)
5. 释放原来的头结点FrontCell

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

typedef int ElementType;
typedef struct Node *PtrToNode;

// 链表邻结点
struct Node {
    // 1.结点数据Data
   ElementType Data;
   // 2.下一个结点Next
   PtrToNode Next;
};
typedef PtrToNode Position;

// 队列链表头结点
struct QNode {
    // 1.链表队列的头Front、尾结Rear点作为指针
   Position Front, Rear;
   // 2.队列容量、长度
   int MaxSize;
};
typedef struct QNode *Queue;

// 创建
Queue CreateQueue() {
   Queue queue;
   // 1.动态申请队列Queue空间
   queue = (Queue) malloc(sizeof(struct QNode));
   // 2.初始化队列队头Front、队尾Rear指针为NULL
   queue->Front = queue->Rear = NULL;
   return queue;
}

// 是否为空队列
bool isEmpty(Queue queue) {
    // 1.判断队头指针Front是否为NULL
   return (queue->Front == NULL);
}

// 入列 - 队尾
void add(Queue queue, ElementType item) {
   if (queue == NULL) {
       return;
   }
   PtrToNode node;
   // 1.动态申请邻结点Node空间
   node = (PtrToNode) malloc(sizeof(struct Node));
   // 2.将新插入的值item赋值给新结点node,并初始化Next为NULL
   node->Data = item;
   node->Next = NULL;
   // 3.如果队列为空，则Front和Rear都指向该结点,否则Rear指向该结点
   bool isEmpty(Queue queue);
   if (isEmpty(queue)) {
       queue->Front = node;
       queue->Rear = node;
   } else {
       queue->Rear = node;
   }
}

// 出列 - 队头
ElementType Delete(Queue queue) {
   Position FrontCell;
   ElementType FrontElem;
   // 1.判断队列是否为空
   bool isEmpty(Queue queue);
   if (isEmpty(queue)) {
       printf("queue is empty!");
       return -1;
   } else {
       // 2.根据队头指针找到头结点FrontCell及其数据
       FrontCell = queue->Front;
       FrontElem = FrontCell->Data;
       // 3.如果队列中只有一个元素，队头Front、队尾Rear指针置为NULL，
       if (queue->Front == queue->Rear) {
           queue->Front = queue->Rear = NULL;
       } else {
           // 4.否则将头结点Front指向头结点的下一个结点(第二个结点)
           queue->Front = FrontCell->Next;
       }
       // 5.释放原来的头结点FrontCell
       free(FrontCell);
       return FrontElem;
   }
}