学习记录——day17 数据结构 队列 链式队列
队列介绍
1、队列也是操作受限的线性表:所有操作只能在端点处进行，其删除和插入必须在不同端进行
2、允许插入操作的一端称为队尾，允许删除操作的一端称为队头
3、特点:先进先出(FIFO)
4、分类：
顺序存储的栈称为顺序栈
链式存储的队列，称为链式队列
顺序队列
1、使用一片连续存储的空间存储队列，并且给定两个变量，分别记录队头和队尾下标
2、普通顺序队列使用中，存在“假溢满”现象
假溢满:队列中明明还有存储空间，但是由于队尾已经达到了数组的最大下标，不能在继续 入队元素了
3、为了解决“假溢满”现象，我们引入了循环顺序队列
循环顺序队列
循环顺序队列:通过相关操作，当对头或队尾达到数组最大下标时，可以返回到下标为0的位置
注：以下均使用人为浪费一个空间的方法判满
1、创建
头节点类型定义
//类型重定义
typedef int datatype;//队列类型结构体
typedef struct Queue
{datatype data[MAX];int head;int tail;}SeqQueue, *SeqQueuePtr;
创建队列
SeqQueuePtr queue_create()
{SeqQueuePtr Q = (SeqQueuePtr)malloc(sizeof(SeqQueue));if(NULL == Q){return NULL;}bzero(Q->data,sizeof(Q->data));Q->front = Q->tail = 0;printf("创建成功 \n");return Q;
}2、判空判满
int queue_empty(SeqQueuePtr Q)
{return Q->tail == Q->front;
}int queue_full(SeqQueuePtr Q)
{return (Q->tail+1)%MAX == Q->front;
}3、插入
void queue_push(SeqQueuePtr Q ,datatype e)
{if (NULL == Q || queue_full(Q)){return;}Q->data[Q->tail] = e;Q->tail = (Q->tail+1)%MAX;return;
}4、遍历
void queue_show(SeqQueuePtr Q)
{if (NULL == Q){return;}printf("遍历结果:");for (int i = Q->front; i !=Q->tail; i=(i+1)%MAX){printf("%d\t",Q->data[i]);}putchar(10);return;
}5、出队
void queue_pop(SeqQueuePtr Q)
{if (NULL == Q || queue_empty(Q)){return;}printf("%d 出队\n",Q->data[Q->front]);Q->front = (Q->front+1)%MAX;
}6、求实际大小
int queue_size(SeqQueuePtr Q)
{if (NULL == Q){return -1;}//不使用循环求大小int size = ((Q->tail-Q->front)+MAX)%MAX;return size;
}7、销毁
void queue_destroy(SeqQueuePtr Q)
{if (NULL != Q){free(Q);Q = NULL;}printf("boom!!\n");return;
}8、完整代码
dui_lie.h
#ifndef DUI_LEI
#define DUI_LEI#include <myhead.h>#define MAX 8
typedef int datatype;typedef struct
{datatype data[MAX];int front;int tail;
}SeqQueue,*SeqQueuePtr;SeqQueuePtr queue_create();int queue_empty(SeqQueuePtr Q);int queue_full(SeqQueuePtr Q);void queue_push(SeqQueuePtr Q ,datatype e);void queue_show(SeqQueuePtr Q);void queue_pop(SeqQueuePtr Q);int queue_size(SeqQueuePtr Q);void queue_destroy(SeqQueuePtr Q);#endif // !DUI_LEI.H
dui_lie.c
#include "dui_lie.h"
#include <myhead.h>SeqQueuePtr queue_create()
{SeqQueuePtr Q = (SeqQueuePtr)malloc(sizeof(SeqQueue)*MAX);if(NULL == Q){return NULL;}bzero(Q->data,sizeof(Q->data));Q->front = Q->tail = 0;printf("创建成功 \n");return Q;
}int queue_empty(SeqQueuePtr Q)
{return Q->tail == Q->front;
}int queue_full(SeqQueuePtr Q)
{return (Q->tail+1)%MAX == Q->front;
}void queue_push(SeqQueuePtr Q ,datatype e)
{if (NULL == Q || queue_full(Q)){return;}Q->data[Q->tail] = e;Q->tail = (Q->tail+1)%MAX;return;
}void queue_show(SeqQueuePtr Q)
{if (NULL == Q){return;}printf("遍历结果:");for (int i = Q->front; i !=Q->tail; i=(i+1)%MAX){printf("%d\t",Q->data[i]);}putchar(10);return;
}void queue_pop(SeqQueuePtr Q)
{if (NULL == Q || queue_empty(Q)){return;}printf("%d 出队\n",Q->data[Q->front]);Q->front = (Q->front+1)%MAX;
}int queue_size(SeqQueuePtr Q)
{if (NULL == Q){return -1;}//不使用循环求大小int size = ((Q->tail-Q->front)+MAX)%MAX;return size;
}void queue_destroy(SeqQueuePtr Q)
{if (NULL != Q){free(Q);Q = NULL;}printf("boom!!\n");return;
}main.c
#include "dui_lie.h"
int main(int argc, char const *argv[])
{SeqQueuePtr Q = queue_create();if (NULL == Q){return -1;}queue_push(Q,90);queue_push(Q,80);queue_push(Q,100);queue_push(Q,20);queue_show(Q);queue_pop(Q);queue_pop(Q);queue_show(Q);printf("数组实际大小为%d:\n",queue_size(Q));queue_destroy(Q);return 0;
}
链式队列
链式存储的队列称为链式队列
实现原理:
单向链表头插尾删实现:链表的头部就是队尾，链表的尾部就是队头
单向链表头删尾插实现:链表的头部就是队头，链表的尾部就是队尾
但是，上述操作中，都要用到链表尾部节点，都需要遍历整个链表完成，于是专门使用一个指针指向队尾，称为尾指针
00.h
#ifndef DAY17_1
#define DAY17_1#include <myhead.h>//类型重定义
typedef int datatype;//节点结构体
typedef struct Node
{union {datatype data;int len;};struct Node *next;}Node, *NodePtr;//头节点结构体
typedef struct Queue
{NodePtr head;NodePtr tail;}Queue, *QueuePtr;//队列创建
QueuePtr queue_create();//判空
int queue_empty(QueuePtr Q);//头插
int queue_push(QueuePtr Q,datatype);//遍历
int queue_show(QueuePtr Q);//出队
int queue_pop(QueuePtr Q);//输出实际大小
int queue_size(QueuePtr Q);//销毁
void queue_destroy(QueuePtr Q);#endif // DAY17_100.c
#include "00.h"//先创建队列 然后创建链表，将队列的两个指针指向链表
QueuePtr queue_create()
{//申请队列的空间QueuePtr Q = (QueuePtr)malloc(sizeof(Queue));if (NULL == Q){printf("创建失败\n");return NULL;}//创建链表Q->head = (NodePtr)malloc(sizeof(Node));if (Q->head == NULL){printf("创建失败\n");free(Q);return NULL;}Q->head->len = 0;Q->head->next = NULL;Q->tail = Q->head;return Q;
}int queue_empty(QueuePtr Q)
{return Q->head->len == 0;
}int queue_push(QueuePtr Q,datatype e)
{if (NULL == Q){return -1;}NodePtr p = (NodePtr)malloc(sizeof(Node));if (NULL == p){return -1;}p->data = e;p->next = NULL;Q->tail->next = p;Q->tail = p;Q->head->len++;}int queue_show(QueuePtr Q)
{if (NULL == Q || queue_empty(Q)){return -1;}NodePtr q = Q->head->next;while (q){printf("%d\t",q->data);q = q->next;}putchar(10);
}int queue_pop(QueuePtr Q)
{if (NULL == Q){return -1;}NodePtr p = Q->head->next;Q->head->next = p->next;printf("%d 出队\n",p->data);free(p);p = NULL;//如果所有节点都出列成功，将尾节点重新指向头节点if (Q->tail == NULL)//Q->head->next == NULL{Q->tail = Q->head;}Q->head->len--;
}int queue_size(QueuePtr Q)
{if (NULL == Q){return -1;}return Q->head->len;
}void queue_destroy(QueuePtr Q)
{if (NULL == Q){return;}//释放所有节点while (!queue_empty(Q)){queue_pop(Q);}//释放头结点free(Q->head);Q->head = Q->tail = NULL;//释放队列空间free(Q);Q = NULL;
}main.c
#include "00.h"int main(int argc, char const *argv[])
{QueuePtr Q = queue_create();if (NULL == Q){return -1;}queue_push(Q,233);queue_push(Q,1314);queue_push(Q,520);queue_show(Q);queue_pop(Q);queue_pop(Q);queue_pop(Q);queue_destroy(Q);return 0;
}