基础知识
//循环队列数据结构
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;文章来源:https://uudwc.com/A/9vpMz
队列是一种常见的数据结构,它遵循==先进先出(FIFO)==的原则。以下是队列的基本操作:
1、入队(Enqueue):将元素添加到队列的末尾。
2、出队(Dequeue):从队列的头部移除一个元素,并返回其值。
3、队列长度(Size):获取队列中元素的个数。
4、队列是否为空(IsEmpty):检查队列是否为空。
5、获取队首元素(Front):获取队列头部的元素值,但不移除该元素。文章来源地址https://uudwc.com/A/9vpMz
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;
}