首页 > 代码库 > 顺序队列代码
顺序队列代码
队列：一种特殊的线性表，其特性就是先进先出（FIFO），即从一端进从另一端出
队头：允许删除的一端 front
队尾：允许插入的一端 rear
如下图所示，出队和入队的流程：
---------------------------------------------------------------------------------------------------------------------------------------------------
可以发现，无论是出队还是入队，front指针 和 rear指针都会增加而不是减少，因此很容易造成溢出 和 空间浪费
因此队列因为存在溢出问题所以日常的软件很少使用队列，那么如何解决，先说说两个概念：
假设最大的存储空间是6
假溢出：front != 0 ,rear = M ，再有元素插入时发生溢出 称为假溢出，存储空间还有剩余，如上图最后一张
真溢出：front = 0 ,rear = M, 再有元素插入时发生溢出 称为真溢出，存储空间已满。
因此为了使得空间不被，因此需要允许假溢出行为，即像时钟那样超过最大值则从头开始存储。
所以可以 与 最大值 QUEUE_ MAX_SIZE 取余(mod) 来继续从头开始利用空间。
而真溢出会导致存储值被破坏因此不能允许发生。如果找到满足队列满了的条件就可以阻止真溢出行为。
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如上图，可以发现当队列空和满时，front == rear，因此为了判断队列是否真的满了，有如下三种方法：
方法一：少用一个存储单元
满的条件为
(rear + 1)%QUEUE_MAX_SIZE == front
空的条件为
rear == front
方法二：标志位
添加一个标志位 tag = 0
当入队成功 tag = 1，出队成功 tag = 0
满的条件为
rear == front && tag = 1
空的条件为
rear == front && tag = 0
方法三：计数器
添加一个计数器 count = 0
当入队成功 count++ ，出队成功 count0--
满的条件为
count > 0 && rear == front
空的条件为
count == 0
下面是队列的实现代码，使用第一种方法防止溢出
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
#define QUEUE_MAX_LEN 1024
typedef int Status;
typedef int ElemType;
typedef struct{
ElemType * base; //基地址
int front; //头偏移量
int rear; //尾偏移量
} sqQueue;
/***********初始化**********/
Status initQueue(sqQueue *Q){
Q->base = (ElemType*)malloc(QUEUE_MAX_LEN * sizeof(ElemType));
Q->front = Q->rear = 0;
return OK;
}
/**********是否空**********/
Status isEmpty(sqQueue Q){
if(Q.front == Q.rear)return TRUE;
else return FALSE;
}
/**********是否满**********/
Status isFull(sqQueue Q){
if(Q.rear % QUEUE_MAX_LEN +1 == Q.front)return TRUE;
else return FALSE;
}
/**********获取长度**********/
Status getLength(sqQueue Q){
return (Q.rear - Q.front + QUEUE_MAX_LEN) % QUEUE_MAX_LEN;
}
/*********获取头值**********/
Status getHead(sqQueue Q,ElemType *e){
if(isEmpty(Q))return ERROR;
*e = *(Q.base + Q.front);
return OK;
}
/***********入队**********/
Status enQueue(sqQueue *Q,ElemType e){
if(isFull(*Q))return OVERFLOW;
*( Q->base + Q->rear ) = e;
Q->rear = (Q->rear + 1)%QUEUE_MAX_LEN;
return OK;
}
/***********出队**********/
Status deQueue(sqQueue *Q,ElemType *e){
if(isEmpty(*Q))return OVERFLOW;
*e = *(Q->base + Q->front);
Q->front = (Q->front +1 )%QUEUE_MAX_LEN;
return OK;
}
/***********打印队列**********/
//事实上队列是不能这么用的
//这里只是为了能看到先进先出的效果
/****************************/
Status printQueue(sqQueue Q){
if(isEmpty(Q))
printf("queue is empty\n");
int len = getLength(Q);
while(Q.rear - Q.front){
printf("[%d] ",*(Q.base+Q.front));
Q.front = (Q.front+1)%QUEUE_MAX_LEN;
}
printf("\n");
return OK;
}
int main(){
char sel;
int val;
sqQueue Q;
initQueue(&Q);
while(1){
system("clear");
printf("\n");
printQueue(Q);
printf("e = enQueue\nd = deQueue\n");
printf("g = getHead\n");
printf("plese enter your choose[e|d|g]:");
sel = getchar();
if(sel == ‘e‘){
printf("[EnQueue]enter value:");
scanf("%d",&val);
enQueue(&Q,val);
}
else if(sel == ‘d‘){
deQueue(&Q,&val);
printf("[DeQueue]value is %d\n",val);
sleep(1);
}
else if(sel == ‘g‘){
getHead(Q,&val);
printf("[HeadVal]value is %d\n",val);
sleep(1);
}
}
return 0;
}
运行结果
顺序队列代码