一、队列的定义
线性表:是具有相同数据类型的n(n≥0)个数据元素的有限序列,其中n为表长,当n=0时,线性表是一个空表。若用L命名线性表,则其一般表示为L=(a1,a2,...,ai,ai+1,...,an)。
栈:是只允许在一段进行插入或删除操作的线性表。
队列:是只允许在一端进行插入,在另一端删除的线性表。
队头、队尾、空队列
特点:先进先出(FIFO) First in first out
二、队列的基本操作
2.1 队列的定义
#define MaxSize 10//定义队列中元素的最大个数 typedef struct{ ElemType
data[MaxSize];//用静态数组存放队列元素 int front,rear;//队头指针和队尾指针 }SqQuene; void
testQueue(){ SqQueue Q;//声明一个队列(顺序存储) }//后续操作...
2.2 初始化操作
void InitQueue(SqQueue &Q){ //初始时,队头、队尾指针指向0 Q.rear=Q.front=0; } void
testQueue(){ //声明一个队列(顺序存储) SqQueue Q; InitQueue(Q); //后续操作... }
判断队列是否为空
bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front)//队空条件 return true; else return
false; }
2.3 入队操作
bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错
Q.data[Q.rear]=x;//将x插入队尾 Q.rear=Q.rear+1;//队尾指针后移 return true; }
Q.data[Q.rear]=x——将 x放入队尾指针所指的位置
Q.rear=Q.rear+1——队尾指针加一,后移
静态数组存满后,队尾指针是10
所以队列已满的条件是:rear==MaxSize????
答案不是
当取出元素时,rear还是等于10,不会变,但这时候队列有空
所以更改代码,采用取余操作Q.rear=(Q.rear+1)%MaxSize,将存储空间从逻辑上变成了“环状”
bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错
Q.data[Q.rear]=x;//将x插入队尾 Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }
因为判断队满的条件是判断rear==front,因此必须牺牲一个单元
队列已满的条件:队尾指针的在下一个位置是队头,即(Q.rear+1)%MaxSize==Q.front;
bool EnQueue(SqQueue &Q,ElemType x){ if((Q,rear+1)%MaxSize==Q.front)//判断队满条件
return false;//队满则报错 Q.data[Q.rear]=x;//将x插入队尾
Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }
队列元素个数:
(rear+MaxSize-front)%MaxSize
2.4 出队操作
只能让队头元素出队
//出队(删除一个队头元素,并用x返回) bool DeQueue(SeQueue &Q,ElemType &x){ if(Q.rear==Q.front)
return false;//队空则报错 x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return
ture; }
2.5 队列查找
获得队头元素,用x返回
bool GetHead(SqQueue Q,ElemType &x){ if(Q.rear==Q.front) return false;//队空则报错
x=Q.data[Q.front]; return true; }
其他元素呢???
2.6 不浪费内存条件下判断队列已满/已空
方法二:
#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int
size;//队列当前长度 }SqQuene;
初始化时rear==front==0;size=0;
插入成功:size++
删除成功:size--;
队满条件:size==MaxSize;
队空条件:size==0;
方法三:
#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int
tag;//最近进行的是删除(0)/插入(1) }SqQuene;
初始化时,rear=front=0;tag=0;
每次删除操作成功时,都令tag=0;
每次插入操作成功时,都令tag=1;
只有删除操作才可能导致队空,因此队空条件为:front==rear&&tag==0;
同理,队满条件为:front==rear&&tag==1;
2.7 rear指针指向队尾元素情况
判空:
(Q.rear+1)%MaxSize==Q,front
判满:
(Q.rear+1)%MaxSize==Q,front
两种方法:
1.牺牲一个存储单元:
rear与front隔了两个单元,队满、隔了 一个单元,队空
2.增加辅助变量
size、tag
三、链式存储实现队列
3.1 队列的链式实现
typedef struct LinNode{//链式队列结点 ElemType data; struct LinkNode *next;
}LinkNode; typedef struct{//链式队列 LinkNode *front,*rear;//队列的队头和队尾指针 }LinkQueue;
3.2 初始化
带头结点
typedef struct LinkNode{ ELEMtype data; struct LinkNode *next; }LinkNode;
typedef struct{ LinkNode *front,*rear; }LinkQueue; //初始化队列 void
InitQueue(LinkQueue &Q){ //初始时 front、rer都指向头结点
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL;//判空操作 }
void testLinkQueue(){ LinkQueue Q;//声明一个队列 InitQueue(Q);//初始化一个队列 //后续操作.... }
其他判空操作:
bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false;
}
不带头结点
3.3 入队操作
带头结点
void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s=(LinkNode
*)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL;
Q.rear->next=s;//新结点插入rear之后 Q.rear=s;//修改表尾指针 }
元素都是队尾插入,所以s的next指针为空
不带头结点
3.4 出队操作
带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.front==Q.rear) return false;//空队
LinkNode *p=Q.front->next; x=p->data;//用变量x返回队头元素
Q.front->next=p->next;//修改头结点的next指针 if(Q.rear==p)//此次是最后一个结点出队
Q.rear=Q.front;//修改rear指针 free(p);//释放结点空间 return true; }
不带头结点
四、双端队列
只允许从两端插入、两端删除的线性表
若只使用其中一端插入、删除操作,则效果等同于栈