Introduction

  • 实例变量：指向队头的first, 指向队尾的last, 节点个数N
  • 方法：添加到对尾enqueue()，删除对头dequeue()

Detail

Node

1
2
3
4
5
private class Node
{
    Item item;
    Node next;
}

enqueue()

  • 如果链表为空，则要给first变量赋值（指向last）
1
2
3
4
5
6
7
8
9
10
11
12
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++;
}

dequeue()

1
2
3
4
5
6
7
8
9
public Item dequeue()
{
    Item item = first.item;
    first = first.next;
    if(isEmpty())
        last = null;
    N--;
    return item;
}

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Queue<Item> {
	private Node first; //
	private Node last;
	private int N;
	private class Node
	{
		Item item;
		Node next;
	}
	
	public boolean isEmpty()
	{
		return first == null;
	}
	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()
	{
		Item item = first.item;
		first = first.next;
		if(isEmpty())
			last = null;
		N--;
		return item;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Queue<String> q = new Queue<String>();
		
		while (!StdIn.isEmpty())
		{
			String item = StdIn.readString();
			if(!item.equals("-"))
				q.enqueue(item);
			else if(!q.isEmpty())
				StdOut.print(q.dequeue() + " ");
		}
		StdOut.println("(" + q.size() + " left on queue)");
	}

}