如何用栈实现队列功能以及如何用队列实现栈功能
程序员文章站
2022-07-11 08:27:25
...
如何用栈实现队列功能以及如何用队列实现栈功能
首先,我们要明确什么是栈和队列。
栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。栈的特性:后进先出。
队列是一种先进先出的线性表。它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。
栈实现队列
栈实现队列的基本思路:构造两个栈,其中一个用来存放存进来的数据,另外一个用来倒置其中的数据实现输出。
public static class twoStacksQueue {
private Stack<Integer> stackPop;
private Stack<Integer> stackPush;
public twoStacksQueue() {
stackPop = new Stack<>();
stackPush = new Stack<>();
}
public void add(int pushInt) {
stackPush.push(pushInt);
}
public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
} else if (stackPop.empty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
public int peek() {
if (stackPop.isEmpty() && stackPush.isEmpty()) {
throw new RuntimeException("Queue is empty!");
} else if (stackPop.empty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
队列实现栈
队列实现栈的基本思路:构造两个队列,其中一个用来存放输入的数据,在输出时将除最后一个数据外的其他数据全部移动到另外一个队列中去,再把这个队列用于存放输入。
public static class twoQueueStack {
private Queue<Integer> queue;
private Queue<Integer> help;
public void swap() {
Queue<Integer> temp = new LinkedList<>();
temp = queue;
queue = help;
help = temp;
}
public twoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(int pushInt) {
queue.add(pushInt);
}
public int peek() {
if (queue.isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
while (queue.size() != 1) {
help.add(queue.poll());
}
int res = queue.poll();
help.add(res);
swap();
return res;
}
public int pop() {
if (queue.isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
while (queue.size() != 1) {
help.add(queue.poll());
}
int res = queue.poll();
swap();
return res;
}
}
测试代码
public static void main(String[] args) {
twoStacksQueue myQueue = new twoStacksQueue();
myQueue.add(1);
myQueue.add(2);
myQueue.add(3);
myQueue.add(4);
while (myQueue.peek() != 4) {
System.out.println(myQueue.poll());
}
System.out.println(myQueue.peek());
twoQueueStack myStack = new twoQueueStack();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
while (myStack.peek() != 1) {
System.out.println(myStack.pop());
}
System.out.println(myStack.peek());
}