青海省建设网站价格低,网站正在建设 下载,wordpress主题猫,网站建设制作设计seo优化湖北一.队列的基本概念队列的定义队列#xff08;queue#xff09;是只允许在一端进行插入操作#xff0c;而在另一端进行删除操作的线性表。队列是一种先进先出#xff08;First In First Out#xff09;的线性表#xff0c;简称FIFO。允许插入的一端称为队尾#xff0c;允…一.队列的基本概念队列的定义队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。队列是一种先进先出First In First Out的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头。队头Front允许删除的一端又称队首。队尾Rear允许插入的一端。空队列不包含任何元素的空表。2.队列的常见基本操作// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);一.队列设计1.队列的顺序存储类型#define MAXSIZE 50 //定义队列中元素的最大个数
typedef struct{dataType a[MAXSIZE]; //存放队列元素int front,rear;
}SeqQueue;初始状态队空条件Q-front Q-rear 0。进队操作队不满时先送值到队尾元素再将队尾指针加1。出队操作队不空时先取队头元素值再将队头指针加1。设计一个链式的队列2.队列的链式存储类型typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;queue.h#pragma once
#include stdbool.h
#include stdio.h
#include assert.h
#include stdlib.htypedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq); queue.c初始化队列void QueueInit(Queue* pq)
{assert(pq);pq-head NULL;pq-tail NULL;pq-size 0;
}判断是否栈空bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL pq-tail NULL;
}
入栈void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}
出栈void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;pq-head pq-head-next;free(del);}pq-size--;
}
获取队首元素/获取队尾元素QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}获取队列中元素的个数int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}销毁队列void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);//del NULL;}pq-head pq-tail NULL;pq-size 0;
}二.循环队列解决假溢出的方法就是后面满了就再从头开始也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针Q-front MAXSIZE-1后再前进一个位置就自动到0这可以利用除法取余运算%来实现。初始时Q-front Q-rear0。队首指针进1Q-front (Q-front 1) % MAXSIZE。队尾指针进1Q-rear (Q-rear 1) % MAXSIZE。队列长度(Q-rear - Q-front MAXSIZE) % MAXSIZE。但是这种把循环队列存满数据的方式会让我们不能通过Q-front Q-rear来具体判断是否是队满还是队空如图1牺牲一个单元来区分队空和队满入队时少用一个队列单元这是种较为普遍的做法约定以“队头指针在队尾指针的下一位置作为队满的标志”如图 队满条件 (Q-rear 1)%Maxsize Q-front队空条件仍 Q-front Q-rear队列中元素的个数 (Q-rear - Q -front Maxsize)% Maxsize2类型中增设表示元素个数的数据成员。这样队空的条件为 Q-size O 队满的条件为 Q-size Maxsize 。这两种情况都有 Q-front Q-rear3类型中增设tag 数据成员以区分是队满还是队空。tag 等于0时若因删除导致 Q-front Q-rear 则为队空tag 等于 1 时若因插入导致 Q -front Q-rear 则为队满。下面针对第一种方法来设计一个循环顺序队列三.双端队列1、定义双端队列是指允许两端都可以进行入队和出队操作的队列如下图所示。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端两端都可以入队和出队。在双端队列进队时前端进的元素排列在队列中后端进的元素的前面后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时无论是前端还是后端出队先出的元素排列在后出的元素的前面。2、特殊的双端队列在实际使用中根据使用场景的不同存在某些特殊的双端队列。输出受限的双端队列允许在一端进行插入和删除 但在另一端只允许插入的双端队列称为输出受限的双端队列如下图所示。输入受限的双端队列允许在一端进行插入和删除但在另一端只允许删除的双端队列称为输入受限的双端队列如下图所示。若限定双端队列从某个端点插入的元素只能从该端点删除则该双端队列就蜕变为两个栈底相邻接的栈。
