数据结构 (一) 数组实现一个简单的 ArrayList
数据结构 (二) 链表实现 LinkedList
数据结构 (三) 用两种方式简单实现栈
数据结构 (四) 栈和队列的简单应用
数据结构(六)BST 二分搜索树(上)
数据结构(六)BST 二分搜索树(下)
数据结构 (七) 两种方式实现 set
概念
队列(queue): 只允许在一端进行插入操作, 而在另一端进行删除操作的线性表.
队列是一种先进先出 (First In First Out) 的线性表, 简称 FIFO.
允许插入的一端称为队尾, 允许删除的一端称为队头
实现队列的简单的几个方法:
- public interface Queue<E> {
- int getSize();
- boolean isEmpty();
- // 插入队列
- void enqueue(E e);
- // 删除队列队首元素
- E dequeue();
- // 获取队首元素
- E getFront();
- }
实现队列
1.array 实现队列源码如下:
- public class ArrayQueue<E> implements Queue<E>{
- private Array<E> array;
- public ArrayQueue(int capacity){
- array = new Array<>(capacity);
- }
- public ArrayQueue(){
- array = new Array<>();
- }
- @Override
- public int getSize() {
- return array.getSize();
- }
- @Override
- public boolean isEmpty() {
- return array.isEmpty();
- }
- public int getCapacity(){
- return array.getCapacity();
- }
- @Override
- public void enqueue(E e) {
- array.addLast(e);
- }
- @Override
- public E dequeue() {
- return array.removeFirst();
- }
- @Override
- public E getFront() {
- return array.getFirst();
- }
- @Override
- public String toString(){
- StringBuilder res = new StringBuilder();
- res.append("queue");
- res.append("front [");
- for (int i = 0; i<array.getSize() ; i ++){
- res.append(array.get(i));
- if (i != array.getSize() - 1){
- res.append(",");
- }
- }
- res.append("] tail");
- return res.toString();
- }
- public static void main(String[] args) {
- ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
- for (int i = 0; i <10; i++) {
- arrayQueue.enqueue(i);
- System.out.println(arrayQueue);
- if (i % 3 == 2){
- arrayQueue.dequeue();
- System.out.println(arrayQueue);
- }
- }
- }
- }
这几个方法很简单没有什么需要解释的, array 里直接实现了. 下边我们来看看链表实现队列
2. 链表实现队列
- public class LinkedListQueue<E> implements Queue<E> {
- private class Node {
- private E e;
- private Node next;
- public Node(E e, Node next) {
- this.e = e;
- this.next = next;
- }
- public Node(E e) {
- this(e, null);
- }
- public Node() {
- this(null, null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- private Node head, tail;
- private int size = 0;
- public LinkedListQueue() {
- head = null;
- tail = null;
- size = 0;
- }
- @Override
- public int getSize() {
- return size;
- }
- @Override
- public boolean isEmpty() {
- return size == 0;
- }
- @Override
- public void enqueue(E e) {
- if (tail == null) {
- tail = new Node(e);
- head = tail;
- } else {
- tail.next = new Node(e);
- tail = tail.next;
- }
- size++;
- }
- @Override
- public E dequeue() {
- if (isEmpty()) {
- throw new IllegalArgumentException("can not dequeue from a empty queue");
- }
- Node retNode = head;
- head = head.next;
- retNode.next = null;
- if (head == null) {
- tail = null;
- }
- size--;
- return retNode.e;
- }
- @Override
- public E getFront() {
- if (isEmpty()) {
- throw new IllegalArgumentException("can not dequeue from a empty queue");
- }
- return head.e;
- }
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- res.append("queue :front");
- Node cur = head;
- while (cur.next != null) {
- res.append(cur.e);
- cur = cur.next;
- }
- res.append("NULL tail");
- return res.toString();
- }
这里定义了一个头节点, 一个尾节点,
enqueue 插入元素的时候先判断当前链表是否为空, 如果为空, 这个元素的节点赋值给头尾节点; 如果链表不为空, 创建一个节点插入到尾结点, 把尾结点赋值成刚才创建的节点.
dequeue 首先判断一下这个链表是否为空, 如果是空的则抛一个异常, 如果不为空就然后创建一个临时节点把头节点赋值给他, 头结点指向下一个节点, 临时节点赋值为 null; 如果删除之前链表里只有一个节点, 那么删除之后链表就为空了, 头尾节点都为 null, 所以后边加了一个判断.
getFront 获取头结点的元素这个方法很简单, 只需要判断一下当前链表是否为空.
toString 方法也很简单, 只是要在头和尾节点拼接一写我们可以看清楚的提示性文字, 剩下的就是遍历一下链表.
来源: http://www.jianshu.com/p/3f9e8c14f2bd