当前位置：首页 > news >正文

【百日算法计划】：每日一题，见证成长（017）

news 2024/9/20 20:24:39

题目

用栈来实现队列

思路1

入队直接入，出队用两个栈来回倒腾。

static class StackToQueue{Stack<Integer> stack = new Stack<>();Stack<Integer> tmpStack = new Stack<>(); //临时栈public StackToQueue(){}//入队 直接入public void enqueue(Integer val){stack.push(val);}//出队public Integer dequeue(){if (stack.isEmpty()) return null;while (!stack.isEmpty()){tmpStack.push(stack.pop());}Integer pop = tmpStack.pop();while (!tmpStack.isEmpty()){stack.push(tmpStack.pop());}return pop;}
}

思路2

入队来回倒腾，出队直接出。

static class StackToQueue2{Stack<Integer> stack = new Stack<>();Stack<Integer> tmpStack = new Stack<>(); //临时栈public StackToQueue2(){}//入队 两个栈倒腾public void enqueue(Integer val){//新元素进来时，把stack里面的元素倒腾到tmp里去while (!stack.isEmpty()){tmpStack.push(stack.pop());}stack.push(val);while (!tmpStack.isEmpty()){stack.push(tmpStack.pop());}}//出队public Integer dequeue(){if (stack.isEmpty()) return null;return stack.pop();}
}

思路3

倒腾到tmpStack后，不用再倒腾回去了；当tmpStack不为空的时候，直接从tmpStack出队。

static class StackToQueue3{Stack<Integer> stack = new Stack<>();Stack<Integer> tmpStack = new Stack<>(); //临时栈public StackToQueue3(){}//入队 直接入public void enqueue(Integer val){stack.push(val);}//出队 优化一下public Integer dequeue(){if (stack.isEmpty() && tmpStack.isEmpty()) return -1;int r;if (!tmpStack.isEmpty()){r = tmpStack.pop();} else {while (!stack.isEmpty()){tmpStack.push(stack.pop());}r = tmpStack.pop();}return r;}
}