一、队列概念
队列时一种特殊的线性表,只允许在表的前端进行删除操作,而在表的后端进行插入操作,队列具有先进先出的特点。
队列的操作很简单,主要有以下几种常见的操作:
(1)初始化队列:创建一个队列
(2)进队列:将一个元素添加到队尾
(3)出队列:将队头元素取出,同时删除该元素,使下一个元素成为对头
(4)获取队列第一元素:将队头元素取出,不删除该元素
(5)获取队列长度:根据队头和队尾计算出队列中元素的数量
二、顺序队列实现
将队列用顺序存储方式保存时,在内存中申请一片区域用来保存元素,当第一个元素A进入队列时,因是空列队,因此元素A将排在队头,接着B、C、D顺次进入队列,就得到如图所示的队列。其中head指向队头,以指示队头元素出队操作,tail指向队尾,以指示新增元素进入队列。如下图所示:
执行一次出队操作,元素A将出队,这时第2个元素B将成为队头,head指针将指向该元素如果要将元素E入队,则是将其放入tail指针指向元素的后一个位置(如下图为5的单元),并使tail指针指向序号为5的单元。(1)定义顺序队列的结构
#define QUEUEMAX 15typedef struct{ DATA data[QUEUEMAX]; int head; int tail;} SeqQueue;
(2)初始化队列
SeqQueue *SeqQueueInit(){ SeqQueue *q; if (q=(SeqQueue *)malloc(sizeof(SeqQueue))) { q->head = 0; q->tail = 0; return q; } return NULL;}
(3)释放队列
void SeqQueueFree(SeqQueue *q){ if (q) free(q);}
(4)获取队列状态
/**判断队列是否为空*/int SeqQueueIsEmpty(SeqQueue *q){ return (q->head == q->tail);}/**判断队列是否已满*/int SeqQueueIsFull(SeqQueue *q){ return (q->tail == QUEUEMAX);}/**获取队列的长度*/int SeqQueueLen(SeqQueue *q){ return (q->tail - q->head);}
(5)入队操作
int SeqQueueIn(SeqQueue *q, DATA data){ if (SeqQueueIsFull(q)) { printf("队列已满!\n"); return 0; } q->data[q->tail++] = data; return 1;}
(6)出队操作
DATA *SeqQueueOut(SeqQueue *q){ if (SeqQueueIsEmpty(q)) { printf("队列已空!\n"); return NULL; } return &(q->data[q->head++]);}
(7)获取队头元素
DATA *SeqQueuePeek(SeqQueue *q){ if (SeqQueueIsEmpty(q)) { printf("队列已空!\n"); return NULL; } return &(q->data[q->head]);}
三、循环队列
由于每次出队后,队头的指针都向后移动,这时候就会出现一个问题,就是假溢出。如下图所示:
tail已指向队尾,这时进行入队操作时,虽然前面还有空位置,但仍然显示队列已满。为了解决这个问题,就提出了循环队列。
循环队列就是将队列的首尾相连构成一个环形区域,当在第n个位置进行元素的入队操作后,下一个地址就翻转为1
循环队列结构图:
在循环队列中,主要需要计算队尾tail和队头head的序号
以入队操作为例:
1、将队尾序号加1,即tail=tail+1
2、若tail=n+1,则tail=1
其实前2步,可以使用表达式tail=(tail+1)%n
3、若head=tail,即队尾和队头重合了,表示队列已满提示队列溢出
4、若未溢出,将元素入队即可
(1)定义循环队列的结构
#define QUEUEMAX 15typedef struct{ DATA data[QUEUEMAX]; int head; int tail;} CycQueue;
(2)初始化队列
CycQueue *CycQueueInit(){ CycQueue *q; if (q=(CycQueue *)malloc(sizeof(CycQueue))) { q->head = 0; q->tail = 0; return q; } return NULL;}
(3)释放队列
void CycQueueFree(CycQueue *q){ if (q) free(q);}
(4)获取队列状态
/**判断队列是否为空*/int CycQueueIsEmpty(CycQueue *q){ return (q->head == q->tail);}/**判断队列是否已满*/int CycQueueIsFull(CycQueue *q){ return ((q->tail+1)%QUEUEMAX == q->head);}/**获取队列的长度*/int CycQueueLen(CycQueue *q){ int n; n = q->tail - q->head; if (n < 0) { n = QUEUEMAX + n; } return n;}
(5)入队操作
int CycQueueIn(CycQueue *q, DATA data){ if (CycQueueIsFull(q)) { printf("队列已满!\n"); return 0; } q->tail = (q->tail+1)%QUEUEMAX; q->data[q->tail] = data; return 1;}
(6)出队操作
DATA *CycQueueOut(CycQueue *q){ int head; if (CycQueueIsEmpty(q)) { printf("队列已空!\n"); return NULL; } head = q->head; q->head = (q->head +1)%QUEUEMAX; return &(q->data[head]);}
(7)获取队头元素
DATA *CycQueuePeek(CycQueue *q){ if (CycQueueIsEmpty(q)) { printf("队列已空!\n"); return NULL; } return &(q->data[q->head]);}