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

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头节点,而队尾指针指向终端节点。空队列时,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 条评论
登录 后参与评论

相关文章

来自专栏数据魔术师

数据结构-线性表|顺序表|链表(下)

1 1 1 哈喽。各位小伙伴好久不见,热心的小编赶在开学季又来给大家送上满满的干货了。祝大家开心快乐! 继上两次咱们聊了顺序表、单链表、静态链表等知识。那么热爱...

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

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

2856
来自专栏King_3的技术专栏

leetcode-598-Range Addition II

841
来自专栏行者常至

java 自定义注解之ElementType.PARAMETER

332
来自专栏aCloudDeveloper

算法导论第六章堆排序(一)

现在来看, 堆的含义大概有两种,一种是数据结构,一种是在一些语言中所定义的“垃圾回收机制”,如Java,在书本上的开篇强调了这两者,并强调若非特殊说明,皆把堆看...

20910
来自专栏calmound

HDU 3652 B-number(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3652 题意:类似3555,0-n之间某个数中包含13,且整个数能被13...

3126
来自专栏WD学习记录

牛客网 构造队列

小明同学把1到n这n个数字按照一定的顺序放入了一个队列Q中。现在他对队列Q执行了如下程序:

581
来自专栏蜉蝣禅修之道

LeetCode之Binary Tree Maximum Path Sum

884
来自专栏撸码那些事

【图解数据结构】 栈&队列

1245
来自专栏算法channel

二叉树非递归版的中序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

3025

扫码关注云+社区