链队列

一、链队列的基本概念

队列的链式存储就是用一个线性链表来表示队列,称为链队,一般用单链表表示。

为了操作上的方便,需要一个头指针和尾指针分别指向链队列的队头和队尾元素。图形表示如下。

链队列的图形示意图:
链队列的图形表示
front 指向链队的队头元素,rear指向链队的队尾元素。
删除出队时只要修改队头指针,插入入队时只要修改队尾指针。

二、链队列的实现

typedef int DataType;   // 这里以整型为队列的数据类型

class QueueNode {
  public:
    DataType data;
    QueueNode *next;
    QueueNode() {
      next = NULL;
    }
}

class LinkQueue {
  private:
    QueueNode *front;
    QueueNode *rear;

  public:
    LinkQueue() {   // 构造一个新的空队列
      front = NULL;
      rear = NULL;
    }

    ~LinkQueue() {  // 销毁一个已存在的队列
      QueueNode *p, *q;
      p = front;

      while(p) {  // 删除链上所有的结点
        q = p;
        p=p->next;
        delete q;
      }

      front = NULL;   // 置为空表示空队列
      rear = NULL;  // 置为空表示空队列
    }

    int Empty_Queue();  // 判断队列是否为空
    int En_Queue(DataType e);   // 将元素e插入队尾
    int De_Queue(DataType &e);  // 从队头删除一个元素到e中返回
    int Front_Queue(DataType &e);   // 从队头取出一个元素到e中返回
}

(一)判断链队列是否为空

算法思想:只需判断front和rear是否都等于NULL。

int LinkQueue::Empty_Queue() {
  return (front == NULL && rear == NULL);
}

(二)进队操作

算法思想:首先申请新结点,不成功则失败退出;否则,将申请的结点插入单链表的表尾。注意,此时如果原来的队列非空,只需修改队尾指针即可;若原来队列为空,则不仅要修改rear,还需要修改front后再返回成功标志。

int LinkQueue::En_Queue(DataType e) {
  QueueNode *p = new QueueNode;

  if (p) {  // 申请结点成功
    p->data = e;

    if (rear) { // 原队列为非空队列,入队元素直接插入单链表的尾部
      rear->next = p;
      rear = p;
    } else {  // 原队列为空队列,插入元素既是队头元素也是队尾元素
      front = rear = p;
    }
    
    return 1;
  } else
    return 0;
}

(三)出队操作

算法思想:首先判断队列是否为空,为空,则失败退出;否则,删除队头指针指向的结点。注意,此时如果原来的队列只有一个结点,则删除队头指针指向的结点后成了空队列,因此还要修改队尾指针。

int LinkQueue::De_Queue(DataType &e) {
  QueueNode *p;

  if (!Empty_Queue()) {
    p = front;
    e = p->data;
    front = front->next;  // 修改队头指针

    if (!front) { // 删除出队元素后队列成了空队列,要修改队尾指针
      rear = NULL;
    }

    delete p;
    return 1;
  } else
    return 0;
}

(四)取队头元素操作

算法思想:首先判断队列是否为空,为空则失败退出;否则,取出队头指针front指向的结点的值。

int LinkQueue::Front_Queue(DataType &e) {
  if (!Empty_Queue()) {
    e = front->data;
    return 1;
  } else
    return 0;
}
用户头像
登录后发表评论