Skip to content

Instantly share code, notes, and snippets.

@diaolizhi diaolizhi/LinkQueue.java
Last active Sep 29, 2018

Embed
What would you like to do?
链表实现的队列
import java.util.Iterator;
import java.util.Scanner;
public class LinkQueue<Item> implements Iterable<Item>{
// 分别指向队头、队尾
private Node first;
private Node last;
// 队列中元素个数
private int N;
private class Node {
private Item item;
private Node next;
}
/*
* 入队操作
* 入队有一种特殊情况:本来没有元素,入队之后不仅要修改 first 还要修改 last。
* 题外话:可能出现的情况有很多,但是在理想的状态下(程序没有 bug 的情况下),有方法确认出现的情况。
*/
public void enqueue(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
// 如果队列为空,first 和 last 同时指向刚创建的对象。
if(isEmpty()) {
first = last;
} else {
// 否则新创建的对象接在队列的尾部
oldLast.next = last;
}
N++;
}
/*
* 出队操作
* 出队在队首操作,但是还要考虑出队之后,队列是否为空,如果为空,last 还要置为 null。
*/
public Item dequeue() {
if(isEmpty()) return null;
Item item = first.item;
first = first.next;
if(isEmpty()) last = null;
N--;
return item;
}
// 判断队列是否为空
public boolean isEmpty() {
return first == null;
}
// 获取队列的 大小
public int size() {
return N;
}
@Override
public Iterator<Item> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator<Item>{
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
// 测试
public static void main(String[] args) {
LinkQueue<String> queue = new LinkQueue<String>();
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
String string = in.nextLine();
if(string.equals("exit")) break;
if(string.equals("-")) {
System.out.println("出队:" + queue.dequeue());
} else {
queue.enqueue(string);
}
}
for (String string : queue) {
System.out.print(string + " ");
}
System.out.println();
in.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.