队列

微信扫一扫,分享到朋友圈

队列

一、什么是队列

队列(Queue):具有一定操作约束的线性表

  • 插入和删除操作: 只能在 一端插入 ,而在 另一端删除

  • 数据插入:入队列(AddQ)

  • 数据删除:出队列(DeleteQ)

  • 先来先去服务

  • 先进先出: (FIFO)

二、队列的抽象数据类型描述

类型名称: 队列( (Queue)

数据对象集: 一个有 (0) 个或多个元素的有穷线性表。

操作集: 长度为 (MaxSize) 的队列 (Qin{Queue}) ,队列元素 (itemin{ElementType})

  1. Queue CreateQueue(int MaxSize) :生成长度为 (MaxSize) 的空队列;
  2. int IsFullQ(Queue Q, int MaxSize) :判断队列 (Q) 是否已满;**
  3. void AddQ(Queue Q, ElementType item) :将数据元素 (item) 插入队列 (Q) 中;
  4. int IsEmptyQ(Queue Q) :判断队列 (Q) 是否为空;**
  5. ElementType DeleteQ(Queue Q) :将队头数据元素从队列中删除并返回。

三、队列的顺序存储实现

队列的顺序存储结构通常由一个 一维数组 和一个记录队列头元素位置的变量 front 以及一个记录队列尾元素的变量 rear 组成。

/* c语言实现 */

#define MaxSize <储存数据元素的最大个数>
struct QNode{
  ElementType Data[MaxSize];
  int rear;
  int front;
};
typedef struct QNode *Queue;

例: 一个工作队列

四、循环队列

思考:

  1. 上述这种循环队列的方案: 堆栈空和满 的判别条件是什么?
  2. 为什么会出现空、满无法区分?根本原因是什么?

解决方案:

  1. 使用额外标记: (Size) 或者 (tag)
  2. 仅使用 (n-1) 个数组空间

4.1 入队列

Frontrear 指针的移动采用“ 加1取余 ”法,体现了顺序存储的“ 循环使用 ”。

/* c语言实现 */

void AddQ(Queue PtrQ, ElementType item)
{
  if ((PtrQ->rear + 1) % MaxSize == PtrQ->front){
    printf("队列满");
    return ;
  }
  PtrQ->rear = (PtrQ->rear+1) % MaxSize;
  PtrQ->Data[PtrQ->rear] = item;
}

4.2 出队列

/* c语言实现 */

ElementType DeleteQ(Queue PtrQ)
{
  if (PtrQ->front = PtrQ->rear){
    printf("队列空");
    return ERROR;
  } else {
    PtrQ->front = (PtrQ->front + 1) % MaxSize;
    return PtrQ->Data[PtrQ->front];
  }
}

五、队列的链式存储实现

队列的链式存储结构也可以用一个 单链表 实现。插入和删除操作分别在链表的两头进行; 队列指针front应该在链表的头部;rear应该在链表的尾部。因为front在链表的尾部,删除操作后找不到上一个元素。

/* c语言实现 */

struct Node{
  ElementType Data;
  struct Node *Next;
}
struct QNode{ /* 链队列结构 */
  struct Node *rear; /* 指向队尾结点 */
  struct Node *front; /* 指向队头结点 */
};
typedef struct QNode *Queue;
Queue PtrQ;

5.1 出队列

不带头结点的链式队列 出队操作 的一个示例:

/* c语言实现 */

ElementType DeleteQ(Queue PtrQ)
{
  struct Node *FrontCell;
  ElementType FrontElem;
  
  if (PtrQ->front == NULL){
    printf("队列空"); return ERROR;
  }
  FrontCell = PtrQ->front;
  if (PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */
    PtrQ->front = PtrQ->rear = NULL; /* 删除后对列置为空 */
  else
    PtrQ->front = PtrQ->front->Next;
  FrontElem = FrontCell->Data;
  free(FrontCell); /* 释放被删除结点空间 */
  return FrontElem;
}

微信扫一扫,分享到朋友圈

队列

神州数码2019中报净利润3.97亿 云计算业务增速107.93%

上一篇

“ ZAO ”换脸刷屏,但背后隐私、版权、伦理的风险细思恐极

下一篇

你也可能喜欢

队列

长按储存图像,分享给朋友