当前位置:首页>Java>Java 高级教程>Java队列的实现

Java队列的实现

作者:githubofrico发布时间:2019-09-14 17:00:37地址:https://dwz.cn/AMenD9kw

Java队列的概念

什么是队列

队列,和栈一样,也是一种对数据的”存”和”取”有严格要求的线性存储结构。

与栈结构不同的是,队列的两端都”开口”,要求数据只能从一端进,从另一端出,如下图所示:

队列的存储结构

队列名词概念

通常,称进数据的一端为 “队尾”,出数据的一端为 “队头”,数据元素进队列的过程称为 “入队”,出队列的过程称为 “出队”。

队列遵循原则

不仅如此,队列中数据的进出要遵循 “先进先出” 的原则,即最先进队列的数据元素,同样要最先出队列。

拿上图 中的队列来说,从数据在队列中的存储状态可以分析出,元素 1 最先进队,其次是元素 2,最后是元素 3。此时如果将元素 3 出队,根据队列 “先进先出” 的特点,元素 1 要先出队列,元素 2 再出队列,最后才轮到元素 3 出队列。

队列和栈

栈和队列不要混淆,栈结构是一端封口,特点是”先进后出”;而队列的两端全是开口,特点是”先进先出”。

因此,数据从表的一端进,从另一端出,且遵循 “先进先出” 原则的线性存储结构就是队列

Java队列的实现

队列(基于数组的实现、基于链表的实现和基于栈的实现)的数据结构及其相关算法

队列结构包含三个要素

  • 队头指针head

  • 队尾指针rear

  • 队列大小size,具体操作包括:

队列的常用操作

  • 入队操作put

  • 出队操作pop

  • 查看队头元素peek

  • 查看队列的大小

  • 查看队列是否为空

构造节点类Node

准备工作,先构件一个结点类 Node


/**
 * Title: 结点类 
 * Description: 队列的基本元素
 */
 public class Node<T> {
    //包可见性
    Node<T> next;   
    T data;

    /**
     * 构造函数
     * 
     * @description 构造一个新节点
     * @param data 新元素数据
     * @param next 新元素与链表结合节点
     */
    public Node(T data) { 
        this.data = data;
    }

    @Override
    public String toString() {
        return data.toString();
    }
}

Java队列(基于数组的实现)

Java队列核心数据结构

import java.util.Arrays;


/**        
 * Title: 基于数组的队列实现     
 */      
public class SeqQueue<E> {


    /**  队列的存储结构 */      
    private Object[] queue;         
    private int size;
    private int maxSize;    // 最大容量

    public SeqQueue(int maxSize){
        this.maxSize = maxSize;
        queue = new Object[maxSize];
    }
}

添加元素到队尾

public void put(E data){
    if(!isFull()){
        queue[size] = data;
        size ++;
    }
}

删除队头并返回队头元素的值

public E pop(){
    if (!isEmpty()) {
        E temp = (E) queue[0];
        for (int i = 0; i < size - 1; i++) {
            queue[i] = queue[i+1];
        }
        queue[size-1] = null;
        size--;
        return temp;
    }
    return null;
}

返回队头元素

public E peek(){
    if (!isEmpty()) {
        return (E) queue[0];
    }
    return null;
}

队列是否已满

public boolean isFull(){
    return size == maxSize;
}

队列是否为空

public boolean isEmpty(){
    return size == 0;
}

队列的大小

public int size(){
    return size;
}

toString方法

@Override
public String toString() {
    return Arrays.toString(queue);
}

Java队列(基于链表的实现)

Java队列核心数据结构

含头结点(头结点不存储值,添加操作O(1)),尾指针(删除操作O(1))

public class LinkedQueue<E> {

    private Node<E> head;  // 头结点
    private Node<E> rear;   // 尾指针
    private int size;   // 队列大小

    public LinkedQueue(){
        head = rear = new Node<E>(null);
    }
}

添加元素到队尾

public void put(E data){
    Node<E> node = new Node<E>(data);
    rear.next = node;
    rear = node;
    size ++;
}

删除队头并返回队头元素的值

public E pop(){
    if(!isEmpty()){
        E e = null;
        Node<E> temp = head.next;
        head.next = temp.next;
        e = temp.data;

        temp.data = null;
        temp.next = null;
        size--;
        return e;        
    }
    return null;
}

返回队头元素的值

public E peek() {
    if (!isEmpty()) {
        return head.next.data;
    }
    return null;
}

队列是否为空

public boolean isEmpty(){
    return size == 0;
}

队列大小

public int size() {
    return size;
}

toString方法

@Override
public String toString() {
    // TODO Auto-generated method stub
    Node<E> cur = head.next;
    StringBuilder sb = new StringBuilder();
    while(cur != null){
        sb.append(cur.data).append(" ");
        cur = cur.next;
    }
    return sb.toString();
}

Java队列(基于栈的实现)

Java队列核心数据结构

使用两个栈模拟一个队列,其中一个栈作存储空间,另一个栈作临时缓冲区。

public class StackQueue<E> {

    private LinkedStack<E> stack1;    // 存储空间
    private LinkedStack<E> stack2;  //临时缓冲区

    public StackQueue() {
        stack1 = new LinkedStack<E>();
        stack2 = new LinkedStack<E>();
    }
}

put 添加元素到队尾

先检查stack2是否为空。

若为空,则直接对stack1执行压栈操作。

否则,先将stack2中的元素倒回stack1,再对stack1执行压栈操作。

public void put(E e) {
    if (!stack2.isEmpty()) {
        while (stack2.size() > 0) {
            stack1.push(stack2.pop().getData());
        }
    }
    stack1.push(e);
}

pop 删除队头并返回队头元素的值

先检查stack2是否为空。

若为空,先将stack1中的size-1个元素倒回stack2,再对stack1中栈底元素执行弹栈操作。

否则,则直接对stack2执行弹栈操作。

public E pop() {
    if (stack2.isEmpty()) {
        if (!stack1.isEmpty()) {
            while (stack1.size() > 1) {
                stack2.push(stack1.pop().getData());
            }
            return stack1.pop().getData();
        }
        return null;
    } else {
        return stack2.pop().getData();
    }
}

toString方法

@Override
public String toString() {
    if (!stack1.isEmpty()) {
        return new StringBuilder(stack1.toString()).reverse().toString();
    }
    return stack2.toString();
}

Java队列测试代码

public class LinkedQueueTest {
    public static void main(String[] args) {
        LinkedQueue<Integer> queue = new LinkedQueue<Integer>();
        queue.put(1);
        queue.put(2);
        queue.put(4);
        queue.put(3);
        queue.put(0);
        System.out.println(queue);
        System.out.println("\n ------------------- \n");


        queue.pop();
        System.out.println(queue);
        System.out.println("\n ------------------- \n");


        System.out.println(queue.peek());
        queue.put(121);
        System.out.println(queue);

    }
}
public class StackQueueTest {
    public static void main(String[] args) {
        StackQueue<Integer> queue = new StackQueue<Integer>();
        queue.put(1);
        queue.put(3);
        queue.put(5);
        queue.put(2);
        queue.put(8);
        queue.put(6);
        System.out.println(queue);
        System.out.println("\n------------------\n");

        queue.pop();
        System.out.println(queue);
        System.out.println("\n------------------\n");

        queue.put(4);
        System.out.println(queue);
        System.out.println("\n------------------\n");
    }
}
public class SeqQueueTest {

    public static void main(String[] args) {

        SeqQueue<Integer> queue = new SeqQueue<Integer>(5);
        queue.put(1);
        queue.put(2);
        queue.put(3);
        queue.put(4);
        queue.put(3);
        queue.put(4);
        System.out.println(queue);
        System.out.println("\n----------------\n");

        queue.pop();
        System.out.println(queue);
        System.out.println("\n----------------\n");

        System.out.println(queue.peek());
        System.out.println(queue);
    }
}