使用两个队列实现栈

具体的实现方法可以参考下图,

  • 压栈时,将元素e插入q1,将q2中的元素顺次删除,插入q1中,再将q1中的元素顺次删除,插入q2中,从而使新插入的元素e位于q2的队首位置;

  • 出栈时,首先检查q2是否为空,不为空,删除队首元素。

队列的具体类java.util.PriorityQueue这里不能很好地实现队列的功能,链表类java.util.LinkedList也实现了队列接口java.util.Queue,这里在Queue2Stack的无参构造方法中,使用链表类初始化队列。

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
public class Queue2Stack<E> {
private Queue<E> q1;
private Queue<E> q2;
public Queue2Stack() {
q1 = new java.util.LinkedList<E>();
q2 = new java.util.LinkedList<E>();
}
public void push(E e) {
q1.add(e);
while(!q2.isEmpty())
q1.add(q2.remove());
while(!q1.isEmpty())
q2.add(q1.remove());
}
public E pop() {
if(q2.isEmpty())
return null;
E e = q2.remove();
return e;
}
}
使用两个栈实现队列

具体的实现方法可以参考下图,

  • 插入时,将s1中的元素顺次出栈,压入s2,插入元素e后,再将s2中的元素顺次出栈,压入s1,从而使新插入的元素位于s1的栈顶位置;

  • 删除时,首先检查s1是否为空,不为空,将栈顶元素出栈。

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
public class Stack2Queue<E> {
private java.util.Stack<E> s1;
private java.util.Stack<E> s2;
public Stack2Queue() {
s1 = new java.util.Stack<E>();
s2 = new java.util.Stack<E>();
}
public void add(E e) {
while(!s1.isEmpty())
s2.push(s1.pop());
s1.push(e);
while(!s2.isEmpty())
s1.push(s2.pop());
}
public E remove() {
if(s1.isEmpty())
return null;
return s1.pop();
}
}