概述
数据结构之队列结构
目录
- 数据结构之队列结构
- 一、队列结构介绍（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实现）
/************************************
> 作者：杭电羊皮卷
> 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实现）
/************************************
> 作者：杭电羊皮卷
> 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）队列链式实现
/************************************
> 作者：杭电羊皮卷
> 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(数组实现，链表实现)数据结构之队列结构所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复