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

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

相关文章

来自专栏腾讯IVWEB团队的专栏

Fibonacci Sequences in JavaScript with/without recursive

本文主要介绍几种使用javascript实现斐波那契数列的方法。

990
来自专栏Java Edge

Mybatis#BaseExecutor源码解析BaseExecutor源码解析

BaseExecutor是Executor的一个子类,是一个抽象类,实现接口Executor的部分方法,并提供了三个抽象方法

1056
来自专栏专注 Java 基础分享

为并发而生的 ConcurrentHashMap(Java 8)

HashMap 是我们日常最常见的一种容器,它以键值对的形式完成对数据的存储,但众所周知,它在高并发的情境下是不安全的。尤其是在 jdk 1.8 之前,reha...

69011
来自专栏海天一树

小朋友学Java(13):控制台输入

C语言用scanf来输入,C++用cin来输入,java则用Scanner来输入。 程序 import java.util.*; public class Sc...

2746
来自专栏jeremy的技术点滴

Java开发小技巧_02

3924
来自专栏一“技”之长

让你的iOS应用程序支持运行JavaScript脚本:JavaScriptCore框架详解

    说到JavaScript脚本,iOS开发者都会想到一个名叫JavaScriptCore的框架。这个框架的确十分强大,其中封装了一套JavaScript运...

1702
来自专栏小狼的世界

JavaScript设计模式学习(四)单件(Singleton Pattern)

单件是JavaScript中最基本、最有用的设计模式,而你今后也会经常的使用这个模式。通过单件,我们可以把统一到一个逻辑单元中并且提供一个唯一的入口,这就保证你...

1084
来自专栏小勇DW3

Mybatis使用动态代理实现拦截器功能

  拦截器顾名思义为拦截某个功能的一个武器,在众多框架中均有“拦截器”。这个Plugin有什么用呢?或者说拦截器有什么用呢?可以想想拦截器是怎么实现的。Plug...

1802
来自专栏算法与数据结构

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

2646
来自专栏架构之路

Spring 数据库连接(Connection)绑定线程(Thread)的实现

最近在看spring事务的时候在想一个问题:spring中的很多bean都是单例的,是非状态的,而数据库连接是一种有状态的对象,所以spring一定在创建出co...

3433

扫码关注云+社区