大话数据结构九:队列的链式存储结构(链队列)

1. 链队列的特点:

链队列其实就是单链表,只不过它是先进先出的单链表,为了实现方便,程序中设置了队头(front),队尾(rear)两个指针。

2. Java使用链表实现队列:

//结点类,包含结点的数据和指向下一个节点的引用
public class Node<E> {
    private E data; // 数据域
    private Node<E> next; // 指针域保存着下一节点的引用  

    public Node() {
    }  

    public Node(E data) {
        this.data = data;
    }  

    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }  

    public E getData() {
        return data;
    }  

    public void setData(E data) {
        this.data = data;
    }  

    public Node<E> getNext() {
        return next;
    }  

    public void setNext(Node<E> next) {
        this.next = next;
    }
}

更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

// Java实现链队列
public class LinkedQueue<T> {
    private Node<T> front; // 记住队头结点
    private Node<T> rear; // 记住队尾结点
    private int size; // 记住链表长度  

    public LinkedQueue() {
        front = rear = null;
        size = 0;
    }  

    // 将元素追加到队列尾部
    public boolean enqueue(T data) {
        Node<T> newNode = new Node<T>(data);
        if (isEmpty()) { // 判断队列是否为空
            front = rear = newNode;
        } else {
            rear.setNext(newNode); // 将新进来的结点设置为尾结点
            rear = newNode;
        }
        size++;
        System.out.println(data + "入队..");
        return true;
    }  

    // 队列头部的第一个元素出队
    public T dequeue() {
        T data = null;
        if (isEmpty()) {
            System.out.println("队列为空,无法出队..");
        } else {
            if (front.getNext() == null) { // 队列中只有一个结点
                rear = null;
            }
            data = front.getData();
            front = front.getNext(); // 将原队头的下一个结点设置为队头
            System.out.println(data + "出队..");
            size--;
        }
        return data;
    }  

    // 获取链队列的长度
    public int size() {
        return size;
    }  

    // 判断链队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }  

    // 清空链队列
    public void clear() {
        front = rear = null;
        size = 0;
    }  

    // 打印队列中的元素
    public void display() {
        if (!isEmpty()) {
            Node<T> nextNode = front;
            for (int i = 0; i < size(); i++) {
                System.out.print(" " + nextNode.getData());
                nextNode = nextNode.getNext();
            }
        }
    }  

    // 测试方法
    public static void main(String[] args) {
        LinkedQueue<String> queue = new LinkedQueue<String>();
        queue.enqueue("张三");
        queue.dequeue();
        queue.dequeue();
        queue.enqueue("李四");
        queue.enqueue("王五");
        queue.enqueue("赵六");
        queue.dequeue();
        queue.enqueue("田七");
        queue.dequeue();
        queue.enqueue("周八");
        System.out.println("队列中元素个数为: " + queue.size());
        System.out.print("打印队列中的元素: ");
        queue.display();
    }
}

3. 链队列和循环队列比较:

1.) 时间上:循环队列事先申请好空间,使用期间不释放。链队列每次申请和释放结点存在一些时间开销,如果入队出队操作频繁,链队列性能稍差。

2.) 空间上:循环队列必须有一个固定长度,所以就有了存储元素个数和空间浪费的问题。链队列不存在这个问题,所以在空间上更为灵活。

4. 什么时候使用链队列:

1.) 在可以确定队列长度最大值的情况下,建议用循环队列。

2.) 如果无法预估队列的长度,则用链队列 。

作者:csdn博客 zdp072

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索循环队列
, 队列
, node
, 结点
, 队
, 链队列
, data
, queue
, public
, 循环队列存储
, mode getnext
, linkedqueue
, c链式循环嵌套
一个队列
,以便于您获取更多的相关知识。

时间: 2016-12-30

大话数据结构九:队列的链式存储结构(链队列)的相关文章

数据结构的C++实现之队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列.为了操作上的 方便,我们将队头指针指向链队列的头节点,而队尾指针指向终端节点.空队列时,front和rear都指向头节点. 示例程序 :(改变自<大话数据结构>) #include<iostream> using namespace std; typedef int ElemType; typedef struct Node { ElemType data; struct Node *nex

大话数据结构二:线性表的链式存储结构(单链表)

1. 线性表的链式存储结构:指的是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的,这就意味着这些数据元素可以存在内存未被占用的任意位置. 2. 结点:结点由存放数据元素的数据域和存放后继结点地址的指针域组成. 1.)顺序存储结构中,每个数据元素只需要存数据元素的信息就可以了. 2.)链式存储结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址. 3.)链表中第一个结点叫头结点,它的存储位置叫做头指针,它的数据域可以不存储任何信息,链表的最后一个结

数据结构的C++实现之栈的链式存储结构

当单链表限定只能在头部进行插入和删除操作的时候,即为链栈,一般我们会将单链表的头指针和栈的栈顶指针top合二 为一,通常对链栈来说,是不需要头节点的,因为我们维护了栈顶指针.对于链栈来说,基本不存在栈满的情况,除非内存 已经没有可以使用的空间,对于空栈来说,链表原定义是头指针指向空,那么链栈的空其实就是top = = NULL的时候.   示例代码:(改编自<大话数据结构>) #include <iostream> using namespace std; typedef int

JAVA 实现二叉树(链式存储结构)_java

二叉树的分类(按存储结构) 树的分类(按存储结构)              顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根:                                    完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示:   二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private St

大话数据结构二十一:图的存储结构之邻接多重表

1.引言: 若要删除左边的(V0,V2)这条边,需要对图下表的阴影两个结点进行删除操作. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 2.邻接多重表的存储结构: iVex和jVex:是与某条边依附的两个顶点在顶点表中的下标. iLink:指向依附顶点iVex的下一条边. jLink:指向依附顶点jVex的下一条边. 3.邻接多重表示意图绘制: 作者:csdn博客 zdp072

大话数据结构二十:图的存储结构之十字链表

1. 引言: 对于有向图来说,邻接表是有缺陷的: 邻接表:关心了出度问题,想了解入度就必须要遍历整个图才知道. 逆邻接表:解决了入度,却不了解出度的情况. 能否把邻接表和逆邻接表结合起来呢?答案就是:使用十字链表. 2.十字链表存储结构: 顶点表结点结构: firstin:表示入边表头指针,指向该顶点的入边表中第一个结点. firstout:表示出边表头指针,指向该顶点的出边表中的第一个结点. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn

大话数据结构三:线性表的链式存储结构(静态链表)

1. 静态链表:用数组描述的链表叫静态链表,通常为方便数据插入,我们会把数组建的大一些. 2. 数组元素(node):由两个数据域组成(data,cursor).数据域data用来存放数据元素,也就是通常我们要处理的数据:而cursor相当于单链表中的指针,存放该元素的后继在数组中的下标. 3. Java实现静态链表: // 静态链表 class StaticLinkedList { private int size; private Node[] node = new Node[100]; /

大话数据结构五:线性表的链式存储结构(双向链表)

1. 双向链表:在单链表的每个结点中,再设置一个指向其前驱结点的指针域,那么在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱. 2. 单链表和双向链表比较: 单链表:总是要从头到尾找结点,只能正遍历,不能反遍历. 双向链表: 可以从头找到尾,也可以从尾找到头,即正反遍历都可以,可以有效提高算法的时间性能,但由于每个结点需要记录两份指针,所以在空间占用上略多一点,这就是通过空间来换时间. 3. Java实现双向链表: // 双向链表 public class DoubleLi

大话数据结构四:线性表的链式存储结构(单向循环链表)

1. 单向循环链表:将单链表尾结点的指针端由空指针改为指向头结点,使整个单链表形成一个环,这种头尾相接的单链表称为单向循环链表.   2. 单向循环链表和单链表实现的区别: 1.)添加一个结点到单向循环链表末尾时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为null. 2.)判断是否到达表尾时,单向循环链表可以判断该结点是否指向头结点,单链表只需要知道是否为null.   3.Java实现单向循环链表: // 单向循环链表 public class CircularLinked