class MyStack {
Queue<Integer> a = new LinkedList<>(), b = new LinkedList<>();
public MyStack() {}
public void push(int x) {
a.offer(x);
}
public int pop() {
while (a.size() > 1) b.offer(a.poll());
int ans = a.poll();
Queue<Integer> t = b; b = a; a = t;
return ans;
}
public int top() {
while (a.size() > 1) b.offer(a.poll());
int ans = a.poll();
b.offer(ans);
Queue<Integer> t = b; b = a; a = t;
return ans;
}
public boolean empty() {
return a.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
from collections import deque
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue1 = deque()
self.queue2 = deque()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.queue1.append(x)
while self.queue2:
tmp = self.queue2.popleft()
self.queue1.append(tmp)
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.queue2.popleft()
def top(self) -> int:
"""
Get the top element.
"""
if self.queue2:
return self.queue2[0]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not bool(self.queue2)
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
时间O(N) O(1)，空间O(N)
class MyStack {
Queue<Integer> in;
Queue<Integer> out;
public MyStack() {
in = new LinkedList<Integer>(); //空队列 数据输入
out = new LinkedList<Integer>(); //原始的数据存在这里
}
public void push(int x) {
in.offer(x);
while(!out.isEmpty()){
in.offer(out.poll());
}
Queue<Integer> temp = in; //设置中转队列
in = out;
out = temp;
}
public int pop() {
return out.poll();
}
public int top() {
return out.peek();
}
public boolean empty() {
return out.isEmpty();
}
}
class MyStack {
Deque<Integer> deque1;
Deque<Integer> deque2;
public MyStack() {
deque1 = new ArrayDeque<>();
deque2 = new ArrayDeque<>();
}
public void push(int x) {
deque1.add(x);
}
public int pop() {
while(deque1.size()>1){
deque2.add(deque1.poll());
}
int x = deque1.poll();
while(!deque2.isEmpty()){
deque1.add(deque2.poll());
}
return x;
}
//
public int top() {
int x = 0;
while(!deque1.isEmpty()){
x = deque1.poll();
deque2.add(x);
}
while(!deque2.isEmpty()){
deque1.add(deque2.poll());
}
return x;
}
public boolean empty() {
return deque1.isEmpty();
}
}
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue1.add(x);
}
public int pop() {
while (queue1.size() > 1) {
queue2.add(queue1.poll());
}
int res = queue1.poll();
while (!queue2.isEmpty()) {
queue1.add(queue2.poll());
}
return res;
}
public int top() {
while (queue1.size() > 1) {
queue2.add(queue1.poll());
}
int res = queue1.poll();
queue2.add(res);
while (!queue2.isEmpty()) {
queue1.add(queue2.poll());
}
return res;
}
public boolean empty() {
return queue1.isEmpty();
}
}
class MyStack {
Queue<Integer> que;
public MyStack() {
que = new LinkedList<>();
}
public void push(int x) {
que.offer(x);
int size = que.size();
while(size-- > 1){
que.offer(que.remove());
}
}
public int pop() {
return que.poll();
}
public int top() {
return que.peek();
}
public boolean empty() {
return que.isEmpty();
}
}
class MyStack {
Queue<Integer> A, B;
public MyStack() {
this.A = new LinkedList<>();
this.B = new LinkedList<>();
}
// A用于存储数据， B作为辅助，始终让后插入的元素在队列头部
// 通过交换，让B队列始终为空。
public void push(int x) {
B.offer(x);
while(!A.isEmpty())
B.offer(A.poll());
Queue<Integer> temp = B;
B = A;
A = temp;
}
public int pop() {
return A.poll();
}
public int top() {
return A.peek();
}
public boolean empty() {
return A.isEmpty();
}
}
class MyStack {
Queue queue;
public MyStack() {
queue = new LinkedList();
}
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
//只有在pop和top的时候获取list最后一个元素处理，存储按照队列处理
//时间复杂度O(n)
//空间复杂度O(n)
class MyStack {
private Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
public void push(int x) {
queue.add(x);
}
public int pop() {
if (queue.isEmpty()) {
return -1;
}
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()){
list.add(queue.poll());
}
int res = list.get(list.size()-1);
list.remove(list.size()-1);
queue.addAll(list);
return res;
}
public int top() {
if (queue.isEmpty()) {
return -1;
}
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()){
list.add(queue.poll());
}
int res = list.get(list.size()-1);
queue.addAll(list);
return res;
}
public boolean empty() {
return queue.isEmpty();
}
}
class MyStack {
Queue<Integer> q;
public MyStack() {
q = new LinkedList<>();
}
public void push(int x) {
q.add(x);
for (int i = 0; i < q.size()-1; i++) {
q.add(q.remove());
}
}
public int pop() {
return q.remove();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}
shuaidi
共以下 60 个回答
一个队列实现栈
两个队列实现栈
两个队列，实现新进的元素在队列头，从而完成后进先出
代码如下
利用队列先进先出的特性，每入队一个就交换两个队列就行
思路和两栈实现队列一样，一个负责正常顺序进队，另一个负责从前面的队尾取后正常顺序压入，这里偷懒了，直接用了一个deque了hh
1、初始情况：qStackOut负责将push的值放在其头节点，然后与qStackIn（当前为空）交换，qStackIn的front成为最后push进的值；
2、循环情况：qStackOut负责将push的值放在其头节点，再将qStackIn的值依次放在其屁股后；结果再放回到qStackIn中，这样保持qStackIn的头始终是最后push的值，尾始终是最先push的值。
双队列
//典中典 que1,que2;
class MyStack {
public:
queue
MyStack() {
};
注意：在插入数据后需要将两个队列的元素进行交换，以保证插入数据后队列2的数据顺序即为栈的数据顺序
解题思路
根据题意，要用两个队列来实现栈，首先我们知道，队列是先进先出，栈是后进先出。
知道了以上要点，我们两个队列的用处也就一目了然了。
一个队列为主队列，一个为辅助队列，当入栈操作时，我们先将主队列内容导入辅助队列，然后将入栈元素放入主队列队头位置，再将辅助队列内容，依次添加进主队列即可。
好像这个题目的内存占用都很高。。。
“`{r} queue1; queue2;
class MyStack {
Queue
Queue
}
“`
思路：原理与上一道题类似，边界性考虑，栈的特性先进后出，双队列实现。一个队列压入，一个队列弹出。
两种方法，第一种较为简单，第二种略有繁琐。
我的思路：用两个队列实现栈，那肯定需要一个队列作为辅助队列。我用了两个队列queue1，queue2，其中queue2是给queue1打辅助的，不像用两个栈实现一个队列的思路解决这个问题，因为队列是先进先出的。把queue1的元素全部入队到queue2中，元素的出顺序是没有变化的。我是在出栈处上做文章，而leetcode官方题解是在入栈处做文章。入栈时直接入队到queue1中，出栈时queue1队尾的元素就是栈顶元素，我们需要获得它，直接将queue1队尾之前的元素全部入队到queue2，取得它，再把queue2的元素全部入队到queue1中。
leetcode官方题解的两种思路：一种用了两个队列queue1（作为真正的栈），queue2，入栈时元素e入队到queue2中，在把queue1的元素全部入队到queue2中，最后交换queue1、queue2，这样queue1队首的元素就是栈顶的元素，而queue2是空队。另一种用一个队列实现，就是在入栈时，把队列的队尾之前的元素再重新入队到这个队列。
思路:q1和q2两个队列，每次出栈时，q2依次入队q1出队的数据，直到q1剩下最后一个，这个数就是待出栈的数。接着把这个数暂存起来，q1再依次入队q2出队的数据，最后把暂存的那个数返回即可.
两个队列queue1、queue2，queue1在没有push时保存空队列，在push时先将数据加入到queue1，再将queue2的数据加入到queue1，保证queue1为空就将queue1的数据在加入到queue2。这是对queue2的poll（获取并移除此队列的头）操作就相当于对栈的出栈操作。
一个queue实现，主要在push部分，每添加一个数就重新排序，让队首的到队尾去
C语言实现 两个队列代替栈
注：根据题目原因，直接采用一个定长数组充当队列，减少了一些移动操作，所以代码用于解题可以，但是实际上数据量一大会出问题，解决方法是每次将数组元素往前挪front位，但是会消耗大量时间，解决方法2是使用链式队列
push操作
时间复杂度：O(n)
空间复杂度：O(n) 使用了另外一个栈作为缓冲空间
pop操作
时间复杂度：O(1)
空间复杂度：O(1)
top操作
时间复杂度：O(1)
空间复杂度：O(1)
empty操作
时间复杂度：O(1)
空间复杂度：O(1)
leetcode 时间beats 100%
空间 beats 22.3%
解题思路：栈为先入后出，使用队列（先入先出），需要保证最后入队列的元素最先出队列
时间复杂度：push为O(n),其余为O(1)
空间复杂度：O(1)
位置交换
使用一个队列
第一个队列是主队列，第二个是辅助队列，每次模拟入栈的时候先入辅助队，然后把主队列从左出队，入辅助队列，然后把辅助队赋给主队列，辅助队为空
下面代码
投机取巧
这里借别处老哥的方法写一下思路
这里只开一个队列，将原来需要将暂存到辅助队列里面的直接插入到队列的队尾
不得不说还是很舒服呀。
交换队列法，第一个队列为空，第二个队列为栈，入队首先入第一个队列，如果第二个队列有值，则将第二个队列的所有元素出队再入队第一个队列，然后交换第一个队列和第二个队列，第二个队列就为栈了。
使用list 实现
1、弄俩队列，一个是主队列，一个是辅助队列，新加元素时先将元素放入辅助队列中，在将主队列元素存储到辅助队列中，最后交换俩队列
2、弹出，返回栈顶元素，判断是否为空直接判断队列A就可以
时间复杂度：O(n)
空间复杂度：O(n)
第四天第二题
q1为存储队列，q2为辅助队列，将新元素存入q2，再将旧元素逐个存入q2，最后交换队列，保证q1元素正确
//一个队列