ShadowyHalo 永久会员 2025年6月7日下午4:14

class MyStack {
Queue queue1;//对应栈
Queue queue2;//操作队列

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

/**2放置新元素，然后1存储整个队列，将1传入2后再传回去 */
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();
}

}

/**
* 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 条回复

Lil Lee_ 普通 2024年12月3日下午5:43

//双队列实现栈
class MyStack {
    Queue<Integer> A, B; 
    public MyStack() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

    public void push(int x) {
        B.add(x);
        while(!A.isEmpty()){
            B.add(A.remove());
        }
        Queue<Integer> C = B;
        B = A;
        A = C;
    }

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

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

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

0 赞同 0 条回复

yelinliner 普通 2024年12月2日下午12:04

###

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

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

    public void push(int x) {
        queue1.offer(x);
        // 把队列2的全部转给a队列
        while (!queue2.isEmpty()) {
            queue1.offer(queue2.poll());
        }
        // 再交换两个队列，确保队列1始终处于空队列，队列2是调整之后的队列
        Queue temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

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

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

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

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午11:59

/**
解题思路：采用一个队列，新值入队后，将队列内已有值出队在入队，以做到队头元素为最后加入的元素
时间复杂度O(N),空间复杂度O(N)
ps:真是为了实现而实现
 */
class MyStack {

    Deque<Integer> q;

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

    public void push(int x) {
        int sz = q.size();
        q.add(x);
        for (int i = 0; i < sz; i++){
            q.add(q.pop());
        }
    }

    public int pop() {
        return q.pop();
    }

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

    public boolean empty() {
        return q.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 条回复

mpweixin用户普通 2024年11月30日下午7:48

需要借助一个辅助队列，每次push的时候，先将元素放入，再放入已有的元素。

from collections import deque

class MyStack:

    def __init__(self):
        self.s1 = deque()
        self.s2 = deque()


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


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


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


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



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

0 赞同 0 条回复

Firefly 普通 2024年11月30日下午12:51

队列
class MyStack {
public:
MyStack() {

}

void push(int x) 
{   
    int nSize=m_q1.size();
    m_q1.push(x);
    for(auto i=0;i<nSize;i++)
    {
        m_q1.push(m_q1.front());
        m_q1.pop();
    }
}

int pop() 
{
    if(!empty())
    {
        auto nValue=m_q1.front();;
        m_q1.pop();
        return nValue;
    }
    return -1;
}

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

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

private:
std::queue m_q1;
};

/**
* 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 条回复

岱永久会员 2024年11月29日下午3:33

两个队列实现栈

class MyStack {
    Queue<Integer> A;
    Queue<Integer> B;

    public MyStack() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

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

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

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

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

0 赞同 0 条回复

LovLe 普通 2024年11月29日上午11:49

中转队列
先进后出，后进先出：中转队列始终先放新进来的，然后把q1已经是栈顺序的元素依次放过来，那么得到新的栈。然后把这个新的放到q1，进行交换。所以每次新元素进来的时候，中转队列总是为空。

class MyStack:

    def __init__(self):
        # append,pop(0)
        self.queue1=[]
        self.queue2=[]

    def push(self, x: int) -> None:
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.pop(0))
        self.queue1,self.queue2=self.queue2,self.queue1

    def pop(self) -> int:
        return self.queue1.pop(0) if self.queue1 else -1


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

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


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

0 赞同 0 条回复

陆狗陆狗普通 2024年11月28日下午11:21

class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;

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

    public void push(int x) {
        if(q1.isEmpty()){
            // q1为空就把新元素作为q1的首元素，能保证先出去
            q1.offer(x);
            // 把q2的全部数据放到q1里面
            while(!q2.isEmpty()){
                q1.offer(q2.poll());
            }
        }else{
            q2.offer(x);
            while(!q1.isEmpty()){
                q2.offer(q1.poll());
            }
        }
    }

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

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

    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

0 赞同 0 条回复

🌟 普通 2024年11月27日上午9:22

“`cpp
//简单题
class MyStack {
queue main;
queue temp;
public:
MyStack() {

}

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

int pop() {

    int val=main.front();
    main.pop();
    return val;
}

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

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

};

“`cpp

0 赞同 0 条回复

hjx 普通 2024年11月26日下午8:37

代码
class MyStack {
Queueque1;
Queueque2;
public MyStack() {
que1=new LinkedList<>();
que2=new LinkedList<>();
}
//1
//2 1
public void push(int x) {
if(que2.isEmpty()){
que2.offer(x);
while(!que1.isEmpty()){
int val=que1.poll();
que2.offer(val);
}
}else{
que1.offer(x);
while(!que2.isEmpty()){
int val=que2.poll();
que1.offer(val);
}
}

}

public int pop() {
    if(!que2.isEmpty()){
        return que2.poll();
    }else{
        return que1.poll();
    }
}

public int top() {
    if(!que2.isEmpty()){
        return que2.peek();
    }else{
        return que1.peek();
    }
}

public boolean empty() {
    if(que1.isEmpty() && que2.isEmpty())
        return true;
    return false;
}

}

0 赞同 0 条回复

生活在经验里普通 2024年11月26日上午11:02

type MyStack struct {
    slice []int  // 用切片实现栈
}

func Constructor() MyStack {
    myStack := MyStack{}
    myStack.slice = make([]int, 0)
    return myStack
}

func (this *MyStack) Push(x int) {
    this.slice = append(this.slice, x)
}

func (this *MyStack) Pop() int {
    element := this.slice[len(this.slice)-1]
    this.slice = this.slice[0 : len(this.slice)-1]
    return element
}

func (this *MyStack) Top() int {
    index := len(this.slice) - 1
    return this.slice[index]
}

func (this *MyStack) Empty() bool {
    if len(this.slice) <= 0 {
        return true
    } else {
        return false
    }
}

0 赞同 0 条回复

越努力越幸运普通 2024年11月26日上午12:21

“`c++
class MyStack {
public:
queue queue1;
queue 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();
}

};
//用队列实现栈

“`

0 赞同 0 条回复

秋山丽奈普通 2024年11月25日下午7:39

实现思路：在入队列时使用两个队列处理，确保当前元素处在队列第一个位置中

class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;

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

    public void push(int x) {
        this.queue2.offer(x);

        // 将 queue1中元素 放入 queue2 使得 当前元素 在queue1中的第一位 
        while(!this.queue1.isEmpty()){
            this.queue2.offer(this.queue1.poll());
        }

        while(!this.queue2.isEmpty()){
            this.queue1.offer(this.queue2.poll());
        }


    }

    public int pop() {

        return this.queue1.poll();

    }

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

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

0 赞同 0 条回复

Pendulumpal 普通 2024年11月25日下午4:43

保持q2有着最后一个到来的元素

“`c++
class MyStack {
public:
queueq1;
queueq2;
MyStack() {

}

void push(int x) {
    if(q2.size()==1){
        q1.push(q2.front());
        q2.pop();
        q2.push(x);
    }else{
        q1.push(x);
    }
}

int pop() {
    int res=-1;
    if(q2.size()==1){
        res=q2.front();
        q2.pop();
    }else{
        while(q1.size()){
            q2.push(q1.front());
            q1.pop();
        }
        while(q2.size()>1){
            q1.push(q2.front());
            q2.pop();
        }
        if(q2.size()==1){
            res=q2.front();
            q2.pop();
        }
    }
    return res;
}

int top() {
    int res=-1;
    if(q2.size()==1){
        res=q2.front();
    }else{
        while(q1.size()){
            q2.push(q1.front());
            q1.pop();
        }
        while(q2.size()>1){
            q1.push(q2.front());
            q2.pop();
        }
        if(q2.size()==1){
            res=q2.front();
        }
    }
    return res;
}

bool empty() {
    return !(q1.size()||q2.size());
}

};

“`

0 赞同 0 条回复

无言永久会员 2024年11月25日下午12:52

class MyStack {
public:
    queue<int> que1;
    queue<int> que2;
    MyStack() {

    }

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

    int pop() { 
        int ans = que1.back();
        while(que1.size() > 1) {
            que2.push(que1.front());
            que1.pop();
        }
        if(que1.size() == 1) {
            que1.pop();
        }
        while(!que2.empty()) {
            que1.push(que2.front());
            que2.pop();
        }
        return ans;
    }

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

    bool empty() {
        return que1.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)  其余是O(1)
空间复杂度: O(N)

0 赞同 0 条回复

zing 普通 2024年11月25日下午12:04

注意其中为了泛化而做的一些“额外”操作

class MyStack:

    def __init__(self):
        # 声明两个队列
        self.queue1 = collections.deque()
        self.queue2 = collections.deque()

    def push(self, x: int) -> None:
    # 入栈操作时，首先将元素入队到 queue1 ，然后将 queue1 的全部元素依次出队并入队到 queue2 ，此时queue2 的前端的元素即为新入栈的元素，再将 queue1 和 queue2 互换，则 queue1 的元素即为栈内的元素，queue1 的前端和后端分别对应栈顶和栈底。
    # 输入的新的元素是栈顶，应该先输出，所以应该放在队头，所以要成为队列最先输入的元素，所以要将原来的队列输入输出到新队列

        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1

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

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

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.queue1   

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

0 赞同 0 条回复

黑键〰普通 2024年11月25日上午11:30

var MyStack = function() {
    this.queue1 = []
    this.queue2 = []
};

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

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    // 辅助queue把原来的queue值逐个存入，留下最后一个值
    while(this.queue1.length > 1) {
        this.queue2.push(this.queue1.shift())
    }
    let res = this.queue1.shift()
    // 重新把值存回来原来的queue
    while(this.queue2.length) {
        this.queue1.push(this.queue2.shift())
    }
    return res
};

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

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.queue1.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 条回复

Poetry and distance 永久会员 2024年11月25日上午1:36

思路：利用二个队列实现栈的后进先出功能，主要是一个队列放最后的原始到一个队列的第一个作为先出，然后将后面的逆序放入队列中，实现后进先出
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);
        if(!queue1.isEmpty())
            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(n)
空间复杂度:O(n)

0 赞同 0 条回复

Xiang. 永久会员 2024年11月25日上午12:22

思路：始终将定义的A队列作为要模拟的栈，入栈时以B作为中转处，先将元素入队B，再将A中的元素依次出队并加入到B中，最后将A、B的引用替换。
class MyStack {
    Queue<Integer> A,B;
    public MyStack() {
        A=new LinkedList<Integer>();
        B=new LinkedList<Integer>();
    }

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

0 赞同 0 条回复

Jerry 普通 2024年11月24日下午11:14

class MyStack {
public:
    queue<int> writeque;
    queue<int> readque;
    MyStack() {

    }

    void push(int x) {
        if(readque.empty()){
            readque.push(x);
        }
        else if(!readque.empty()){
            writeque.push(x);
            while(!readque.empty()){
                int tmp = readque.front();
                writeque.push(tmp);
                readque.pop();
            }
            while(!writeque.empty()){
                int tmp = writeque.front();
                readque.push(tmp);
                writeque.pop();
            }
        }
    }

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

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

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

思路：write队列作为临时中转站，负责将【后进】的元素排到队列第一个，进而达到【先出】的效果。再把write队列中所有元素腾到read队列中即可。

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月24日下午10:20

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

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

        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }

        Queue<Integer> tmp = queue2;
        queue2 = queue1;
        queue1 = tmp;

    }

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

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

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

核心思想：新的值单独入一个队列，再把另一个队列的值挪过来，实现逆序输出

0 赞同 0 条回复

苯庸普通 2024年11月24日下午9:45

class MyStack {
Queue q1;
Queue q2;

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

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

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

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

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

}
时间：O（1）
空间：O（n）

0 赞同 0 条回复

🍊 普通 2024年11月24日下午4:59

两个队列
class MyStack {
Queue queue1;
Queue 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();
}

}

0 赞同 0 条回复

月下足迹普通 2024年11月24日下午2:21

//pop操作就是留下最后一个队列元素出列
class MyStack {

    Queue<Integer> queue1,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 topElement = queue1.poll();
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;

        return topElement;
    }

    public int top() {
        while (queue1.size() > 1) {
            queue2.offer(queue1.poll());
        }
        int topElement = queue1.peek();
        queue2.offer(queue1.poll());

        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;

        return topElement;
    }

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

0 赞同 0 条回复

youngsir 普通 2024年11月24日上午10:19

打卡
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 result = q1.front();
    q1.pop();
    q1 = q2;
    while(!q2.empty()){
        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 条回复

Tom Yuan 普通 2024年11月24日上午6:53

用两个队列，一个是缓存原有的数据，另一个是handle新入的数据
push时将新数据放入辅助队列，此时他在队列头部，然后将原有数据依次放入辅助队列，最后将主队列和辅助队列交换
pop时因为新数据在主队列最左边，根据LIFO原则他应该最先出来，所以popleft。

from collections import deque
class MyStack:

    def __init__(self):
        self.queue1 = deque() # main
        self.queue2 = deque() # sub

    def push(self, x: int) -> None:
        # always keep sub empty as a buffer
        # to make sure when push it can be at the top.
        self.queue2.append(x)
        while len(self.queue1):
            self.queue2.append(self.queue1.popleft())
        self.queue2, self.queue1 = self.queue1, self.queue2

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

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

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

time O(n) space O(n)

0 赞同 0 条回复

jaron 普通 2024年11月23日下午10:50

class MyStack {

    public Queue<Integer> 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();
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月23日下午10:49

class MyStack {
public:
    queue<int> q;
    MyStack() {
    }

    void push(int x) {
        int l = q.size();
        q.push(x);
        while(l != 0){
            int temp = q.front();
            q.pop();
            q.push(temp);
            l--;
        }
    }

    int pop() {
        int result = q.front();
        q.pop();
        return result;
    }

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

    bool empty() {
        return q.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)，空间复杂度O(N)。

0 赞同 0 条回复

Kisara 普通 2024年11月23日下午10:31

将队列想象成一个环，要出栈就出队再入队留下原来的第一个元素，这样队头就是栈顶，但是只能o（n）

class MyStack {
    Queue<Integer> queue;

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

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

    public int pop() {
        int size=queue.size();
        while(size--!=1){
            queue.add(queue.remove());
        }
        return queue.remove();
    }

    public int top() {
       int size=queue.size();
        while(size--!=1){
            queue.add(queue.remove());
        }
        int top=queue.peek();
        queue.add(queue.remove());
        return top;
    }

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

时间复杂度O(N) 空间复杂度O(N)

0 赞同 0 条回复

lQl 永久会员 2024年11月23日下午10:25

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

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

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

    public int pop() {
        while(q1.size()>1){
            q2.offer(q1.poll());
        }
        int pop = q1.poll();
        while(q2.size()>0){
            q1.offer(q2.poll());
        }
        return pop;
    }

    public int top() {
        while(q1.size()>1){
            q2.offer(q1.poll());
        }
        int top = q1.peek();
        q2.offer(q1.poll());
        while(q2.size()>0){
            q1.offer(q2.poll());
        }
        return top;
    }

    public boolean empty() {
        if(q1.size()<=0){
            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();
 * boolean param_4 = obj.empty();
 */

0 赞同 0 条回复

Renasc 普通 2024年11月23日下午9:29

class MyStack {
    Queue<Integer> in;
    Queue<Integer> out;

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

    public void push(int x) {
        // in表示新入的元素
        in.offer(x);
        // out表示之前存过的元素
        while (!out.isEmpty()) {
            in.offer(out.poll());  // 把之前存的元素再放到in里的新元素后面，就实现了栈
        }

        // 互换栈
        Queue<Integer> temp = out;
        out = in;
        in = temp;
    }

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

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

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

0 赞同 0 条回复

晓宇普通 2024年11月23日下午9:08

class MyStack {
private:
    list<int> listStack;
public:
    MyStack() {

    }

    void push(int x) {
        listStack.push_back(x);
    }

    int pop() {
        int x = listStack.back();
        listStack.pop_back();
        return x;
    }

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

    bool empty() {
        return listStack.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 条回复

休一普通 2024年11月23日下午9:00

1.代码

class MyStack {
private:
    queue<int> q;
public:
    MyStack() {
        // 初始化空队列
    }

    void push(int x) {
        q.push(x);
        int size = q.size();
        // 将之前的元素重新入队，保持新元素在队头
        while (size > 1) {
            q.push(q.front());
            q.pop();
            size--;
        }
    }

    int pop() {
        int topElement = q.front();
        q.pop();
        return topElement;
    }

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

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

2.复杂度分析

时间复杂度：o(n),由于每次都必须将元素重新添加一遍；
空间复杂度：o(n)，使用了一个队列来模拟一个栈；

0 赞同 0 条回复

迢迢星野普通 2024年11月23日下午8:06

class MyStack {

    // 使用两个队列实现栈
    Deque<Integer> que1;
    Deque<Integer> que2;

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

    public void push(int x) {
        que1.addLast(x);
    }

    public int pop() {
        // que1 只留一个队尾元素，其余的元素依次入队列 que2 中
        int size = que1.size();
        size--;
        while(size-- > 0) {
            que2.addLast(que1.peekFirst());
            que1.pollFirst();
        }
        int res = que1.pollFirst();

        // 交换两个队列
        Deque<Integer> tmp = que1;
        que1 = que2;
        que2 = tmp;
        return res;
    }

    public int top() {
        return que1.peekLast();
    }

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

思路

题目要求使用两个队列实现栈，que1 用于添加元素，que2 用于删除元素。

构造函数

初始化两个队列。

push 方法

将元素添加至 que1 的末尾即可。
时间复杂度：O(1)，只是将元素添加至 que1 的末尾。
空间复杂度：O(n)，元素个数。

pop 方法

将 que1 中除最后一个元素外的其他元素逐一移动到 que2。
弹出 que1 的最后一个元素并返回，就是栈顶元素。
交换 que1 和 que2，确保 que1 始终用于添加元素，que2 用于删除元素。
时间复杂度：O(n)，需要将 que1 中除最后一个元素外的其他元素逐一移动到 que2。
空间复杂度：O(n)，元素个数。

top 方法

返回 que1 的最后一个元素，即栈顶元素。
时间复杂度：O(1)，只访问 que1 的最后一个元素。
空间复杂度：O(n)，元素个数。

empty 方法

检查 que1 是否为空，以判断栈是否为空。
时间复杂度：O(1)，只需要检查 que1 是否为空。
空间复杂度：O(n)，元素个数。

0 赞同 0 条回复

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

共以下 35 个回答

1.代码

2.复杂度分析

思路

构造函数

push 方法

pop 方法

top 方法

empty 方法

# 回答此问题取消回复

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

共以下 35 个回答

1.代码

2.复杂度分析

思路

构造函数

push 方法

pop 方法

top 方法

empty 方法

# 回答此问题 取消回复

# 回答此问题取消回复