Tim的资源站

一、链队列的基本概念

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

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

链队列的图形示意图：

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;
}