Java实现--链表队列

用链表实现队列的操作，其实质就是把双端队列包装一下，包装成队列而已，其实质用到的是双端队列的两个方法，第一个方法是insertLast(int data)，这是队列的插入操作，另外一个remove()操作，用到的是deleteFirst()方法，将这两个方法包装一下就成了队列。

以下为完整地代码：

/**
 * 定义一个结点类
 * @author Administrator
 *
 */
public class Link {
	public int data;	//数据域
	public Link next;	//指向下一个结点
	
	public Link(int data) {
		super();
		this.data = data;
	}
	
	//打印结点的数据域
	public void diaplayLink() {
		System.out.print("{"+ data + "} ");
	}
}

/**
 * 建立双端链表 
 * @author Administrator
 *
 */
public class FirstLastLink {
	private Link first;
	private Link last;
	
	public FirstLastLink() {
		first = null;
		last = null;
	}
	
	public boolean isEmpty() {
		return (first==null);
	}
	
	//头部插入,last永远指向的是第一个插入的结点,头部插入的特点就是会逆置
	public void inserstFirst(int data) {
		Link newNode = new Link(data);
		if(isEmpty()) {					//如果链表是空的即first==null，则代表我们将要插入第一个结点
			last = newNode;				//last永远指向的是第一个我们插入的结点
		}
		newNode.next = first;			//跟我们初始单链表的时候一样，在头部插入，先将新的结点的next域指向老的结点，以插入第二个结点为例：
		first = newNode; 				//1、first--->（指向）第一个结点
	}									//2、将新的结点newNode.next---> first(即新的结点next指向第一个结点)
										//first = newNode  first指向第二个结点即最新插入的结点 	
	
	//尾部插入,last永远指向最新插入的结点
	public void insertLast(int data) {
		Link newNode = new Link(data);
		if(isEmpty()) {					//如果链表是空的，则将last指向第一个数据结点
			newNode.next = null;		//newNode.next = null;这条语句其实不是必须的，只是为了方便大家理解
			first = newNode;			//将first指向第一个结点
		}else {
			last.next = newNode;		//last此时指向的是上次插入的结点，比如说现在我们插入的是第二个结点，那么此时，last指向的是第一个数据结点
			newNode.next = null;		//同上面一样newNode.next = null;这条语句其实不是必须的，只是为了方便大家理解
		}
		last = newNode;					//上述已经完成了将新的数据结点插入链表，最后则是将last指向最新的结点
	}
	
	public Link deleteFirst() {				//从头部删除结点返回结点
		Link temp = first;
		if(first.next==null)			//如果只有一个结点，则删除后链表为空，则返回null 
			return null;
		first = first.next;				//若不是，则将first指向第二个结点
		return temp;
	}
	
	//删除最后一个结点,该操作比较繁琐，不太推荐使用，效率低下
	public Link deleteLast() {
		Link current = first;			//定义当前结点	
		Link temp = first;				//定义一个标志结点，后面会用到
		if(isEmpty()) {					//如果链表是空的，则返回null
			return null;
		}else if(current.next==null) {	//否则如果链表的下一个是空的话，也就是说链表只有一个结点，此时我们要删除它
			first = null;				//则first指向null，意味着第一个数据结点被删除，此时链表为空
			return current;
		}else {
			while(current.next.next!=null) {	//循环，如果当前结点的next的next为空的话，意味着当前结点的下一个结点时最后一个结点，我们要删除它
				current = current.next;			//如果current.next.next==null，退出循环，说明我们找到了倒数第二个结点
			}									//将最后一个结点赋给temp，然后将current.next即倒数第二个结点赋null，称为最后一个结电，在最后将temp返回
			temp = current.next;
			current.next = null;
			return temp;
		}
	}
	
	
	//删除指定数据的结点
	public Link delete(int key) {
		Link current = first;			//获取当前结点
		Link previous = first;			//获取当前结点，方便删除结点
		while(current.data!=key) {		//只要当前数据不等于key，则一直遍历下去
			if(current.next == null) {	//如果current.next==null表示当前结点是最后一个结点或者链表为空，意味着找不到key，返回null
				return null;
			}else {
				previous = current;		//否则将当前结点赋给previous表示上一个结点
				current = current.next  ;	//然后将当前结点的下一个结点赋给当前结点，即current = current.next
			}
		}
		if(current==first) {		//如果current==first，表示第一个结点的data与key是相等的，为了删除该结点，first指向first.next（即第二个结点）
			first = first.next;		//和delete操作相同
		}else {
			previous.next = current.next;	//否则将current即当前结点的上一个结点previous.next和下一个结点current.next相连
		}
		return current;		//返回删除的结点
	}
	
	public void displayList() {
		//System.out.print("List(first--->last): ");
		Link current = first;
		while(current!=null) {
			current.diaplayLink();
			current = current.next;
		}
		System.out.println();
	}
	
}

/**
 * 定义一个链表队列
 * @author Administrator
 *
 */
public class LinkQueue {
	
	private FirstLastLink theList;
	
	public LinkQueue() {
		theList = new FirstLastLink();
	}
	
	public boolean isEmpty() {
		return theList.isEmpty();
	}
	
	public void Insert(int data) {
		theList.insertLast(data);
	}
	
	public int remove() {
		return theList.deleteFirst().data;
	}
	
	public void displayQueue() {
		System.out.print("Queue(front--->rear): ");
		theList.displayList();
	}
}

 

/**
 * 测试链表队列
 * @author Administrator
 *
 */
public class TestLinkQueue {
	public static void main(String[] args) {
		LinkQueue theQueue = new LinkQueue();
		theQueue.Insert(20);
		theQueue.Insert(40);
		theQueue.displayQueue();
		
		theQueue.Insert(60);
		theQueue.Insert(80);
		theQueue.displayQueue();
		
		theQueue.remove();
		theQueue.remove();
		theQueue.displayQueue();
	}
}

 测试结果：

Queue(front--->rear): {20} {40} 
Queue(front--->rear): {20} {40} {60} {80} 
Queue(front--->rear): {60} {80}