队列的定义、循环队列的顺序存储结构及链式存储结构

1 队列的定义

1.1 文字定义

队列:只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

队列是一种先进先出(First In First Out)的线性表,简称FIFO结构。允许插入的一端称为队尾,允许删除的一端称为队头。

队列的定义、循环队列的顺序存储结构及链式存储结构

1.2 代码定义

伪代码定义:

ADT 队列(Queue)
Data
同线性表。元素具有相同的类型,相邻元素具有前驱和后继的关系。
Operation
InitQueue(*Q):初始化操作,建立一个空队列Q。
DestoryQueue(*Q):若队列Q存在,则销毁它。
ClearQueue(*Q):将队列Q清空。
QueueEmpty(Q):若队列Q为空,返回true,否则返回false。
GetHead(Q,*e):若队列Q存在且非空,用e返回队列Q的队头元素。
EnQueue(*Q,e):若队列Q存在,插入新元素e到队列Q中并成为队尾元素。
DeQueue(*Q,*e):删除队列Q中队头元素,并用e返回其值。
QueueLength(Q):返回队列Q的元素个数。
endADT

2 循环队列

2.1 循环队列的定义

循环队列:队列的这种头尾相接的顺序存储结构成为循环队列。

队列的定义、循环队列的顺序存储结构及链式存储结构

​rear​​​队尾结点,​​front​​​队头结点,空队列条件:​​frnotallow=near​​​,满队列条件:​​(rear+1)%QueueSize==front​​(取模“%”的目的就是为了整合rear与front大小为一个问题),如下图的例子,QueueSize=5,frnotallow=0,rear=4,(4+1)%5=0,此时队满。

通用计算队列长度的公式:(rear-front+QueueSize)%QueueSize

2.2 循环队列的顺序存储结构

循环队列的顺序存储结构代码如下:

typedef int QElemType;  // QElemType类型根据实际情况而定,这里假设为int

typedef struct{
QElemType data[MAXSIZE];
int front; // 头指针
int rear; // 尾指针,若队列不为空,指向队列尾元素的下一个位置
}SqQueue;

循环队列的初始化代码如下:

// 初始化空队列
Status InitQueue(SqQueue *Q){
Q->front = 0;
Q->near = 0;
return OK;
}

循环队列求队列长度代码:

// 返回队列Q的元素个数,也就是队列的当前长度
int QueueLength(SqQueue Q){
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

循环队列入队代码:

// 若队列未满,则插入元素e为Q新的队尾元素
Status EnQueue(SqQueue *Q,QElemType e){
if((Q->rear+1)%MAXSIZE) == Q->front){ // 队列满
return ERROR;
}
Q->data[Q->rear] = e; // 将元素e赋值给队尾
Q->rear=(Q->rear+1)%MAXSIZE; // rear指针向后移动一位,若到最后则转到数组头部
return OK;
}

循环队列的出队操作:

// 若队列不空,则删除Q中队头元素,用e返回其值
Status DeQueue(SqQueue *Q,QElemType *e){
if(Q->front == Q->rear){ // 队列空
return ERROR;
}
*e = Q->data[Q->front]; // 将队头元素赋值给e
Q->front = (Q->front+1)%MAXSIZE; // front指针后移,若到最后则转到数组头部
return OK;
}

3 队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出,我们将其称为链队列。

为了操作的方便,我们将队头指针指向链队列的头结点,而尾指针指向终端结点。

队列的定义、循环队列的顺序存储结构及链式存储结构

链队列的结构为:

typedef int QElemType;

typedef struct QNode{ //结点结构
QElemType data;
struct QNode *next;
}QNode.*QueuePtr;

typedef struct{ // 队列的链表结构
QueuePtr front,rear; // 队头队尾指针
}LinkQueue;

3.1 链队列的入队操作

入队操作时,其实就是再链表尾部插入结点,如图所示:

队列的定义、循环队列的顺序存储结构及链式存储结构

代码如下:

// 插入元素e为Q的新队尾元素
Status EnQueue(LinkQueue *Q,QElemType e){
QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); // 创建新结点
if(!s){ // 存储分配失败
exit(OVERFLOW);
}
s->data = e;
s->next = NULL;
Q->rear->next = s; // 把拥有元素e的新结点s赋值给源队尾结点的后继,步骤1
Q->rear = s; // 把当前s设置为队尾结点,rear指向s,步骤2
return OK;
}

3.2 链队列的出队操作

出队操作时,就是头结点的后继结点出队,将头结点的后继改为其后面结点,如图所示。

队列的定义、循环队列的顺序存储结构及链式存储结构

// 若队列不为空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
Status DeQueue(LinkQueue *Q,QElemType *e){
QueuePtr p;
if(Q->front == Q->rear){ // 队空
return ERROR;
}
p = Q->front->next; // 将预删除的队头结点赋值给p,步骤1
*e = p->data; // 将预删除的队头结点的值赋值给e
Q->front->next = p->next; // 将原队头结点的后继p->next赋值给头结点,步骤2
if(Q->rear=p){
Q->rear = Q->front; // 若队头就是队尾,则删除后将rear指向头结点,步骤3
}
free(p);
return OK;
}

4 总结

栈和队列都是特殊的线性表,只不过对插入和删除操作做了限制。

  • 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。(Last In Frist Out)
  • 队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。(First In First Out)

栈和队列均可以用线性表的顺序存储结构来实现,但都存在着顺序存储的一些弊端。因此它们各自有各自的技巧来解决这个问题。

  • 对于栈来说,如果是两个相同数据类型的栈,则可以用数组的两端作栈底的方法来两个栈共享数据,这就可以最大化地利用数组的空间。
  • 对于队列来说,为了避免数组插入和删除时需要移动数据,于是就引入了循环队列,使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗,使得本来插入和删除是​​的时间复杂度变成了O(1)
发表评论

相关文章