方案

  1. 声明两个队列
  2. 入栈：向非空队列中put元素，如都为空，则随便选。
  3. 出栈：将非空中的lenth-1个元素put到另外一个队列中，出队最后一个元素。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package queue2stack;
import Queue.Queue;
/**
 * 队列实现栈，可扩容
 * 
 * @author jack
 * 2016年11月19日 上午2:52:04
 */
public class Stack {
	private Queue q1;
	private Queue q2;
	private int cap = 10;
	public Stack(int cap) {
		super();
		this.cap = cap;
		this.q1 = new Queue(cap + 1);
		this.q2 = new Queue(cap + 1);
	}
	// 入栈
	public boolean push(Object o) throws Exception {
		Queue q;
		if (q1.isEmpty()) {
			q = q1;
		}
		q = q2;
		if (q.isFull()) {
			expand();
		}
		q = q2;
		return q.put(o);
	}
	// 出栈
	public Object pop() throws Exception {
		Queue from;
		Queue to;
		if (!q1.isEmpty()) {
			from = q1;
			to = q2;
		} else {
			from = q2;
			to = q1;
		}
		queueTransExceptOne(from, to);
		return from.poll();
	}
	// 扩容
	private void expand() throws Exception {
		this.cap = this.cap * 2 + 1;
		Queue q3 = new Queue(this.cap);
		Queue q4 = new Queue(this.cap);
		queueTrans(q1, q3);
		queueTrans(q2, q4);
		q1 = q3;
		q2 = q4;
	}
	private void queueTransExceptOne(Queue queue1, Queue queue2) throws Exception {
		while (queue1.getSize() > 1) {
			queue2.put(queue1.poll());
		}
	}
	private void queueTrans(Queue queue1, Queue queue2) throws Exception {
		while (!queue1.isEmpty()) {
			queue2.put(queue1.poll());
		}
	}
}

测试

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
package queue2stack;
import queue2stack.Stack;
/**
 *
 * @author jack
 * 2016年11月19日 上午3:03:57
 */
public class Test {
	public static void main(String[] args) {
		Stack stack = new Stack(5);
		for (int i = 0; i < 15; i++) {
			try {
				stack.push(i + "");
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		for (int i = 0; i < 15; i++) {
			try {
				System.out.println(stack.pop());
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		try {
			System.out.println(stack.pop());
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
//		System.out.println(stack.s);
	}
}