Use linked list&array to create stack&queue

Posted on | Edited on | In

使用链表和数组来实现栈和队列是一个很基本的问题。在Algorithm的课上老师提到了这一点，因此我花了一点时间重新实现了一遍。老师在课上没有提到用ResizingArray来实现队列的方法，“Not difficult, but
a definitely tricky programming exercise that people are welcome to try”，因此我也尝试了一下。

Linked List — stack

老师提到早起的java并没有使用泛型，因此如果想使用一个String的栈和Integer的栈，那就得写两次代码，显然很不方便了。在这里我使用了泛型，同时实现了Iterable接口以便client side能遍历.

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
42
class CustomStack<Item> implements Iterable<Item>{
	private StackNode first;
	private class StackNode{
		private Item item;
		private StackNode next;
	}
	public CustomStack() {
		first = null;
	}
	public void push(Item item) {
		StackNode n = new StackNode();
		n.item = item;
		n.next = first;
		first = n;
	}
	public Item pop() {
		Item res = first.item;
		first = first.next;
		return res;
	}
	
	public boolean isEmpty() {
		return first==null;
	}
	@Override
	public Iterator<Item> iterator() {
		return new StackIterator();
	}
	private class StackIterator implements Iterator<Item> {
		private StackNode cur = first;
		@Override
		public boolean hasNext() {
			return cur != null;
		}
		@Override
		public Item next() {
			Item item = cur.item;
			cur = cur.next;
			return item;
		}
	}
}

测试代码：

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
		// TODO Auto-generated method stub
		CustomStack<Integer> test = new CustomStack<>();
		test.push(2);
		test.push(4);
		test.push(6);
		test.push(9);
		for(int a : test) {
			System.out.println(a);
		}
	}

遍历后的结果：

1
2
3
4
9
6
4
2

ResizingArray

Java不允许使用泛型数组，如果要在此使用泛型，那就得涉及到强制转换，而老师又提到这是ugly的事情，因此我就以String为例写了一下。

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
class ResizingArrayStackOfStrings{
	private String[] array;
	private int p;
	public ResizingArrayStackOfStrings() {
		array = new String[1];
		p=0;
	}
	public void push(String item) {
	//当前数组满了，就将数组大小扩大一倍
		if(p==array.length -1)	resize(array.length * 2);
		array[p++] = item;
	}
	public String pop() {
		String res = array[--p];
		array[p] = null;
		/*
		当栈中元素是栈大小的1/4，则将栈的大小减小一半。
		这里是1/4而不是1/2的原因是防止thrashing，也就是在1/2处用          户频繁进行push和pop操作
		*/
		if(p > 0 && p==array.length/4)	resize(array.length/2);
		return res;
	}
	public boolean isEmpty() {
		return p==0;
	}
	private void resize(int capacity) {
		String[] newArray = new String[capacity];
		for(int i=0;i<array.length;i++)	newArray[i] = array[i];
		array = newArray;
	}
}

LinkedList — queue

这里需要两个指针，指向一头一尾。

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
42
43
44
45
46
class CustomQueue<Item> implements Iterable<Item>{
	private StackNode begin;
	private StackNode end;
	private class StackNode{
		private Item item;
		private StackNode next;
	}
	public CustomQueue() {
		begin = null;
		end = null;
	}
	public void enqueue(Item item) {
		StackNode n = new StackNode();
		n.item = item;
		if(begin==null)	begin = n;  //对于空队列处理
		else	end.next = n;
		end = n;
	}
	public Item dequeue() {
		Item item = begin.item;
		begin = begin.next;
		if(begin == null)	end = null; //对于空队列处理
		return item;
	}
	public boolean isEmpty() {
		return begin==null;
	}
	@Override
	public Iterator<Item> iterator() {
		return new StackIterator();
	}
	
	private class StackIterator implements Iterator<Item> {
		private StackNode cur = begin;
		@Override
		public boolean hasNext() {
			return cur != null;
		}
		@Override
		public Item next() {
			Item item = cur.item;
			cur = cur.next;
			return item;
		}
	}
}

ResizingArray — queue

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
class ResizingArrayQueueOfStrings{
	public String[] array;
	private int begin;	//指向队列头
	private int end;	//指向队列尾
	private int N;		//记录有几个元素
	public ResizingArrayQueueOfStrings() {
		array = new String[1];
		begin = 0;
		end = 0;
		N = 0;
	}
	public void enqueue(String item) {
		if(N==array.length) resize(N*2);	//如果当前队列满，则扩一倍容
		array[end++] = item;
		if(end == array.length)	end=0;	//如果end指针到达数组尾，则将其指向数组头
		N++;	//元素个数加1
	}
	public String dequeue() {
		N--;	//元素个数减1
		String item = array[begin];
		array[begin++] = null;	//将队列尾设为空，避免对象游离
		if(begin ==array.length)	begin = 0;	//如果begin到了数组尾部，则将其指向数组头
		if(N == array.length /4)	resize(array.length/2);		//当元素个数只有数组的1/4时，减1/2容
		return item;
	}
	public boolean isEmpty() {
		return N==0;
	}
	private void resize(int capacity) {
		String[] newArray = new String[capacity];
		for(int i=0;i<N;i++) {
			newArray[i] = array[(i+begin)%array.length];
		}
		array = newArray;
		begin = 0;	//重新设置begin和end
		end = N;
	}
}