Deckkker 普通 2024年4月27日下午4:22

class MyStack:

def __init__(self):
    self.Que_1 = []
    self.Que_2 = []

def push(self, x: int) -> None:
    # Push element x onto stack. 
    self.Que_1.append(x)

def pop(self) -> int:
    # Removes the element on top of the stack and returns that element.
    while len(self.Que_1)>1:
        self.Que_2.append(self.Que_1.pop(0))
    res = self.Que_1.pop(0)
    self.Que_1, self.Que_2 = self.Que_2, self.Que_1
    self.Que_2.clear()
    return res

def top(self) -> int:
    # Get the top element.
    while len(self.Que_1)>1:
        self.Que_2.append(self.Que_1.pop(0))
    res = self.Que_1[0]
    self.Que_2.append(self.Que_1.pop(0))
    self.Que_1, self.Que_2 = self.Que_2, self.Que_1
    self.Que_2.clear()
    return res

def empty(self) -> bool:
    return not self.Que_1

入栈操作（push）：O(1)
出栈操作（pop）：平均情况下接近O(1)，最坏情况下O(n)
获取栈顶元素（top）：平均情况下接近O(1)，最坏情况下O(n)
判空操作（empty）：O(1)

0 赞同 0 条回复

山月普通 2024年3月15日下午3:41

//用两个队列实现栈，关键在于q1，q2是备份,难点在于pop，只让q1保留一个元素，其余的都备份到q2,如何实现这个while(size–)
class MyStack {
public:
queue q1;
queue q2;
MyStack() {

}

void push(int x) {
    q1.push(x);

}

int pop() {
    int size = q1.size();
    size--;
    while(size--)
    {
        q2.push(q1.front());
        q1.pop();
    }
    int res = q1.front();
    q1.pop();

    q1 = q2;
    while(!q2.empty())
    {
        q2.pop();
    }
    return res;

}

int top() {
    return q1.back();

}

bool empty() {
    return q1.empty();
}

};

/**
* 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();
* bool param_4 = obj->empty();
*/

0 赞同 0 条回复

YOLO 普通 2024年3月13日上午11:19

class MyStack {
    Queue<Integer>queue1;
    Queue<Integer>queue2;

    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();

    }
    //将x压入栈
    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer>temp = queue1;
        queue1 = queue2;
        queue2 = temp;

    }

    //移除栈顶端元素
    public int pop() {
        return queue1.poll();

    }

    //获得顶端元素
    public int top() {
        return queue1.peek();

    }

    //若栈空返回
    public boolean empty() {
        return queue1.isEmpty();

    }
}

0 赞同 0 条回复

晚风、普通 2024年3月12日下午11:03

class MyStack:

def __init__(self):
    self.q1=deque()
    self.q2=deque()

def push(self, x: int) -> None:
    self.q2.append(x)
    while self.q1:
        self.q2.append(self.q1.popleft())
    self.q1, self.q2 = self.q2, self.q1

def pop(self) -> int:
    return self.q1.popleft()

def top(self) -> int:
    return self.q1[0]

def empty(self) -> bool:
    return len(self.q1) == 0

思路：两个队列
q1用来储存，q2用来辅助
q1中存储的数字已经按照先进在后的方式存储
每次新增加一个数字，都先存在q2中，再将q1 popleft将q1中的结果按照在进在后的顺序存到q2中
再将q1 q2呼唤。这样q1就达到存储目的
时间复杂度：o(n)
空间复杂度：o(1)

0 赞同 0 条回复

Fancy 普通 2024年3月11日上午9:35

from collections import deque #这是一个双端队列
class MyStack:
def init(self):
self.queue1 = deque()
self.queue2 = deque()

def push(self, x: int) -> None: #修改push
    self.queue2.append(x)
    if self.queue1:
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
    # 互换引用
    temp = self.queue1
    self.queue1 = self.queue2
    self.queue2 = temp
    # 每次交换完之后。queue2都为空
def pop(self) -> int:
    return self.queue1.popleft()

def top(self) -> int:
    return self.queue1[0]

def empty(self) -> bool:
    if not self.queue1:
        return True
    else:
        return False

0 赞同 0 条回复

一颗红豆普通 2024年3月10日下午4:53

时间复杂度O（n）空间复杂度O（1）
class MyStack {
public:
queue q1;
queue q2;
MyStack() {
std::queue q1;
std::queue q2;

}

void push(int x) {
    q2.push(x);
    while(!q1.empty())
    {
        q2.push(q1.front());
        q1.pop();
    }
    swap(q1,q2);
}

int pop() {
    int r = q1.front();
    q1.pop();
    return r;

}

int top() {
    // int r = q1.front();
    return q1.front();
}

bool empty() {
    if (q1.empty())
    {
        return true;
    }
    else
    {
        return false;
    }

}

};

/**
* 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();
* bool param_4 = obj->empty();
*/

0 赞同 0 条回复

e=mc² 普通 2024年3月9日下午9:02

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }

    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        queue1 = queue2;
        queue2 = new ArrayDeque<>();
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

铭命鸣普通 2024年3月9日上午10:36

两个队列，出栈的时候，哪个队列有值，就一个一个出队列放到另一个队列里，等到最后一个值时直接return。
这样任意时刻总有一个队列有值，一个队列是空的。
class MyStack {
    LinkedList<Integer> l1;
    LinkedList<Integer> l2;

    public MyStack() {
        l1 = new LinkedList<Integer>();
        l2 = new LinkedList<Integer>();
    }

    public void push(int x) {
        if(!l1.isEmpty()){
            l1.add(x);
        }else if(!l2.isEmpty()){
            l2.add(x);
        }else{
            l1.add(x);
        }
    }

    public int pop() {

        while(!l1.isEmpty()){
            Integer value = l1.pop();
            if(l1.isEmpty()){
                return value;
            }
            l2.add(value);
        }


        while(!l2.isEmpty()){
            Integer value = l2.pop();
            if(l2.isEmpty()){
                return value;
            }
            l1.add(value);
        }

        return -1;
    }

    public int top() {

        while(!l1.isEmpty()){
            Integer value = l1.pop();
            l2.add(value);
            if(l1.isEmpty()){
                return value;
            }
        }


        while(!l2.isEmpty()){
            Integer value = l2.pop();
            l1.add(value);
            if(l2.isEmpty()){
                return value;
            }
        }

        return -1;
    }

    public boolean empty() {
        if(l1.isEmpty() && l2.isEmpty()){
            return true;
        }
        return false;
    }
}

0 赞同 0 条回复

零普通 2024年3月8日下午4:28

思路：两个队列，先入一个队列，再将另一个队列的所有元素插入这个队列，然后两者互换
代码：


    class MyStack {
        Queue queue1,queue2;
        public MyStack() {
            queue1 = new LinkedList<>();
            queue2 = new LinkedList<>();
        }

        public void push(int x) {
            queue2.offer(x);
            while(!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            Queue temp = queue1;
            queue1 = queue2;
            queue2 = temp;
         }

        public int pop() {
            return queue1.poll();
        }

        public int top() {
            return queue1.peek();
        }

        public boolean empty() {
            return queue1.isEmpty();
        }
    }

0 赞同 0 条回复

Yeah~ 普通 2024年3月8日下午3:02

“`c++

class MyStack {
public:
queue q1;
queue q2;
MyStack() {

}

void push(int x) {
    q2.push(x);
    while(!q1.empty()){
        q2.push(q1.front());
        q1.pop();
    }
    q2.swap(q1);
}

int pop() {
    int ret = q1.front();
    q1.pop();
    return ret;

}

int top() {
    return q1.front();
}

bool empty() {
    if(q1.empty()){
        return true;
    }else return false;
}

};
空间O(1)，时间O(n)
进2队，再把1队搬过来2队依次入队，交换1，2队，这样就能实现后进先出。

“`

0 赞同 0 条回复

小耿普通 2024年3月8日上午10:41

“`C++
class MyStack {
public:
queue queue1, queue2;
MyStack() {

}

void push(int x) {
    queue2.push(x);
    while(!queue1.empty()) {
         queue2.push(queue1.front());
         queue1.pop();
    }
    swap(queue1, queue2);
}

int pop() {
        int a = queue1.front();
        queue1.pop();
        return a;        
}

int top() {
    int a = queue1.front();
    return a;
}

bool empty() {
    return queue1.empty();
}

};

“`C++
使用两个queue 来实现栈，
让queue1始终是栈的格式，最前面的是栈顶，也就是最后加入的值。
让queue2作为中转栈，每次加入一个元素时，把queue1的元素依次加到queue2中，然后再交换queue1和queue2,这样新加入的元素又到了queue1的最前面。
pop 和 top 其实就很简单了。只需要操作最前面的元素即可。

0 赞同 0 条回复

普通 2024年3月7日下午7:56

class MyStack {
public:

queue<int> queue1; 
queue<int> queue2;   // 作为临时队列
MyStack() {

}

void push(int x) {
    queue2.push(x);
    while(!queue1.empty())
    {
        queue2.push(queue1.front());
        queue1.pop();
    }
    swap(queue1,queue2);
}

int pop() {
    int r=queue1.front();
    queue1.pop();
    return r;
}

int top() {
    int r=queue1.front();
    return r;
}

bool empty() {
    return queue1.empty();
}

};
采用两个队列，一个作为临时队列，
每次push(x)时，把x放入临时队列中，再将另一个队列中的元素依次出队再入队，然后swap

0 赞同 0 条回复

　南木普通 2024年3月7日下午4:47

栈和队列的实现就是互相倒来倒去，时间复杂度O（n），空间复杂度O（1）

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
    }

    public void push(int x) {
        q2.add(x);
        while(!q1.isEmpty()){
            q2.add(q1.poll());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.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();
 */

0 赞同 0 条回复

Let it be 永久会员 2024年3月7日下午12:03

class MyStack {
Queue A;
Queue B;
public MyStack() {
A = new LinkedList();
B = new LinkedList();
}

public void push(int x) {
    B.offer(x);
    while(!A.isEmpty()){
        B.offer(A.poll());
    }
    Queue<Integer> temp = A;
    A = B;
    B = temp;
}

public int pop() {
    return A.poll();
}

public int top() {
    return  A.peek();
}

public boolean empty() {
    return A.isEmpty();
}

}时间复杂度O（n）空间复杂度O（n）

0 赞同 0 条回复

HU 普通 2024年3月7日上午5:58

var MyStack = function() {
    // 创建主队列queue和辅助队列_queue
    this.queue = [];
    this._queue = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    // 先弹出主队列中的元素至插入辅助队列
    while(this.queue.length != 0) {
        this._queue.push(this.queue.shift());
    }
    // 再将元素x插入主队列
    this.queue.push(x);
    // 再将辅助队列元素依次弹出并插入主队列
    while(this._queue.length != 0) {
        this.queue.push(this._queue.shift());
    }
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    return this.queue.shift();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.queue[0];
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.queue.length;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */

0 赞同 0 条回复

南梁陈庆之普通 2024年3月6日下午5:43

两个列队实现栈
队列是先进先出的数据结构，实现一个栈先进后出的效果。
队列A作为存储结构，队列B辅助存储
1、除了存储offer时，主程序其他操作（取最新值、删除最新值、获取是否为空）与队列中方法一致
2、存储值时，先将值保存在队列B中，然后将队列A中值按先进先出的顺序保存在队列B中；然后再将队列B中的值按先进先出的顺序保存在队列A中，则此时最新保存的值会在列队最前面，如果取值会先取出

class MyStack {
    Queue<Integer> queueA ,queueB;
    public MyStack() {
        queueA = new LinkedList<>();
        queueB = new LinkedList<>();
    }

    public void push(int x) {
        queueB.offer(x);
        while (!queueA.isEmpty()) {
            queueB.offer(queueA.poll());
        }
        while (!queueB.isEmpty()) {
            queueA.offer(queueB.poll());
        }
    }

    public int pop() {
        return queueA.poll();
    }

    public int top() {
        return queueA.peek();
    }

    public boolean empty() {
        return queueA.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();
 */

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月6日上午9:30

class MyStack {
public:
    MyStack() {

    }

    // 一个队列1用来保存出栈的顺序
    // 另一个队列2作为中介，每次入队一个新元素，就把保存出栈顺序的那个队列1的元素加入此队列2后面
    // 再交换二者，那么此时队列1又保存了新的正确出栈顺序
    void push(int x) {
        que1.push(x);
        while(!que2.empty()) {
            que1.push(que2.front()); que2.pop();
        }
        swap(que1, que2);
    }

    int pop() {
        int res = que2.front();
        que2.pop();
        return res;
    }

    int top() {
        return que2.front();
    }

    bool empty() {
        return que2.empty();
    }
private:
    queue<int> que1, que2;
};

0 赞同 0 条回复

神经蛙普通 2024年3月6日上午12:14

class MyStack {
public:
queue queue1;
queue queue2;

/** Initialize your data structure here. */
MyStack() {

}

/** Push element x onto stack. */
void push(int x) {
    queue2.push(x);
    while (!queue1.empty()) {
        queue2.push(queue1.front());
        queue1.pop();
    }
    swap(queue1, queue2);
}

/** Removes the element on top of the stack and returns that element. */
int pop() {
    int r = queue1.front();
    queue1.pop();
    return r;
}

/** Get the top element. */
int top() {
    int r = queue1.front();
    return r;
}

/** Returns whether the stack is empty. */
bool empty() {
    return queue1.empty();
}

};
时间复杂度除了添加是O(n)，其它都是O（1）；
空间复杂度是O(n)

0 赞同 0 条回复

mpweixin用户普通 2024年3月5日下午10:11

java
class MyStack{
Queue queue1;
Queue queue2;

public MyStack(){
    queue1 = new LinkedList<Integer>();
    queue2 = new LinkedList<Integer>();
}

public void push(int x){
    queue2.offer(x);
    while(!queue1.isEmpty()){
        queue2.offer(queue1.poll());
    }
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;
}

public int pop(){
    return queue1.poll();
}

public int top(){
    return queue1.peek();
}

public boolean empty(){
    return queue1.isEmpty();
}

}
提交

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月5日下午8:43

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList();
        queue2 = new LinkedList();
    }

    public void push(int x) {
        //保持Q1为空
        queue1.offer(x);
        while(!queue2.isEmpty()){
            queue1.offer(queue2.poll());
        }

        // 交换队列1和队列2
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue2.poll();
    }

    public int top() {
        return queue2.peek();
    }

    public boolean empty() {
        return queue2.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();
 */

时间复杂度除了添加操作是 O(n)，其他操作都是 O(1)
空间复杂度添加操作是 O(n)

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月5日下午8:27

import java.util.Deque;

class MyStack {
    // 队列特性：先进先出；栈特性：先进后出
    // 利用两个队列实现栈，每次新增元素时 Q2 空队列添加新元素，Q1 队列将原有数据按序添加到 Q2 队列中
    // Q1 与 Q2 交换引用
    private Deque<Integer> q1 = new ArrayDeque<>();
    private Deque<Integer> q2 = new ArrayDeque<>();

    public MyStack() {
    }

    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Deque<Integer> q = q1;
        q1 = q2;
        q2 = q;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
    // 时间复杂度 除了添加操作是 O(n)，其他操作都是 O(1)
    // 空间复杂度 添加操作是 O(n)
}

0 赞同 0 条回复

Jimmy 普通 2024年3月5日下午8:01

class MyStack {
private:
    queue<int> q1;// 模仿出来的栈
    queue<int> q2;// 用于q1的备份

public:
    MyStack() {

    }

    void push(int x) {
        q1.push(x);
    }

    int pop() {
        int size = q1.size()-1;
        while(size--){// 将que1导入que2，但要留下最后一个元素
            q2.push(q1.front());
            q1.pop();
        }
        int result = q1.front();//留下的最后一个元素就是返回值
        q1.pop();
        q1 = q2;// 把q2赋值给q1
        while(!q2.empty()){// 清空q2
            q2.pop();
        }
        return result;
    }

    int top() {
        return q1.back();
    }

    bool empty() {
        return q1.empty();
    }
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

0 赞同 0 条回复

NULL 普通 2024年3月5日下午7:02

class MyStack {
// 用一个队列实现
Queue queue;

public MyStack() {
    queue = new LinkedList<>();
}

public void push(int x) {
    queue.offer(x);
    int size = queue.size();
    while(size -- > 1){
        queue.offer(queue.poll());
    }
    return;
}

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();
*/

0 赞同 0 条回复

Raphtalia. 普通 2024年3月5日下午4:43

class MyStack {
public:
queue q1;
queue q2;
MyStack() {

}

void push(int x) {
    q2.push(x);
    while(!q1.empty()){
        q2.push(q1.front());
        q1.pop();
    }
    swap(q1,q2);
}

int pop() {
    int ans = q1.front();
    q1.pop();
    return ans;
}

int top() {
    return q1.front();
}

bool empty() {
    return q1.empty();
}

};

/**
* 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();
* bool param_4 = obj->empty();
*/
时间复杂度O(n)

0 赞同 0 条回复

持之以恒:-) 普通 2024年3月5日下午3:55

使用队列queue中的add poll peek 以及size方法实现FILO

时间复杂度O(n)空间复杂度为O(n)

思路

插入数据时两种情况
其中一个queue有值，向有数据的queue插值
两个都没值，选择list1插入
删除元素两种情况
list中有值
list1 中有值 -> 一直poll到list2中，直到list1.size() 1
list2中有值 -> 一直poll到list1中，直到list2.size() 1
list没有值

class MyStack {

    LinkedList<Integer> list1; 
    LinkedList<Integer> list2; 

    public MyStack() {
        list1 = new LinkedList<>();
        list2 = new LinkedList<>();
    }

    // 哪个队列不为空哪个队列插入元素
    public void push(int x) {
        if(list1.size() != 0)
            list1.add(x);
        else if(list2.size() != 0)
            list2.add(x);
            // 都为空时插入list1
        else{
            list1.add(x);
        }
    }

    // 哪个队列不为空，哪个队列的tail element为新值
    public int pop() {

        // list1 有数据
        while(list1.size() > 1){
            list2.add(list1.poll());
        }
        if(list1.size() == 1)
            return list1.poll();

        // list2 有数据
        while(list2.size() > 1)
            list1.add(list2.poll());

        if(list2.size() == 1)
            return list2.poll();
        // 都没有数据时
        return -1;
    }

    public int top() {
        int topValue = -1;
        if(empty())
            return -1;
        if(list1.size() != 0){
            while(list1.size() > 1){
                list2.add(list1.poll());
            }
            topValue = list1.poll();
            list2.add(topValue);
            return topValue;
        }
        else{
            while(list2.size() > 1){
                list1.add(list2.poll());
            }
            topValue = list2.poll();
            list1.add(topValue);
            return topValue;
        }

    }

    public boolean empty() {
        if(list1.size() == 0 && list2.size() == 0)
            return true;
        return false;
    }
}

0 赞同 0 条回复

Jankin 普通 2024年3月5日下午3:19

class MyStack {

    Queue queue1;
    Queue queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.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();
 */

时间复杂度：入栈操作 O(n)，其余操作都是 O(1)
空间复杂度：O(n)

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月5日下午2:40

一个队列实现栈的入队出队操作
class MyStack {

Queue<Integer> queue;

public MyStack() {
    queue = new LinkedList<>();
}

//每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
public void push(int x) {
    queue.offer(x);
    int size = queue.size();
    //移动除了 A 的其它数
    while (size-- > 1)
        queue.offer(queue.poll());
}

public int pop() {
    return queue.poll();
}

}

0 赞同 0 条回复

=.= 普通 2024年3月5日下午2:26

class MyStack {

Deque<Integer> queue1;
Deque<Integer> queue2;

public MyStack() {
    queue1 = new ArrayDeque<>();
    queue2 = new ArrayDeque<>();
}

public void push(int x) {
    queue2.addLast(x);
    while(!queue1.isEmpty()){
        queue2.addLast(queue1.removeFirst());
    }
    Deque<Integer> q = queue1;
    queue1 = queue2;
    queue2 = q;
}

public int pop() {
    return queue1.removeFirst();
}

public int top() {
    return queue1.getFirst();
}

public boolean empty() {
    return queue1.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();
*/

插入时间复杂度O(n)，其余时间复杂度O(1)；
空间复杂度O(n)。

0 赞同 0 条回复

刘超波普通 2024年3月5日下午2:17

class MyStack {
Queue q1;
Queue q2;
public MyStack() {
q1 = new LinkedList();
q2 = new LinkedList();
}

public void push(int x) {
    q2.offer(x);
    while (!q1.isEmpty())
    {
        q2.offer(q1.poll());
    }

    Queue<Integer> tem = q1;
    q1 = q2;
    q2 = tem;
}

public int pop() {
    return q1.poll();
}

public int top() {
    return q1.peek();
}

public boolean empty() {
    return q1.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();
*/打卡

0 赞同 0 条回复

kfaebot 普通 2024年3月5日上午11:57

class MyStack {
public:
    //主队列
    queue<int>main_que;
    //辅助队列
    queue<int>help_que;

    MyStack() {

    }

    void push(int x) {
        help_que.push(x);
        //入栈将主队列内容导入辅助队列
        //然后将入栈元素放入主队列队头位置
        //再将辅助队列内容添加进主队列
        while(!main_que.empty()){
            int tmp=main_que.front();
            help_que.push(tmp);
            main_que.pop();
        }
        swap(help_que,main_que);
    }

    int pop() {
        int tmp=main_que.front();
        main_que.pop();
        return tmp;
    }

    int top() {
        return main_que.front(); 

    }

    bool empty() {
        if(main_que.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

0 赞同 0 条回复

Monou 普通 2024年3月5日上午11:20

队列实现栈
class MyStack {
Queue queue1;
Queue queue2;

 public MyStack() {
    queue1 = new LinkedList<>();
    queue2 = new LinkedList<>();
}

public void push(int x) {
    if (!queue2.isEmpty()){
        Queue<Integer> temp = queue2;
        queue2 = queue1;
        queue1 = temp;
    }
    queue1.offer(x);
}

public int pop() {
    if (queue1.isEmpty() && queue2.isEmpty()) return -1;
    if (!queue2.isEmpty()){
        Queue<Integer> temp = queue2;
        queue2 = queue1;
        queue1 = temp;
    }
    while (!queue1.isEmpty()){
        Integer poll = queue1.poll();
        if (queue1.isEmpty()) return poll;
        queue2.offer(poll);
    }
    return -1;
}

public int top() {
    if (queue1.isEmpty() && queue2.isEmpty()) return -1;
    if (!queue2.isEmpty()){
        Queue<Integer> temp = queue2;
        queue2 = queue1;
        queue1 = temp;
    }
    while (!queue1.isEmpty()){
        Integer poll = queue1.poll();
        queue2.offer(poll);
        if (queue1.isEmpty()) return poll;
    }
    return -1;
}

public boolean empty() {
    return queue2.isEmpty() && queue1.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();
*/

0 赞同 0 条回复

😴 普通 2024年3月5日上午11:03

class MyStack {
//定义队列
Queue queue1;
Queue queue2;

public MyStack() {
     queue1 = new LinkedList<Integer>();
     queue2 = new LinkedList<Integer>();
}

//入栈 用两个队列实现
public void push(int x) {
    queue2.offer(x);//在队列末尾添加x
    while(!queue1.isEmpty()){
        queue2.offer(queue1.poll());
    }
    //将两个队列元素互换
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;

}

public int pop() {
    return queue1.poll();

}

public int top() {
    return queue1.peek();
}

public boolean empty() {
    return queue1.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();
*/
重点在于思路理解，如何转换
时间复杂度 O(1)
空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2024年3月5日上午10:59

public MyStack() {
queue1 = new LinkedList();
queue2 = new LinkedList();
}

public void push(int x) {
     queue2.offer(x);
    while (!queue1.isEmpty()) {
        queue2.offer(queue1.poll());
    }
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;
}

public int pop() {
    return queue1.poll();
}

public int top() {
     return queue1.peek();
}

public boolean empty() {
    return queue1.isEmpty();}

思路：用一个队列即可每次将前size-1个元素先出队再入队，插入就正常做

0 赞同 0 条回复

神经蛙普通 2024年3月5日上午10:45

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
// 先取出size
        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();

    }
}

0 赞同 0 条回复

紫芝普通 2024年3月5日上午9:59

思路：定义两个队列 qIn, qOut, 分别负责栈的输入与输出。输入时使用qIn.push(x), 输出时先将qIn内的数据输出到qOut（剩余一个元素在qIn），然后输出剩余的一个元素即为栈顶元素，最后将qOut的数据又输入到qIn内。

“`c++
class MyStack {
public:
MyStack() {

}

void push(int x) {
    qIn.push(x);
}

int pop() {
    int size = qIn.size();
    size--;
    while (size--) {
        qOut.push(qIn.front());
        qIn.pop();
    }
    int res = qIn.front();
    qIn.pop();
    while (!qOut.empty()) {
        qIn.push(qOut.front());
        qOut.pop();
    }
    return res;
}

int top() {
    return qIn.back();
}

bool empty() {
    return qIn.empty() && qOut.empty();
}

private:
queue qIn, qOut;
};

“`

0 赞同 0 条回复

Yuki 永久会员 2024年3月5日上午9:45

打卡
https://leetcode.cn/problems/implement-stack-using-queues/solutions/2668150/dui-lie-mo-ni-zhan-by-yukislab-8c7t

0 赞同 0 条回复

Free 普通 2024年3月5日上午8:36

class MyStack 
{
public:
    MyStack() 
    {}

    void push(int x) 
    {
        main.push(x);
    }

    int pop() 
    {
        int res = main.back();
        int n = main.size();
        for(int i = 0; i < n - 1; i++)
        {
            main.push(main.front());
            main.pop();
        }
        main.pop();
        return res;
    }

    int top() 
    {
        return main.back();
    }

    bool empty() 
    {
        return main.empty();
    }
private:
    queue<int> main;
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

时空复杂度O(n)

0 赞同 0 条回复

莫～慢～待普通 2024年3月5日上午12:19

class MyStack {
Queue queue1;
Queue queue2;
public MyStack() {
queue1=new LinkedList();
queue2=new LinkedList();
}

public void push(int x) {
queue2.offer(x);
while(!queue1.isEmpty())
{
    int top=queue1.poll();
    queue2.offer(top);
}
  Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;
}

public int pop() {
return queue1.poll();
}

public int top() {
return queue1.peek();
}

public boolean empty() {
return queue1.isEmpty();
}

}
利用两个队列实现栈，其中队列2为辅助角色，每次都将新插入的元素放入其中，并将队列1中的依次插入队列2，以此维护“先进后出”的栈风格，最后将队列1和队列2互换，保持队列2经常为空。

0 赞同 0 条回复

方铎码农普通 2024年3月5日上午12:04

class MyStack {

    Deque<Integer> q1;
    Deque<Integer> q2;

    public MyStack() {
        this.q1 = new ArrayDeque<>();
        this.q2 = new ArrayDeque<>();
    }

    public void push(int x) {
        q2.offer(x);
        while(!q1.isEmpty()){
            q2.offer(q1.poll());
        }

        Deque<Integer> q = q1;
        q1 = q2;
        q2 = q;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.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();
 */

时间复杂度O(n),空间复杂度O(n)

0 赞同 0 条回复

Laboratory 普通 2024年3月5日上午12:00

class MyStack {
    LinkedList<Integer> queue1;
    LinkedList<Integer> queue2;    
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if(queue2.size() == 0) {
            queue1.addLast(x);
        } else {
            queue2.addLast(x);
        }
    }

    public int pop() {
        if(queue1.size() != 0) {
            while(queue1.size()-1 > 0) {
                queue2.addLast(queue1.removeFirst());
            }
            return queue1.removeLast();
        } else {
            while(queue2.size()-1 > 0) {
                queue1.addLast(queue2.removeFirst());
            }
            return queue2.removeLast();
        }
    }

    public int top() {
        if(queue1.size() == 0 && queue2.size() == 0){
            return -1;
        }
        if(queue2.size() != 0) {
            return queue2.getLast();
        } else {
            return queue1.getLast();
        }
    }

    public boolean empty() {
        if(queue1.size() == 0 && queue2.size() == 0){
            return true;
        } 
        return false;
    }
}

/**
 * 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();
 */

时间复杂度O(n),空间复杂度O(n)

0 赞同 0 条回复

MARS 普通 2024年3月4日下午11:54

day4第二题

var MyStack = function () {
    this.queue = []
    this.tempQueue=[]
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
    this.queue.push(x)
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
    for(let i=0,length=this.queue.length-1;i<length;i++){
        this.tempQueue.push(this.queue.shift())
    }
    let res = this.queue.shift()
    let temp = this.queue
    this.queue = this.tempQueue
    this.tempQueue = temp
    return res
};

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
    let val = this.pop()
    this.push(val)
    return val
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    return this.queue.length == 0
};

0 赞同 0 条回复

heathhou 普通 2024年3月4日下午10:29

class MyStack {
public:
    queue<int> queue1;
    queue<int> queue2;

    MyStack() {

    }

    void push(int x) {
        queue2.push(x);
        while(!queue1.empty()){
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }

    int pop() {
        int ans = queue1.front();
        queue1.pop();
        return ans;
    }

    int top() {
        return queue1.front();
    }

    bool empty() {
        return queue1.empty();
    }
};

使用两个队列模拟一个栈操作。队列2用来辅助入栈操作。队列1保存出队列的数据与出栈的数据是一致的。

0 赞同 0 条回复

机电皮怪永久会员 2024年3月4日下午9:53

时间复杂度O(n*(n+1)/2)
空间复杂度O(2n)

C++

class MyStack {
    queue <int> queue1;
    queue <int> queue2;
public:
    MyStack() {


<pre><code>}

void push(int x) {
    //优先入栈queue1
    if(queue1.empty() == true)
    {
        queue1.push(x);
        //queue2有元素则入栈到queue1
        while(queue2.empty() == false)
        {
            int temp = queue2.front();
            queue1.push(temp);
            queue2.pop();
        }
    }
    //反之亦然
    else
    {
        queue2.push(x);
        while(queue1.empty() == false)
        {
            int temp = queue1.front();
            queue2.push(temp);
            queue1.pop();
        }
    }
}

int pop() {
    if(MyStack::empty() == true)
    {
        return -1;
    }
    int res = MyStack::top();
    if(queue1.empty() == false)
    {
        queue1.pop();
    }
    else
    {
        queue2.pop();
    }
    return res;
}

int top() {
    //栈顶元素是非空队列头部
    if(queue1.empty() == false)
    {
        return queue1.front();
    }
    else
    {
        return queue2.front();
    }
}

bool empty() {
    return (queue1.empty() && queue2.empty());
}
</code></pre>

};

0 赞同 0 条回复

进取普通 2024年3月4日下午9:26

class MyStack {
public:
queue q1;
queue q2;
MyStack() {
}

void push(int x) {
    q1.push(x);
    while (!q2.empty()){
        int n = q2.front();
        q2.pop();
        q1.push(n);
    }
    while (!q1.empty()){
        int n = q1.front();
        q1.pop();
        q2.push(n);
    }
}

int pop() {
    int n = q2.front(); 
    q2.pop();
    return n;
}

int top() {
    return q2.front();
}

bool empty() {
    return q2.empty();
}

};
时空复杂度O(n)

0 赞同 0 条回复

言之命至普通 2024年3月4日下午9:06

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;


    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }


    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }
    public boolean empty() {
        return queue1.isEmpty();
    }
}
时间复杂度：入栈操作 O(n),其余操作都是 O(1)。其中 n 是栈内的元素个数。
空间复杂度：O(n)，其中 n 是栈内的元素个数。需要使用两个队列存储栈内的元素。

0 赞同 0 条回复

云无深雁影普通 2024年3月4日下午8:54

class MyStack {
Queue q1;
Queue q2;

public MyStack() {
    q1 = new LinkedList<Integer>();
    q2 = new LinkedList<Integer>();   
}

public void push(int x) {
    if(q1.isEmpty()){
        q1.offer(x);
        while(!q2.isEmpty()){
            q1.offer(q2.poll());
        }
    }
    else{
        q2.offer(x);
        while(!q1.isEmpty()){
            q2.offer(q1.poll());
        }
    }


}

public int pop() {
    if(!q1.isEmpty()){
        int ans = q1.poll();
        return ans;
    }
    else{
        int ans = q2.poll();
        return ans;
    }

}

public int top() {
    if(!q1.isEmpty()){
        int ans = q1.peek();
        return ans;
    }
    else{
        int ans = q2.peek();
        return ans;
    }

}

public boolean empty() {
    if(q1.isEmpty() && q2.isEmpty())
        return true;
    else
        return false;

}

}
//每次插入，先插入空队列，然后把另一队列内容插入到本队列队尾。便能始终保持队列倒置。
//时间复杂度 push O(n) popO(1)
//空间复杂度 O1

0 赞同 0 条回复

王位詮釋普通 2024年3月4日下午8:14

class MyStack {
    Deque<Integer> queue1;
    Deque<Integer> queue2;
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        while(queue1.size()!=1){
            queue2.offer(queue1.poll());
        }
        int val = queue1.poll();
        while(!queue2.isEmpty()){
            queue1.offer(queue2.poll());
        }
        return val;
    }

    public int top() {
        int val = pop();
        push(val);
        return val;
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}
思路：一个队列专门用来存储数据queue1，另一个队列queue2用来中转
push方法直接将数据插入queue1的队尾中，时间复杂度是O(1)
pop方法输出的值应该是queue1的最后一个值，所以将前面的所有值中转到queue2中，所需要的值之后，再将queue2中的值中转回来，时间复杂度：O(n)
top方法是获取栈顶元素，和pop思路一样，不过不能删除，相当于pop之后再push进来，时间复杂度：O(n)
empty直接返回queue是否为空，时间复杂度为O(1)

0 赞同 0 条回复

Yox 普通 2024年3月4日下午8:04

class MyStack:

def __init__(self):
    self.q1 = deque()
    self.q2 = deque()


def push(self, x: int) -> None:
    self.q1.append(x)


def pop(self) -> int:
    while len(self.q1) > 1:
        self.q2.append(self.q1.popleft())

    top = self.q1.popleft()
    self.q1, self.q2 = self.q2, self.q1
    return top


def top(self) -> int:
    while len(self.q1) > 1:
        self.q2.append(self.q1.popleft())
    top = self.q1[0]

    self.q2.append(self.q1.popleft())

    tmp = self.q2
    self.q2 = self.q1
    self.q1 = tmp

    return top



def empty(self) -> bool:
    return len(self.q1) == 0

【基本数据结构】LeetCode 225. 用队列实现栈

共以下 48 个回答

使用队列queue中的add poll peek 以及size方法实现FILO

思路

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()

# 回答此问题取消回复

【基本数据结构】LeetCode 225. 用队列实现栈

共以下 48 个回答

使用队列queue中的add poll peek 以及size方法实现FILO

思路

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()

# 回答此问题 取消回复

# 回答此问题取消回复