基础数据结构02：队列

2017-06-30

介绍

队列是一种先进先出的数据结构。类似于一截水从一端流向另一端的水管，先进入水管的水最先从另一端出来。

API

Java实现

下面使用链表来实现先进先出的数据结构。

package com.algs.base;

import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkQueue<Item> implements Iterable<Item> {

	private Node first;		// 指向最早添加的节点的链接
	private Node last;		// 指向最近添加的节点的链接
	private int N;			// 队列中的元素总数量

	// 队列中的一个元素
	private class Node{
		Item item;
		Node next;
	}

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

	public int size(){return N;}

	// 向队列中添加一个元素
	public void enqueue(Item item){
		// 向链表的尾部添加一个元素
		Node oldLast = last;
		last = new Node();
		last.item = item;
		last.next = null;
		//只有一个节点时，首节点和尾节点相等
		if(isEmpty()) 	first = last;
		else			oldLast.next = last;
		N++;
	}

	//从队列中删除一个元素(先进先出)
	public Item dequeue(){
		if(first==null){
			System.out.println("队列中没有元素");
			return null;
		}
		// 从表头删除元素
		Item item = first.item;
		first = first.next;
		if(isEmpty())	last = null;
		N--;
		return item;
	}
	@Override
	public Iterator<Item> iterator()  {
        return new ListIterator();  
    }
	//链表遍历实现
    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args) {
    	LinkQueue<String> queue = new LinkQueue<String>();
    	queue.enqueue("One");
    	queue.enqueue("two");
    	queue.enqueue("three");
		for(String node:queue){
			//打印结果为：One->two->three->
			System.out.print(node+"->");
		}
		//删除一个元素
		System.out.println("");
		//打印结果为：node:One
		System.out.println("node:"+queue.dequeue());
		for(String node1:queue){
			//打印结果为：two->three->
			System.out.print(node1+"->");
		}
	}
}

说明

对于队列的实现，除了可以使用链表，还可以使用数组来实现。但是在Java中的数组，初始化时必须指定数组的大小，所以当使用数组来实现队列时，需要动态调整队列的大小。
当数组空间不够时，需要扩展空间。当队列中的元素只有空间的四分之一时，此时可以把数组的长度减半。

代码如下：

// 以数组来实现队列或栈时需动态调整数组的大小
private void resize(int max){
	//将队列中的元素移动到新数组中
	Item[] temp = (Item[])new Object[max];
	for(int i=0;i<N;i++){
		temp[i] = queue[i]; //queue为存放队列元素的数组
	}
	queue = temp;
}

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：基础数据结构01：链表
下一篇：基础数据结构03：栈