数据结构--循环队列、链队
基础知识
//循环队列数据结构
typedef struct
{
QElemType data[MaxQSize];//数据域
int front,rear; //队头队尾指针
}SqQueue;
//链队结点数据结构
typedef struct QNode
{
int data;//数据域
struct QNode* next;//指针域
}QNode, * QueuePtr;
typedef struct
{
struct QNode* front, * rear;//rear指针指向队尾 用于入队 front指针指向队头 用于出队
}LinkQueue;
队列是一种常见的数据结构，它遵循==先进先出（FIFO）==的原则。以下是队列的基本操作：
1、入队（Enqueue）：将元素添加到队列的末尾。
2、出队（Dequeue）：从队列的头部移除一个元素，并返回其值。
3、队列长度（Size）：获取队列中元素的个数。
4、队列是否为空（IsEmpty）：检查队列是否为空。
5、获取队首元素（Front）：获取队列头部的元素值，但不移除该元素。
C++ 实现队列的基本操作的示例代码：
#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;// 入队myQueue.push(10);myQueue.push(20);myQueue.push(30);// 队列长度std::cout << "队列长度：" << myQueue.size() << std::endl;// 出队int frontElement = myQueue.front();myQueue.pop();std::cout << "出队元素：" << frontElement << std::endl;// 获取队首元素std::cout << "队首元素：" << myQueue.front() << std::endl;// 队列是否为空std::cout << "队列是否为空：" << (myQueue.empty() ? "是" : "否") << std::endl;return 0;
}在C语言中，队列的基本操作可以通过结构体和指针来实现。
#include <stdio.h>
#include <stdlib.h>// 定义队列结构体
typedef struct {int *array; // 存储队列元素的数组int front; // 队首索引int rear; // 队尾索引int size; // 队列的容量
} Queue;// 初始化队列
void initQueue(Queue *queue, int capacity) {queue->array = (int*)malloc(capacity * sizeof(int));queue->front = 0;queue->rear = -1;queue->size = 0;
}// 销毁队列
void destroyQueue(Queue *queue) {free(queue->array);
}// 入队
void enqueue(Queue *queue, int element) {queue->rear = (queue->rear + 1) % queue->size;queue->array[queue->rear] = element;queue->size++;
}// 出队
int dequeue(Queue *queue) {int dequeuedElement = queue->array[queue->front];queue->front = (queue->front + 1) % queue->size;queue->size--;return dequeuedElement;
}// 获取队列长度
int getSize(Queue *queue) {return queue->size;
}// 检查队列是否为空
int isEmpty(Queue *queue) {return queue->size == 0;
}// 获取队首元素
int getFront(Queue *queue) {return queue->array[queue->front];
}int main() {Queue myQueue;initQueue(&myQueue, 5);// 入队enqueue(&myQueue, 10);enqueue(&myQueue, 20);enqueue(&myQueue, 30);// 队列长度printf("队列长度：%d\n", getSize(&myQueue));// 出队int frontElement = dequeue(&myQueue);printf("出队元素：%d\n", frontElement);// 获取队首元素printf("队首元素：%d\n", getFront(&myQueue));// 队列是否为空printf("队列是否为空：%s\n", isEmpty(&myQueue) ? "是" : "否");destroyQueue(&myQueue);return 0;
}循环队列
#define MaxSize 100
typedef struct { int data[MaxSize]; int front, rear; }SqQueue;//*********************************** 基本操作函数 *******************************************int InitQueue(SqQueue &Q)
{Q.front = Q.rear = 0;return 1;}
bool QueueEmpty(SqQueue& Q) {if (Q.front != Q.rear) return true;else return false;
}//入队：尾部加1； 出队：头部加1
bool EnQueue(SqQueue& Q, int& e) {if (Q.front ==Q.rear) return false;e = Q.data[Q.rear];Q.rear = (Q.rear + 1) % MaxSize; //指针加1 取模return true;
}bool DeQueue(SqQueue& Q, int &e) {if (Q.front == Q.rear) return false;e = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize; //指针加1 取模return true;
}bool GetHead(SqQueue& Q, int &e)
{if (Q.front == Q.rear) return false;//队空 e = Q.data[Q.front];return true;
}//********************************功能实现函数**************************************//void EnterToQueue(SqQueue& Q)
{int n; int e; int flag;printf("请输入入队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){printf("请输入第%d个元素的值:", i + 1);scanf("%d", &e);flag = EnQueue(Q, e);if (flag)printf("%d已入队\n", e);else { printf("队已满！！！\n"); break; }}
}void DeleteFromQueue(SqQueue& Q)
{int n; int e; int flag;printf("请输入出队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){flag = DeQueue(Q, e);if (flag)printf("%d已出队\n", e);else { printf("队已空！！！\n"); break; }}
}void GetHeadOfQueue(SqQueue Q)
{int e; bool flag;flag = GetHead(Q, e);if (flag)printf("队头元素为:%d\n", e);else printf("队已空！！！\n");
}void menu() {printf("********1.入队 2.出队*********\n");printf("********3.取队头元素 4.退出*********\n");
}int main() {SqQueue Q;int choice = 0;;InitQueue(Q);while (1){menu();printf("请输入菜单序号：\n");scanf("%d", &choice);if (choice == 4) break;switch (choice){case 1:EnterToQueue(Q); break;case 2:DeleteFromQueue(Q); break;case 3:GetHeadOfQueue(Q); break;default:printf("输入错误！！！\n");}system("pause");system("cls");}return 0;
}
链队
#define MaxSize 100//链队结点数据结构
typedef struct QNode
{int data;//数据域struct QNode* next;//指针域}QNode, * QueuePtr;
typedef struct
{struct QNode* front, * rear;//rear指针指向队尾 用于入队 front指针指向队头 用于出队
}LinkQueue;//*********************************** 基本操作函数 *******************************************int InitQueue(LinkQueue &Q)
{Q.front = Q.rear = new QNode;Q.front->next = NULL;return 1;}int EnQueue(LinkQueue& Q, int& e) {QNode* p;p = new QNode;//生成新节点p->data = e; //赋值p->next = NULL;Q.rear->next = p;//加入队尾Q.rear = p; //尾指针后移return 1;
}bool DeQueue(LinkQueue &Q, int &e) {QueuePtr p;if (Q.front == Q.rear)return false;//队空e = Q.front->next->data; //e返回值 之前写的Q.front->data 炸了，头结点没数据的，一定要注意头结点p = Q.front->next; //保留，一会儿释放空间Q.front->next = p->next; //出队,注意Q.front->next 不是Q.front 还有头结点if (Q.rear == p)Q.rear = Q.front; //最后一个元素出队，rear指向头结点free(p);return true;
}//取队顶函数 用e返回
bool GetHead(LinkQueue &Q, int &e)
{if (Q.front == Q.rear) return false;//队空 e = Q.front->next->data;return true;
}//********************************功能实现函数**************************************//void EnterToQueue(LinkQueue& Q)
{int n; int e; int flag;printf("请输入入队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){printf("请输入第%d个元素的值:", i + 1);scanf("%d", &e);flag = EnQueue(Q, e);if (flag)printf("%d已入队\n", e);}
}void DeleteFromQueue(LinkQueue& Q)
{int n; int e; int flag;printf("请输入出队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){flag = DeQueue(Q, e);if (flag)printf("%d已出队\n", e);else { printf("队已空！！！\n"); break; }}
}void GetHeadOfQueue(LinkQueue Q)
{int e; bool flag;flag = GetHead(Q, e);if (flag)printf("队头元素为:%d\n", e);else printf("队已空！！！\n");
}void menu() {printf("********1.入队 2.出队*********\n");printf("********3.取队头元素 4.退出*********\n");
}int main() {LinkQueue Q;int choice = 0;;InitQueue(Q);while (1){menu();printf("请输入菜单序号：\n");scanf("%d", &choice);if (choice == 4) break;switch (choice){case 1:EnterToQueue(Q); break;case 2:DeleteFromQueue(Q); break;case 3:GetHeadOfQueue(Q); break;default:printf("输入错误！！！\n");}system("pause");system("cls");}return 0;
}