数据结构:队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头节点,而队尾指针指向终端节点。空队列时,front和rear都指向头节点。

示例程序:(改变自《大话数据结构》)

#include<iostream>
using namespace std;

typedef int ElemType;

typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node, *NodePtr;

typedef struct
{
    NodePtr front;/* 队头、队尾指针 */
    NodePtr rear;
} LinkQueue;
/* 构造一个空队列 */
bool InitQueue(LinkQueue *Lp)
{
    cout << "Init Queue ..." << endl;
    NodePtr p = (NodePtr)malloc(sizeof(Node));
    p->next = NULL;
    Lp->front = Lp->rear = p;
    return true;
}
/* 销毁队列,包括头节点 */
bool DestroyQueue(LinkQueue *Lp)
{
    cout << "Destroy Queue ..." << endl;
    while (Lp->front)
    {
        Lp->rear = Lp->front->next;
        free(Lp->front);
        Lp->front = Lp->rear;
    }

    return true;
}
/* 清为空队列,保留头节点 */
bool ClearQueue(LinkQueue *Lp)
{
    cout << "Clear Queue ..." << endl;
    NodePtr p = Lp->front->next;
    Lp->front->next = NULL;
    Lp->rear = Lp->front;
    NodePtr q;

    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }

    return true;
}

bool QueueEmpty(LinkQueue LQ)
{
    return LQ.front == LQ.rear;
}

int QueueLength(LinkQueue LQ)
{
    int i = 0;
    if (LQ.front == NULL)
        return 0;
    NodePtr p = LQ.front->next;
    while (p)
    {
        ++i;
        p = p->next;
    }

    return i;
}

bool GetHead(LinkQueue LQ, ElemType *pe)
{
    NodePtr p;
    if (LQ.front == LQ.rear)
        return false;
    p = LQ.front->next;
    *pe = p->data;
    cout << "Get Head Item : " << *pe << endl;
    return true;
}

/* 插入元素Elem为队列的新的队尾元素 */
bool EnQueue(LinkQueue *Lp, ElemType Elem)
{
    cout << "EnQueue Item " << Elem << endl;
    NodePtr s = (NodePtr)malloc(sizeof(Node));
    s->data = Elem;
    s->next = NULL;
    Lp->rear->next = s;
    Lp->rear = s;

    return true;
}
/*删除队列的队头元素,用*pe返回其值 */
bool DeQueue(LinkQueue *Lp, ElemType *pe)
{
    if (Lp->front == Lp->rear)
        return false;
    NodePtr p = Lp->front->next;
    *pe = p->data;
    cout << "DeQueue Item " << *pe << endl;
    Lp->front->next = p->next;
    if (Lp->rear == p)/* 若队头就是队尾,则删除后将rear指向头结点*/
        Lp->rear = Lp->front;
    free(p);

    return true;
}
/* 从队头到队尾依次对队列中每个元素输出 */
bool QueueTraverse(LinkQueue LQ)
{
    cout << "Queue Traverse ..." << endl;
    NodePtr p = LQ.front->next;
    while (p)
    {
        cout << p->data << ' ';
        p = p->next;
    }

    cout << endl;
    return true;
}

int main(void)
{
    LinkQueue LQ;
    InitQueue(&LQ);
    for (int i = 0; i < 5; i++)
        EnQueue(&LQ, i);
    QueueTraverse(LQ);
    int result;
    GetHead(LQ, &result);
    DeQueue(&LQ, &result);
    QueueTraverse(LQ);
    if (!QueueEmpty(LQ))
        cout << "Queue Length : " << QueueLength(LQ) << endl;
    /*ClearQueue(&LQ);*/
    DestroyQueue(&LQ);
    cout << "Queue Length : " << QueueLength(LQ) << endl;

    return 0;
}

输出为:

总的来说,如果可以确定队列的最大值,建议用循环队列,如果不能预估队列的长度,则用链队列。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏伟哥专栏

C#封装v5 COS API实践-put方法

963
来自专栏大内老A

我的WCF之旅(4):WCF中的序列化[下篇]

XMLSerializer 提到XMLSerializer,我想绝大多数人都知道这是asmx采用的Serializer。首先我们还是来看一个例子,通过比较Ma...

18910
来自专栏小樱的经验随笔

UVA 11292 Dragon of Loowater(简单贪心)

Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

2657
来自专栏Hongten

Hibernate的二级缓存 下

import org.hibernate.Session; import org.hibernate.SessionFactory; import org.hi...

501
来自专栏Janti

Java基础巩固——反射

什么是反射 ----    反射机制就是指程序运行时能够获取自身的信息。在Java中,只要给出类的名字,就可以通过反射机制来获取类的信息 哪里用的到反射机制 -...

2827
来自专栏JetpropelledSnake

SNMP学习笔记之SNMP树形结构介绍

Iso(1).org(3).dod(6).internet(1).private(4).transition(868).products(2).chassis(...

733
来自专栏恰同学骚年

数据结构基础温故-1.线性表(中)

在上一篇中,我们学习了线性表最基础的表现形式-顺序表,但是其存在一定缺点:必须占用一整块事先分配好的存储空间,在插入和删除操作上需要移动大量元素(即操作不方便)...

762
来自专栏函数式编程语言及工具

泛函编程(6)-数据结构-List基础

  List是一种最普通的泛函数据结构,比较直观,有良好的示范基础。List就像一个管子,里面可以装载一长条任何类型的东西。如需要对管子里的东西进行处...

1976
来自专栏猿人谷

顺序循环队列

1 //循环队列的顺序存储表示与实现 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 /**...

1878
来自专栏从流域到海域

《数据结构》 队列(Queue)操作代码集合

队列基本操作代码集合,来自《数据结构-用C语言描述》(第二版) 高教社 队列是受限制的链表或顺序表(只能从队首取结点,先进先出FIFO),相关操作可以...

1795

扫码关注云+社区