1. 首页
  2. 文章中心
  3. 数据结构

队列结构04(数组实现，链表实现)数据结构之队列结构

124 阅读 0 评论
我是靠谱客的博主 超帅海燕，这篇文章主要介绍队列结构04(数组实现，链表实现)数据结构之队列结构，现在分享给大家，希望可以做个参考。

数据结构之队列结构

目录

  • 数据结构之队列结构
    • 一、队列结构介绍（FIFO）
    • 二、队列结构要求
    • 三、代码实现
      • 1）多申请一块内存实现循环队列（array实现）
      • 2）多创建一个变量解决队空队满（array实现）
      • 3）队列链式实现

一、队列结构介绍（FIFO）

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

二、队列结构要求

顺序队列的数据项：
1、存储元素的内存首地址 2、容量3、队头下标4、队尾下标
顺序队列的运算：
创建、销毁、入队、出队、队空、队满、查队头、查队尾、数量

顺序队列的注意点：
由一维数组+队头下标front+队尾下标tail组成，入队tail++,出队front++，为了让队列能够反复使用，我们把队列想象成一个环，因此当front和tail加1后都需要用队列容量求余再重新赋值
front = (front+1)%cal;
tail = (tail+1)%cal;
如何判断队空、队满：
1、额外多申请一个元素的内存
队空：front == tail
队满：(tail+1)%cal == front
2、额外创建一个存放数量的变量

三、代码实现

1）多申请一块内存实现循环队列（array实现）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/************************************
> 作者：杭电羊皮卷
> weixin:QQ2997675141
************************************/

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

#define TYPE int
typedef struct ArrayQueue{
	TYPE* ptr;
	size_t cal;
	size_t front;	//队头下标
	size_t tail;	//指向即将入队的位置
}ArrayQueue;

//创建队列结构
ArrayQueue* create_array_queue(size_t cal)
{
	ArrayQueue* queue = (ArrayQueue* )malloc(sizeof(ArrayQueue));
	//申请内存时多申请一个解决队满和队空的判断问题
	queue->ptr = (TYPE* )malloc(sizeof(TYPE)*(cal+1));
	queue->cal = cal+1;
	queue->front = 0;
	queue->tail = 0;
	return queue;
}

//销毁
void destory_array_queue(ArrayQueue* queue)
{
	free(queue->ptr);
	free(queue);
}
//队空
bool empty_array_queue(ArrayQueue* queue)
{
	return queue->front == queue->tail;	
}
//队满
bool full_array_queue(ArrayQueue* queue)
{
	return (queue->tail+1)%queue->cal == queue->front;	
}

//出队
bool pop_array_queue(ArrayQueue* queue,TYPE* val)
{
	if(empty_array_queue(queue))	return false;
	*val = queue->ptr[queue->front];
	queue->front = (queue->front+1)%queue->cal;
	return true;
}

//入队
bool push_array_queue(ArrayQueue* queue,TYPE val)
{
	if(full_array_queue(queue))	return false;
	queue->ptr[queue->tail] = val;
	queue->tail = (queue->tail+1)%queue->cal;
	return true;
}

//队尾
TYPE back_array_queue(ArrayQueue* queue)
{
	return queue->ptr[(queue->tail-1+queue->cal)%queue->cal];	
}

//队头
TYPE front_array_queue(ArrayQueue* queue)
{
	return queue->ptr[queue->front];	
}

//数量
size_t size_array_queue(ArrayQueue* queue)
{
	return (queue->tail+queue->cal-queue->front)%queue->cal;	
}


int main(int argc,const char* argv[])
{
	ArrayQueue* queue = create_array_queue(10);
	for(int i=0; i<10; i++)
	{
		push_array_queue(queue,i);
		printf("tail = %dn",back_array_queue(queue));
	}
    //这里写测试代码
	return 0;
}

2）多创建一个变量解决队空队满（array实现）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/************************************
> 作者：杭电羊皮卷
> weixin:QQ2997675141
************************************/

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

#define TYPE int
typedef struct ArrayQueue{
	TYPE* ptr;
	size_t cal;		//容量
	size_t cnt;		//队列中已存储的元素个数
	size_t front;	//队头下标
	size_t tail;	//队尾下标 -1开始
}ArrayQueue;

//创建队列结构
ArrayQueue* create_array_queue(size_t cal)
{
	ArrayQueue* queue = (ArrayQueue* )malloc(sizeof(ArrayQueue));
	//申请内存时多申请一个解决队满和队空的判断问题
	queue->ptr = (TYPE* )malloc(sizeof(TYPE)*cal);
	queue->cnt =0;
	queue->cal = cal;
	queue->front = 0;
	queue->tail = -1;//指向最后一个元素
	return queue;
}

//销毁
void destory_array_queue(ArrayQueue* queue)
{
	free(queue->ptr);
	free(queue);
}
//队空
bool empty_array_queue(ArrayQueue* queue)
{
	return queue->cnt;	
}
//队满
bool full_array_queue(ArrayQueue* queue)
{
	return queue->cnt >= queue->cal;
}

//出队
bool pop_array_queue(ArrayQueue* queue,TYPE* val)
{
	if(empty_array_queue(queue))	return false;
	*val = queue->ptr[queue->front];
	queue->front = (queue->front+1)%queue->cal;
	queue->cnt--;
	return true;
}

//入队
bool push_array_queue(ArrayQueue* queue,TYPE val)
{
	if(full_array_queue(queue))	return false;
	queue->tail = (queue->tail+1)%queue->cal;
	queue->ptr[queue->tail] = val;
	queue->cnt++;
	return true;
}

//队尾
TYPE back_array_queue(ArrayQueue* queue)
{
	return queue->ptr[queue->tail];	
}

//队头
TYPE front_array_queue(ArrayQueue* queue)
{
	return queue->ptr[queue->front];	
}

//数量
size_t size_array_queue(ArrayQueue* queue)
{
	return queue->cnt;
}


int main(int argc,const char* argv[])
{
	ArrayQueue* queue = create_array_queue(10);
	for(int i=0; i<10; i++)
	{
		push_array_queue(queue,i);
		printf("tail = %dn",back_array_queue(queue));
	}
    //这里写测试代码
	return 0;
}

3）队列链式实现

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/************************************
> 作者：杭电羊皮卷
> weixin:QQ2997675141
************************************/

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

#define TYPE int

typedef struct Node{
	TYPE data;
	struct Node* next;
}Node;

Node* create_node(TYPE data)
{
	Node* node = (Node* )malloc(sizeof(Node));
	node->data = data;
	node->next = NULL;
	return node;
}

typedef struct ListQueue{
	Node* front;//对头节点
	Node* tail;	//队尾节点
	size_t cnt;	//节点数量
}ListQueue;

//创建
ListQueue* create_list_queue(void)
{
	ListQueue* queue = malloc(sizeof(ListQueue));
	queue->front = NULL;
	queue->tail = NULL;
	queue->cnt = 0;
	return queue;
}
//队空
bool empty_list_queue(ListQueue* queue)
{
	return 0 == queue->cnt;	
}

//入队
void push_list_queue(ListQueue* queue,TYPE val)
{
	Node* node = create_node(val);
	if(empty_list_queue(queue))
	{
		queue->front = node;
		queue->tail = node;
	}
	else
	{
		queue->tail->next = node;
		queue->tail = node;
	}
	queue->cnt++;
}

//出队
bool pop_list_queue(ListQueue* queue)
{
	if(empty_list_queue(queue))	return false;
	Node* n = queue->front;
	queue->front = n->next;
	queue->cnt--;
	if(0 == queue->cnt)	queue->tail = NULL;
	free(n);
	return true;
}

//队头
TYPE front_list_queue(ListQueue* queue)
{
	return queue->front->data;	
}

//队尾
TYPE back_list_queue(ListQueue* queue)
{
	return queue->tail->data;	
}

//数量
size_t size_list_queue(ListQueue* queue)
{
	return queue->cnt;	
}


//销毁
void destory_list_queue(ListQueue* queue)
{
	while(pop_list_queue(queue));
	free(queue);
}

int main(int argc,const char* argv[])
{
	ListQueue* queue = create_list_queue();
	for(int i=0; i<10; i++)
	{
		push_list_queue(queue,i);
		printf("tail:%d size:%dn",back_list_queue(queue),size_list_queue(queue));
	}
	printf("================================n");
	while(!empty_list_queue(queue))
	{
		printf("front:%d size:%dn",front_list_queue(queue),size_list_queue(queue));
		pop_list_queue(queue);
	}
    //这里写测试代码
	return 0;
}

最后

以上就是超帅海燕最近收集整理的关于队列结构04(数组实现，链表实现)数据结构之队列结构的全部内容，更多相关队列结构04(数组实现内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(82)

相关文章

CP_THREAD_ACP与CP_ACP区别
CP_THREAD_ACP与CP_ACP区别
AQS的非公平锁与同步队列的FIFO冲突吗？
AQS的非公平锁与同步队列的FIFO冲突吗？
TCP/IP网络编程各头文件作用汇总
TCP/IP网络编程各头文件作用汇总
c++11 完全公平队列实现
c++11 完全公平队列实现
队列结构04(数组实现，链表实现)数据结构之队列结构
队列结构04(数组实现，链表实现)数据结构之队列结构
【数据结构初学笔记04】队列的存储实现
【数据结构初学笔记04】队列的存储实现
C/C++队列的链式实现
C/C++队列的链式实现
队列的基本描述，及c和c++分别顺序队列和链式队列实现，利用队列处理农夫过河问题
队列的基本描述，及c和c++分别顺序队列和链式队列实现，利用队列处理农夫过河问题

评论列表共有 0 条评论

立即
投稿
返回
顶部