数据结构队列以及Java代码实现

浅浅的花香味﹌ 2022-06-12 04:07 216阅读 0赞

## 1. 队列 ##

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

*  队尾(rear)——允许插入的一端
 *  队头(front)——允许删除的一端

队列特点：先进先出(FIFO)

结构模型：

![这里写图片描述][1358293814_6852.png]

## 2.顺序循环队列 ##

![这里写图片描述][1358294352_6461.png]

/** * Queue * 队列的基本操作 * （1）清空队列 * （2）判断是否为空 * （3）元素的个数 * （4）入队列 * （5）出队列 * （6）取对头元素 * Created by heqianqian on 2017/7/14. */
    public interface Queue<T> {
    
        /** * 判断是否为空 */
        boolean isEmpty();
    
        /** * 入队列 */
        void enQueue(T obj);
    
        /** * 出队列 */
        T deQueue();
    
    
        /** * 取队头元素 */
        T peek();
    
        /** * 元素的个数 */
        int size();
    
    
        /** * 清空队列 */
        void clear();
    }

/** * ArrayQueue * 顺序循环队列 * Created by heqianqian on 2017/7/14. */
    public class ArrayQueue<T> implements Queue<T> {
    
        private static final int DEFAULT_SIZE = 10;
    
        private T[] queue;
    
        private int front, rear;
    
        private int size;
    
        @SuppressWarnings("unchecked")
        public ArrayQueue() {
            front = rear = size = 0;
            queue = (T[]) new Object[DEFAULT_SIZE];
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public void enQueue(T obj) {
            if ((rear == front) && (size > 0)) {
       //队列已满
                expand();
            }
            //队尾插入元素
            queue[rear] = obj;
            rear = (rear + 1) % DEFAULT_SIZE;
            size++;
        }
    
        /** * 扩容 */
        @SuppressWarnings("unchecked")
        private void expand() {
            T[] arr = (T[]) new Object[DEFAULT_SIZE * 2];
            System.arraycopy(queue, 0, arr, 0, size);
        }
    
        @Override
        public T deQueue() {
            if ((rear == front) && (size == 0)) {
       //队列为空
                return null;
            }
            //队头取元素
            T result = queue[front];
            front = (front + 1) % DEFAULT_SIZE;
            size--;
            return result;
        }
    
        @Override
        public T peek() {
            return queue[front];
        }
    
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public void clear() {
            front = rear = size = 0;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int i = 0; i < size - 1; i++) {
                sb.append(queue[i]).append(",");
            }
            sb.append(queue[size - 1]).append("]");
            return sb.toString();
        }
    }

## 3.链式队列 ##

![这里写图片描述][1358295103_8019.png]

![这里写图片描述][1358295162_6914.png]

/** * Node * 链式队列的节点 * Created by heqianqian on 2017/7/14. */
    public class Node<T> {
    
        public Node next;
        public T data;
    
        public Node(T data) {
            this.data = data;
            next = null;
        }
    
        @Override
        public String toString() {
            return data.toString();
        }
    }

/** * LinkedQueue * 链式循环队列 * Created by heqianqian on 2017/7/14. */
    public class LinkedQueue<T> implements Queue<T> {
    
        private Node<T> front, rear;
    
        private int size;
    
        @SuppressWarnings("unchecked")
        public LinkedQueue() {
            front = rear = new Node(null);
            size = 0;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public void enQueue(T obj) {
            Node<T> node = new Node<T>(obj);
            //队尾插入
            rear.next = node;
            rear = node;
            size++;
        }
    
        @Override
        @SuppressWarnings("unchecked")
        public T deQueue() {
            //队头出队
            if (size <= 0) {
                return null;
            }
            T data = (T) front.next.data;
            front = front.next;
            size--;
            return data;
        }
    
        @Override
        public T peek() {
            return (T) front.next.data;
        }
    
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public void clear() {
            size = 0;
            front = rear;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node<T> temp = front.next;
            while (temp != rear) {
                sb.append(temp.data.toString()).append(",");
                temp = temp.next;
            }
            sb.append(temp.data).append("]");
            return sb.toString();
        }
    }

[1358293814_6852.png]: https://img-my.csdn.net/uploads/201301/16/1358293814_6852.png
[1358294352_6461.png]: https://img-my.csdn.net/uploads/201301/16/1358294352_6461.png
[1358295103_8019.png]: https://img-my.csdn.net/uploads/201301/16/1358295103_8019.png
[1358295162_6914.png]: https://img-my.csdn.net/uploads/201301/16/1358295162_6914.png