首页 » Java » 数据结构-队列 JAVA语言实现

数据结构-队列 JAVA语言实现

原文 http://blog.csdn.net/z740852294/article/details/77892867

2017-09-08 13:20:10阅读(526)

队列是一种先进先出(First In First Out,FIFO)的数据结构,如果你将两个元素加入队列,先加入的元素将在后加入的元素之前出队。
更新队列时,使用术语“入队”和“出队”,但也可能遇到术语“压入”和“弹出”。压入大致相当于入队,而弹出大致相当于出队。

基于简单循环数组实队列
public class ArrayQueue {
    private int front;//队尾
    private int rear;  //队首
    private int capacity;  //容量
    private int[] arrayInt;
    public ArrayQueue(int front, int rear, int capacity, int[] arrayInt) {
        this.rear = rear;
        this.front = front;
        this.capacity = capacity;
        this.arrayInt = arrayInt;
    }
    /**
     * 队列是否为空
     *
     * @return true 为空  false  不为空
     */
    public boolean isEmpty() {
        if (front == -1) {
            return true;
        } else {
            return false;
        }
    }
    /**
     * 队列是否队满
     *
     * @return true 满  false  不满
     */
    public boolean isFull() {
        if ((rear + 1) % capacity == front) {
            return true;
        } else {
            return false;
        }
    }
    /**
     * 获取队列长度
     *
     * @return
     */
    public int getQueueSiae() {
        return ((capacity + rear + 1 - front) % capacity);
    }
    /**
     * 入队
     *
     * @param data
     */
    public void enQueue(int data) {
        if (isFull()) {
            return;
        } else {
            rear = (rear + 1) % capacity;
            arrayInt[rear] = data;
            if (front == -1) {
                front = rear;
            }
        }
    }
    /**
     * 出队  出首位
     */
    public int deQueue() {
        int data;
        if (isEmpty()) {
            return 0;
        } else {
            data = arrayInt[front];
            if (front == rear) {
                front = rear - 1;
            } else {
                front = (front + 1) % capacity;
            }
            return data;
        }
    }
    public void printArray() {
        for (int i : arrayInt) {
            System.out.print("   " + i);
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = new int[11];
        array[0] = 5;
        array[1] = 1;
        array[2] = 3;
        array[3] = 9;
        array[4] = 7;
        ArrayQueue arrayQueue = new ArrayQueue(0, 4, array.length, array);
        arrayQueue.printArray();
        //入队
//        arrayQueue.enQueue(8);
//        arrayQueue.printArray();
        //出队
        System.out.println(arrayQueue.deQueue());
    }
}
基于链表实现队列
public class ListNodeQueue {
    private ListNode frontNode;
    private ListNode rearNode;
    public ListNodeQueue() {
        this.frontNode = null;
        this.rearNode = null;
    }
    public boolean isEmpty() {
        return (frontNode == null);
    }
    public void enQueue(int data) {
        ListNode listNode = new ListNode(data);
        if (rearNode != null) {
            rearNode.setNext(listNode);
        }
        rearNode = listNode;
        if (frontNode == null) {
            frontNode = rearNode;
        }
    }
    public int deQueue() {
        int data;
        if (isEmpty()) {
            return 0;
        } else {
            data = frontNode.getData();
            frontNode = frontNode.getNext();
        }
        return data;
    }
    public void printQueue() {
        ListNode currentNode = frontNode;
        while (currentNode != null) {
            System.out.print("  " + currentNode.getData());
            currentNode = currentNode.getNext();
        }
        System.out.println();
    }
    public static void main(String[] args) {
        ListNode frontNode = new ListNode(7);
        ListNode listNode1 = new ListNode(5);
        ListNode listNode2 = new ListNode(6);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(5);
        ListNode rearNode = new ListNode(4);
        frontNode.setNext(listNode1);
        listNode1.setNext(listNode2);
        listNode2.setNext(listNode3);
        listNode3.setNext(listNode4);
        listNode4.setNext(rearNode);
        ListNodeQueue listNodeQueue = new ListNodeQueue();
        listNodeQueue.frontNode = frontNode;
        listNodeQueue.rearNode = rearNode;
        listNodeQueue.printQueue();
        //入队
//        listNodeQueue.enQueue(88);
//        listNodeQueue.printQueue();
         //出队
        System.out.println(listNodeQueue.deQueue());
        listNodeQueue.printQueue();
    }
}
JAVA Queue 类

在java5中新增加了java.util.Queue接口,用以支持队列的常见操作。该接口扩展了java.util.Collection接口。

方法摘要:
1.add(E e) 将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回 true,如果当前没有可用的空间,则抛出 IllegalStateException。
2.element() 获取,但是不移除此队列的头。
3.offer(E e) 将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
4.peek() 获取但不移除此队列的头;如果此队列为空,则返回 null。
5.poll() 获取并移除此队列的头,如果此队列为空,则返回 null。
6.remove() 获取并移除此队列的头。

Queue使用时要尽量避免Collection的add()和remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否,add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素,使用
element()或者peek()方法。

public class QueueDemo {
    public void showEnQueue(Queue<Integer> queue, int data) {
        queue.add(data);
        System.out.println("入队:  " + data);
    }
    public void showDeQueue(Queue<Integer> queue) {
        System.out.println("出队:  " + queue.remove());
    }
    public void printQueue(Queue<Integer> queue) {
        queue.forEach(integer -> {
            System.out.print(integer + "  ");
        });
        System.out.println();
    }
    public static void main(String[] args) {
        QueueDemo queueDemo = new QueueDemo();
        Queue<Integer> queue = new LinkedList<>();
        queueDemo.showEnQueue(queue, 7);
        queueDemo.showEnQueue(queue, 5);
        queueDemo.showEnQueue(queue, 1);
        queueDemo.showEnQueue(queue, 2);
        queueDemo.printQueue(queue);
        queueDemo.showDeQueue(queue);
        queueDemo.printQueue(queue);
        queueDemo.showDeQueue(queue);
        queueDemo.printQueue(queue);
    }
}

运行结果:
数据结构-队列 JAVA<a href=语言实现" src="http://img.blog.csdn.net/20170908113516195?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvejc0MDg1MjI5NA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="这里写图片描述" title="">

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示 »

按 Ctrl+D 键,
把本文加入收藏夹