抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

用栈来实现队列

题目: 用两个栈实现一个队列。 请实现它的两个函数appendTail和deleteHead, 分别完成在队列尾部插入结点和在队列头部删除节点的功能

解法: 操作这两个“ 先进后出"的栈实现一个“先进先出” 的队列Queue,具体看图

当stack2中不为空时,在stack2中的栈顶元素是最先进入队列的元素,可以弹出。如果 stack2为空时,我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端,经过弹出和压入之后就处于stack2的顶端了,又可以直接弹出。

代码实现(牛客OJ):

import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

public int pop() {
if (stack2.empty()) {
if (stack1.empty()) {
return 0;
}
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}

以上,该题不具备复杂逻辑,仅需考虑数据结构特性。

扩展题

题目:用两个队列实现一个栈

主要思路:两个队列交替工作,拿三个元素:a,b,c举例,依次压入queue1,queue2为空,此时若想模拟栈的弹出,则只能将queue1的前两项a,b压入queue2,然后弹出queue1中的c即可,对于即将弹出的b来说也是同理,将queue2中的a压入queue1中,弹出queue2的b即可,若此时需压入新元素多个,则将其依次放在非空队列中并按上面的逻辑交替便可解该题。注:两个队列中至少一个为空,为啥捏?看图

代码:两个队列的实现

static Queue<Integer> queue1 = new ArrayDeque<Integer>();
static Queue<Integer> queue2 = new ArrayDeque<Integer>();

public static void push(int node) {
if (queue1.size() > queue2.size()) {
//queue1中有元素
queue1
.add(node);
} else {
//queue2中有元素
queue2
.add(node);
}
}

public static int pop() {
if (isEmpty()) {
return -1;
}
if (queue1.size() > queue2.size()) {
//将queue1中的元素添加至queue2 queue1仅保留一个元素 并返回queue1顶部元素
return swapExceptTop(queue1, queue2);
} else {
return swapExceptTop(queue2, queue1);
}
}

public static int swapExceptTop(Queue<Integer> orig, Queue<Integer> dest) {
if (orig.isEmpty()) {
return -1;
}
while (orig.size() != 1) {
dest.add(orig.poll());
}
return orig.poll();
}

public static boolean isEmpty() {
return queue1.isEmpty() && queue2.isEmpty();
}

精简版:一个队列的实现

static Queue<Integer> queue = new ArrayDeque<Integer>();

public static void push(int node) {
queue.add(node);
}

public static int pop() {
if (queue.isEmpty()) {
return -1;
}
for (int i = 0; i < queue.size()-1; i++) {
queue.add(queue.poll());
}
return queue.poll();
}

测试主函数:

public static void main(String[] args) {
push(1); push(2);
push(3); push(4);
while (!queue.isEmpty()) {
System.out.print(pop() + " ");
}
}

以上。是剑指offer关于栈和队列的面试题。

若对新手不友好,可参看有注释的文章,如:https://cloud.tencent.com/developer/article/1163041


0条评论

发表评论