本篇介绍队列的链式存储,因为队列是在两头插入和删除的逻辑结构,因此要用具体的物理存储结构的时候,需要用到两个指针。一个是头指针,一个是尾指针。头指针指向队头指针,尾指针指向队尾指针,即单链表的最后一个结点。下面介绍有关链队列的算法实现。

一:队列的链式存储类型

typedef struct{
  ElemType data;
  struct LinkNode *next;
}LinkNode;
typedef struct{
  LinkNode *front,*rear;
}LinkQueue

  当Q.front == NULL且Q.rear == NULL,链式队列为空。
  入队时,先建立一个新结点,然后将新结点插入到链表的尾部,并让Q.rear指向这个新插入的结点,若原队列为空,让Q.rear也指向这个结点。
  出队时,先取队头元素,将其从链表中删除,并让Q.front指向下一个结点,若该结点是最后一个结点,则置Q.front与Q.rear都为NULL。
  上面的是不带头结点的链队列,如果需要简单操作,则需要将队列设计成一个带头结点的单链表。
  使用链队列不会出现存储分配不合理和"溢出"的问题。适合需要多个队列的算法问题。

二:链队列的基本操作

1.初始化

void InitQueue(ListQueue &Q){
  Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
  Q.front -> next = NULL;
}

2.判队空

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

3.入队

void EnQueue(LinkQueue &Q,ElemType x){
  LinkQueue *s = (LinkNode*)malloc(sizeof(LinkNode));
  s->data = x;
  s->next = NULL;
  Q.rear->next = s;
  Q.rear = s;
}

4.出队

bool DeQueue(LinkQueue &Q,ElemType &x){
  if(Q.front == Q.rear) retun false;
  LinkNode *p = Q.front->next;
  x = p->data;
  Q.front->next = p->next;
  if(Q.rear == p)
    Q.rear = Q.front;         //若原队列中只有一个结点,删除后变空
  free(p);
  return true;
}

三:队列的应用

1.双端队列

  双端队列是指允许两端都可以进行入队和出队的队列,也有输入受限的双端队列和输出受限的双端队列,在实际应用中用到的地方也有很多。

2.其他应用

  栈在括号匹配和表达式求值中用处很多,以及所有用到递归的算法都可用栈来实现其非递归算法。
  对于队列来说,队列在二叉树层次遍历以及计算机系统中用处广泛,在打印机打印和CPU资源竞争处理中用处也很广泛。

3.矩阵的压缩存储

  数组是线性表的推广,所以可以用数组类似栈或者队列进行一些复杂操作,最常用的就是矩阵的压缩存储操作,可以类似栈或者队列进行操作。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/ITXiaoAng/p/13675819.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!