3.2.2 队列的顺序存储结构.md

↩返回主页

⬅上一节 / 下一节➡

---

3.2.2 队列的顺序存储结构

  顺序队列就是采用顺序存储的队列。

• C 语言描述：

  #define MaxSize 50
  typedef struct {
      ElemType data[MaxSize];
      int front, rear;
  } SqQueue;

  • front 指向队头元素，rear 指向队尾元素的下一位置

  • （或，与上述二选其一）front 指向队头元素的前一位置，rear 指向队尾元素

  • 初始化时：front == rear == 0

• 顺序队列的三种结论：

  • 队列空条件：Q.front == Q.rear

  • 队列长计算：Q.rear - Q.front

  • 队列满条件：Q.rear == MaxSize？

    • 特别强调： 这样不能判断队列满，存在假溢出问题！

    • 我们必须再加上一个判定条件：Q.front == 0

---

  循环队列 就是把（存储队列的）顺序队列在逻辑上视为一个环。

• 由于 front 指针插入时，存在着队头到队尾，rear 指针删除时，存在着队尾到队头，所以我们为了统一操作，均使用取余处理（% MaxSize）

  • front 指针移动

    Q.front = (Q.front+1) % MaxSize

  • rear 指针移动

    Q.rear = (Q.rear+1) % MaxSize

  • 队列长度

    (Q.rear+MaxSize-Q.front) % MaxSize

---

• 思考一个问题？

  我们怎么设立判空和判满条件？

  • 判空条件：Q.front == Q.rear

  • 判满条件：Q.front == Q.rear

  显然矛盾！

• 解决方案

  • 方法一：牺牲一个存储单元（最常用）

    • 队空条件：Q.front == Q.rear

    • 队满条件：Q.front == (Q.rear+1)%MaxSize

  • 方法二：增加一个变量 Q.size 代表元素的个数

    • 队空条件：Q.size == 0

    • 队满条件：Q.size == MaxSize

  • 方法三：增加 tag 标识

    • 队空条件：Q.front==Q.rear && tag==0

    • 队满条件：Q.front==Q.rear && tag==1

---

• 循环队列基本操作

  • 初始化

    void InitQueue(SqQueue &Q) {
        Q.rear = Q.front = 0;
    }

  • 判队空

    bool isEmpty(SqQueue Q) {
        if(Q.rear == Q.front)
            return true;
        else
            return false;
    }

  • 入队

    bool EnQueue(SqQueue &Q, ElemType x) {
        if((Q.rear+1)%MaxSize == Q.front)
            return false;
        Q.data[Q.rear] = x;
        Q.rear = (Q.rear+1)%MaxSize;
        return true;
    }

  • 出队

    bool DeQueue(SqQueue &Q, ElemType &x) {
        if(Q.rear == Q.front)
            return false;
        x = Q.data[Q.front];
        Q.front = (Q.front+1)%MaxSize;
        return true;
    }

💡 题型

  xxx

单项选择题

1. xxxx（ ）

   A. xxx
   B. XX
   C. Xx
   D. xX
   
   

   查看解析

   答案：x

---

返回顶部⤴

-- 完 --