数据结构-----队列

目录

前言

队列

定义 

队列的定义和操作方法

 队列节点的定义

 操作方式

 顺序表实现队列（C/C++代码）

链表实现队列（C/C++代码）

Python语言实现队列

---

前言

        排队是我们日常生活中必不可少的一件事，去饭堂打饭的时候排队，上公交车的时候排队等等，那排队的原则就是先到先得，排在前面的人先打饭，同样的在数据结构当中，有一种数据结构类型叫队列，其性质跟排队是一模一样的，下面我们就一起来看看吧！

队列

定义 

        队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

        队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表

 

队列可以通过顺序表实现和链表实现，下面就一起来看看吧！  

队列的定义和操作方法

 队列节点的定义

顺序表：

//队列定义
typedef struct queue {
	ElemType data[Maxsize];
	int front;//指向队头
	int rear;//指向队尾
}Queue;

链式：

//定义队列
typedef struct queue {
	int count;	//计数
	Node* front;//指向队头指针
	Node* rear;//指向队尾指针
}Queue;

 操作方式

void Queue_init(Queue* queue);//初始化
 
bool isEmpty(Queue* queue);//判空
 
bool isFull(Queue* queue);//判满
 
void enQueue(Queue* queue, ElemType data);//入队
 
Node* deQueue(Queue* queue);//出队
 
int get_length(Queue* queue);//获取长度
 
void travel_Queue(Queue* queue);//遍历（队头到队尾）
 
void clear_Queue(Queue* queue);//清空销毁

 顺序表实现队列（C/C++代码）

#include 
#include
#define Maxsize 20 //最大容量
//顺序表队列
 
//节点数据
typedef struct data {
	int num;
	char name[10];
}ElemType;
//队列定义
typedef struct queue {
	ElemType data[Maxsize];
	int front;//指向队头
	int rear;//指向队尾
}Queue;
 
//初始化
void queue_init(Queue* queue) {
	queue->front = 0;
	queue->rear = 0;
}
 
//判断是否满队列
bool isFull(Queue* queue) {
	if (queue->rear == Maxsize) {
		printf("The queue is full\n");
		return true;
	}
	return false;
}
 
//判断是否空队列
bool isEmpty(Queue* queue) {
	if (queue->rear == 0) {
		printf("The queue is etmpy\n");
		return true;
	}
	return false;
}
 
//入队操作
void enQueue(Queue* queue, ElemType data) {
	if (!isFull(queue)) {
        //赋值
		queue->data[queue->rear].num = data.num;
		strcpy(queue->data[queue->rear].name, data.name);
		queue->rear++;	//队尾+1，往后移动一位
	}
	else
		printf("error\n");
}
 
//出队操作
ElemType deQueue(Queue* queue) {
	ElemType de_data = { 0 };
	if (!isFull(queue)) {
		de_data = queue->data[queue->front];
		queue->front++;	//队头+1往后移动一位
		return de_data;
	}
	else
		printf("error\n");
}
 
//遍历队列（从队头开始到队尾）
void travel_Queue(Queue* queue) {
	for (int i = queue->front; i < queue->rear; i++) {
		printf("%d %s\n", queue->data[i].num, queue->data[i].name);
	}
	printf("printf over!\n");
}
 
//获取队列长度
int get_Queuelength(Queue* queue) {
	return queue->rear-queue->front;
}
 
//清空队列
void clear_Queue(Queue* queue) {
	queue_init(queue);//直接恢复出厂设置
}
 
int main(void)
{
	Queue queue;
	queue_init(&queue);
	ElemType data[4] = { {15,"fuck"},{16,"wdf"},{17,"wtmc"},{18,"cnmb"} };
	for (int i = 0; i < 4;i++) {
		enQueue(&queue, data[i]);
	}
	deQueue(&queue);
	travel_Queue(&queue);
}
 
//16 wdf
//17 wtmc
//18 cnmb
//printf over!

链表实现队列（C/C++代码）

#include
#include
#include 
#include
#include
#define Maxsize 20
 
typedef struct datatype {
	int num;
	char name[10];
}ElemType;
//定义节点
typedef struct node {
	ElemType data;
	struct node* next;
}Node;
//定义队列
typedef struct queue {
	int count;	//计数
	Node* front;//指向队头指针
	Node* rear;//指向队尾指针
}Queue;
 
void Queue_init(Queue* queue);//初始化
bool isEmpty(Queue* queue);//判空
bool isFull(Queue* queue);//判满
void enQueue(Queue* queue, ElemType data);//入队
Node* deQueue(Queue* queue);//出队
int get_length(Queue* queue);//获取长度
void travel_Queue(Queue* queue);//遍历
void clear_Queue(Queue* queue);//清空销毁
 
int main()
{
	Queue myqueue;
	Queue_init(&myqueue);
	ElemType data[4] = { {15,"a"},{16,"wb"},{17,"htt"},{18,"jk"} };
	for (int i = 0; i < 4; i++) {
		enQueue(&myqueue, data[i]);
	}
	deQueue(&myqueue);
	travel_Queue(&myqueue);
}
//16 wb
//17 htt
//18 jk
//Printf over
 
 
//初始化
void Queue_init(Queue* queue) {
	assert(queue);
	queue->front = NULL;
	queue->rear = NULL;
	queue->count=0;
}
 
//创建节点
Node* create_node(ElemType data) {
	Node* new_node = (Node*)malloc(sizeof(Node));
	if (new_node) {
		new_node->data = data;
		new_node->next = NULL;
		return new_node;
	}
	else
	{
		printf("ERRPR\n");
	}
}
 
//判断是否空队列
bool isEmpty(Queue* queue) {
	assert(queue);
	if (queue->count == 0)
	{
		printf("The queue is etmpy\n");
		return true;
	}
	return false;
}
 
//判断是否满队列
bool isFull(Queue* queue) {
	assert(queue);
	if (queue->count == Maxsize) {
		printf("The queue is full\n");
		return true;
	}
	return false;
}
 
//入队
void enQueue(Queue* queue, ElemType data) {
	assert(queue);
	if (!isFull(queue)) {
		Node* new_node = create_node(data);
        //如果队尾指向空的时候，也就是队列为空时
		if (queue->rear == NULL) {
			queue->front = new_node;
			queue->rear = new_node;
			queue->count++;
		}
        //当队列不为空的时候
		else
		{
			queue->rear->next = new_node;
			queue->rear = new_node;
			queue->count++;
		}
	}
	else
	{
		printf("error\n");
	}
}
 
//出队
Node* deQueue(Queue* queue) {
	assert(queue);
	if (!isEmpty(queue)) {
		Node* deNode = queue->front;
		queue->front = deNode->next;
		queue->count--;
		return deNode;
	}
	printf("error\n");
	return NULL;
}
 
//获取队列长度
int get_length(Queue* queue) {
	assert(queue);
	return queue->count;
}
 
//遍历队列
void travel_Queue(Queue* queue) {
	assert(queue);
	Node* cur = queue->front;
	while (cur) {
		printf("%d %s\n", cur->data.num, cur->data.name);
		cur = cur->next;
	}
	printf("Printf over\n");
}
 
//清空队列
void clear_Queue(Queue* queue) {
	assert(queue);
	Node* cur = queue->front;
	while (cur) {
        //要把每一个节点的空间都释放，避免内存泄漏
		Node* p = cur->next;    //获取到当前节点的下一个节点
		free(cur);
		cur = p;
	}
	printf("Clear successfully!\n");
}
 

Python语言实现队列

链接：Python数据结构-----队列_python队列_灰勒塔德的博客-CSDN博客

 以上就是今天的全部内容了，我们下一期再见！！！

分享一张壁纸：