谁仁普通 2023年9月5日下午4:11

#include
#include

using namespace std;

class Stack {
public:
// 判断栈是否为空
bool isEmpty() {
return top -1;
}

// 判断栈是否已满  
bool isFull() {  
    return top >= maxSize - 1;  
}

// 入栈  
void push(int data) {  
    if (isFull()) {  
        cout << "Error: stack is full!" << endl;  
        return;  
    }  
    top++;  
    stackArray[top] = data;  
}

// 出栈  
int pop() {  
    if (isEmpty()) {  
        cout << "Error: stack is empty!" << endl;  
        return -1;  
    }  
    int temp = stackArray[top];  
    top--;  
    return temp;  
}

// 获取栈顶元素  
int peek() {  
    if (isEmpty()) {  
        cout << "Error: stack is empty!" << endl;  
        return -1;  
    }  
    return stackArray[top];  
}

// 获取栈的大小  
int size() {  
    return top + 1;  
}

private:
int top; // 栈顶指针
int maxSize; // 栈的最大容量
int* stackArray; // 栈数组

// 构造函数  
Stack(int maxSize) {  
    this->maxSize = maxSize;  
    top = -1;  
    stackArray = new int[maxSize];  
}

// 析构函数  
~Stack() {  
    delete[] stackArray;  
}

};
时间复杂度O（1），空间复杂度o（n）

0 赞同 0 条回复

小火普通 2023年8月29日下午8:13

不太明白这个有啥意义

class MyStack {
private:
    queue<int> q1;
    queue<int> q2;//

public:
    MyStack() {
    }

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

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

    }

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

0 赞同 0 条回复

我一定要坚持打卡普通 2023年8月27日下午6:26

思路

解题思路

使用队列实现栈的时候，比较复杂的地方在于需要将新插入的数据变成栈的头部，在获取栈top或者出栈的时候，是队列最尾部的数据，所以可以在push 或者pop的时候做特殊处理，将最后一个数据变成队列头部数据方便出栈操作

225. 用队列实现栈 – 力扣（LeetCode）

这个题解写了两种方法，第一种是使用两个队列模拟栈的实现函数，在push的时候，直接先用辅助队列进行存储数据并将主队列数据插入到辅助队列中，直接将新插入的数据变成队列头部，然后将主队列和辅助队列功能互换实现新插入数据头部化

第二种方法是使用一个队列实现栈，本质是一样的，在插入数据后，将前边的数据先出对列，在入队列间接的将新插入的队列变成头部数据

代码随想录 (programmercarl.com)

卡尔哥提出的思想是使用辅助队列在出栈的时候，将最后一个入队列的元素前边的元素先放入到辅助队列中暂存，辅助队列只是起一个暂存的作用

解题方法1

解题方法【双队列法】

在push的时候用辅助队列重排序，顺序与栈内数据一致

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/implement-stack-using-queues/solutions/432204/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

卡尔哥提出了另一种双队列的方法，也是存储队列中的数据与栈内数据顺序一致

只是在push的时候，先将主队列数据清空全部存入到辅助队列中，然后将新插入数据插入到主队列中，再将暂存队列中的数据全部放入到主队列中

class MyStack {
    //q1作为主要的队列，其元素排列顺序和出栈顺序相同
    Queue<Integer> q1 = new ArrayDeque<>();
    //q2仅作为临时放置
    Queue<Integer> q2 = new ArrayDeque<>();

    public MyStack() {

    }
    //在加入元素时先将q1中的元素依次出栈压入q2，然后将新加入的元素压入q1，再将q2中的元素依次出栈压入q1
    public void push(int x) {
        while (q1.size() > 0) {
            q2.add(q1.poll());
        }
        q1.add(x);
        while (q2.size() > 0) {
            q1.add(q2.poll());
        }
    }

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

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

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

时间复杂度： $O(n)$

空间复杂度： $O(n)$

解题方法2

单个队列实现

一个是在push的时候，修改队列的顺序，另一个是在pop的时候修改队列的顺序本质是一样的，都是将新插入数据变成栈顶部数据

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

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

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

class MyStack {
    Queue<Integer> queue;

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

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

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

    public int top() {
        rePosition();
        int result = queue.poll();// 将最顶部数据弹出来，重新在放回队列的尾部，方便在pop的时候重新变成栈顶数据
        queue.add(result);
        return result;
    }

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

    public void rePosition(){
        int size = queue.size();
        size--;
        while(size-->0)
            queue.add(queue.poll());
    }
}

0 赞同 0 条回复

漂洋过海去见你永久会员 2023年8月27日下午4:29

#python题解
class MyStack(object):

def __init__(self):
    self.q1 = [] #出栈入栈均用q1
    self.q2 = [] #中转栈作为q2

def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    self.q1.append(x)

def pop(self):
    """
    :rtype: int
    """
    if len(self.q1) == 0:
        return None
    while len(self.q1) != 1:
        self.q2.append(self.q1.pop(0))
    #交换队列q1和q2，为了下一次的pop
    self.q1, self.q2 = self.q2, self.q1
    return self.q1.pop()

def top(self):
    """
    :rtype: int
    """
    if len(self.q1) == 0:
        return None
    while len(self.q1) != 1:
        self.q2.append(self.q1.pop(0))
    #交换队列q1和q2，为了下一次的pop
    self.q1, self.q2 = self.q2, self.q1
    return self.q2[0]




def empty(self):
    """
    :rtype: bool
    """
    if len(self.q2) == 0:
        return True
    return False

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月25日下午4:24

class MyStack:

def __init__(self):
    self.queue1 = collections.deque()
    self.queue2 = collections.deque()

def push(self, x: int) -> None:
    """先把元素压入2中"""
    self.queue2.append(x)
    """再将1中的元素压入2中"""
    while self.queue1:
        self.queue2.append(self.queue1.popleft())
    """再将1 2交换"""
    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:
    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()

时间复杂度：O(N+1)
空间复杂度：O(N+1)

0 赞同 0 条回复

Miracle· 普通 2023年8月24日下午7:16

class MyStack {
public:
MyStack() {

}

void push(int x) {
    resque.push(x);
    reverseque();
}

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

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

bool empty() {
    return resque.size() == 0;
}

private:
queue resque, tempque; // tempque用于临时存放要反转的元素

// 负责实现元素位置反转
void reverseque () {
    // 将除最后一个元素的所有元素全部插入到tempque中,并且在resque中删除对应的元素
    while (resque.size() != 1) {
        tempque.push(resque.front());
        resque.pop();
    }
    // 把tempque中的所有元素重新插入到resque中,完成反转
    while (!tempque.empty()) {
        resque.push(tempque.front());
        tempque.pop();
    }
}

};

0 赞同 0 条回复

mpweixin用户普通 2023年8月23日下午10:37

时间复杂度：入栈O(n)，其他O(1)，空间复杂度：O(n)

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

0 赞同 0 条回复

mpweixin用户普通 2023年8月23日下午1:11

//栈，先入后出；
//队列，先入先出；
//插入的复杂度为o(1);
//删除的复杂度为o(n);
//空间的复杂度为o(n);
class MyStack {
public:
queue queue1;
queue queue2;

MyStack() {
}

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

int pop() {
    int size = queue2.size();
    size--;
    while(size--){
        queue1.push(queue2.front());
        queue2.pop();
    }
    int tmp = queue2.front();

    queue2.pop();
    queue2=queue1;
    while(!queue1.empty()){
        queue1.pop();
    }
    return tmp;
}

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

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

};

0 赞同 0 条回复

sc_Yang 普通 2023年8月21日下午11:23

// 双队列实现法
// 单队列实现法
class MyStack {
public:
    queue<int> q;
    MyStack() {

    }

    void push(int x) {
        int n = q.size();
        q.push(x);
        for(int i=0; i<n; i++){
            q.push(q.front());
            q.pop();
        }
    }

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

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

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

0 赞同 0 条回复

mpweixin用户普通 2023年8月21日下午9:29

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

    }

    void push(int x) {//入栈 队列里面也是直接入
        q.push(x);
    }

    int pop() {//出栈 首先将前size-1个元素先出队后入队，此时第一个就是栈顶元素
        int size = q.size();
        size--;
        while(size --){
            int tmp = q.front();
            q.pop();
            q.push(tmp);
        }
        int res = q.front();
        q.pop();
        return res;

    }

    int top() {//栈顶元素 在队列里 就是队尾那个元素
        return q.back();
    }

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

0 赞同 0 条回复

小肸永久会员 2023年8月21日下午3:08

lass MyStack {
    //这个入栈时间复杂度O(1)，出栈时间复杂度O(N)。
    Queue<Integer> queue;
    Queue<Integer> tmp;
    public MyStack() {
        queue = new LinkedList<>();
        tmp = new LinkedList<>();
    }

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

    public int pop() {
        this.transfer();
        int res = queue.poll();
        Queue<Integer> t = tmp;
        tmp = queue;
        queue = t;
        return res;
    }

    public int top() {
        int res = this.pop();
        queue.offer(res);
        return res;
    }

    public boolean empty() {
        return queue.isEmpty();
    }
    private void transfer() {
        while (queue.size() > 1) {
            tmp.offer(queue.poll());
        }
    }
}

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月20日下午8:04

时间复杂度：入栈为O(n)，其余都是 O(1)
空间复杂度：O(n)
class MyStack {
public:
queue queue1;
MyStack() {

}

void push(int x) {
    queue1.push(x);
    int n=queue1.size();
    for(int i=1;i<n;i++){
        queue1.push(queue1.front());
        queue1.pop();
    }
}

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

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

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

};

0 赞同 0 条回复

Marc 普通 2023年8月19日下午10:38

class MyStack:

    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        n = len(self.queue)
        self.queue.append(x)
        for i in range(n):
            self.queue.append(self.queue.pop(0))

    def pop(self) -> int:
        return self.queue.pop(0)
    def top(self) -> int:
        return self.queue[0] 
    def empty(self) -> bool:
        return not self.queue

pop和top的时间O1，push On

0 赞同 0 条回复

QQiing 普通 2023年8月19日下午6:13


class MyStack {
public:
    queue queue1;
    queue queue2;
    MyStack() {

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

        while(!queue1.empty())
        {
            queue2.push(queue1.front());
            queue1.pop();
        }
        queue1 = queue2;
        while(!queue2.empty())
        {
            queue2.pop();
        }
    }
    
    int pop() {
        int result = queue1.front();
        queue1.pop();
        return result;
    }
    
    int top() {
        return queue1.front();
    }
    
    bool empty() {
        return queue1.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();
 */

push操作时间复杂度O(n)，空间复杂度O(1)
pop操作时间复杂度O(1)，空间复杂度O(1)
top操作时间复杂度O(1)，空间复杂度O(1)
empty操作时间复杂度O(n)，空间复杂度O(1)

0 赞同 0 条回复

天亮说晚安普通 2023年8月19日下午4:40

思路：两个队列，用另一个队列获取最后一个元素即可
时间复杂度O(N)，空间复杂度O(N)

class MyStack {

    Queue<Integer> A;
    Queue<Integer> B;

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

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

    public int pop() {
        while(A.size()>1){
            B.offer(A.poll()); 
        }
        while(!B.isEmpty()){
            A.offer(B.poll());
        }
        return A.poll();
    }

    public int top() {
        int temp = 0;
        while(!A.isEmpty()){
            temp = A.poll();
            B.offer(temp);
        }
        while(!B.isEmpty()){
            A.offer(B.poll());
        }
        return temp;
    }

    public boolean empty() {
        if(A.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月18日上午10:04

后来想了想确实一个队列就能实现
两个队列反而麻烦了

class MyStack {


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

    //进栈
    public void push(int x) {
        if(!queueA.isEmpty())
            queueA.offer(x);
        else if(!queueB.isEmpty())
            queueB.offer(x);
        else
            queueA.offer(x);
    }

    //出栈
    public int pop() {
        if(!queueA.isEmpty()) {
            while (queueA.size() > 1)
                queueB.offer(queueA.poll());
            return queueA.poll();
        } else if (!queueB.isEmpty()) {
            while (queueB.size()>1)
                queueA.offer(queueB.poll());
            return queueB.poll();
        }
        return -1;
    }

    int temp = -1;
    //得到栈顶元素
    public int top() {
        if(!queueA.isEmpty()) {
            while (queueA.size() > 1)
                queueB.offer(queueA.poll());
            temp = queueA.peek();
            queueB.offer(queueA.poll());
            return temp;    
        } else if (!queueB.isEmpty()) {
            while (queueB.size()>1)
                queueA.offer(queueB.poll());
            temp = queueB.peek();
            queueA.offer(queueB.poll());
            return temp;
        }
        return -1;
    }
    //判断栈是否为空
    public boolean empty() {
        return   queueB.isEmpty()&&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 条回复

海浪漂哇漂普通 2023年8月18日上午12:07

一个队列

class MyStack {
    Queue<Integer> queue;

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

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

Sheng 永久会员 2023年8月17日下午9:51

”’java
//两个队列模拟栈
import java.util.Queue;
import java.util.LinkedList;
class MyStack {
public Queue q1;
public Queue q2;

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

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

public int pop() {
    int elemnt = 0;
    if(!q1.empty()) {
        while(q1.size()!=1) {
            q2.add(q1.remove());
        }
        elemnt = q1.remove();

        if(!q2.empty()) {
            while(q2.empty()) {
                q1.add(q2.remove());
        }
        return element;
    }
    return -1;
}

public int top() {
    int elemnt = 0;
    if(!q1.empty()) {
        while(q1.size()!=1) {
            q2.add(q1.remove());
        }
        elemnt = q1.remove();
        q2.add(elemnt);
        if(!q2.empty()) {
            while(q2.empty) {
                q1.add(q2.remove());
        }
        return element;
    }
    return -1;
}

public boolean empty() {
    return (q1.size()==0);
}

}

0 赞同 0 条回复

Joel 普通 2023年8月17日下午2:34

时间O(n) 空间O(n)

class MyStack:

    def __init__(self):
        self.A, self.B = [], []

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

    def pop(self) -> int:
        while len(self.A) > 1:
            self.B.append(self.A.pop(0))
        temp = self.A.pop(0)
        for i in self.B:
            self.A.append(i)
        self.B = []
        return temp

    def top(self) -> int:
        while len(self.A) > 1:
            self.B.append(self.A.pop(0))
        temp = self.A.pop(0)
        self.B.append(temp)
        for i in self.B:
            self.A.append(i)
        self.B = []
        return temp

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



# 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 条回复

sincere 普通 2023年8月17日上午11:02

思路：q1 压入元素，压入时用变量 top 记录栈顶元素；pop() 时将 q1 元素移到 q2，直到 q1 剩1个元素时停止（在移动时用 top 记录最新的栈顶元素），此时该元素即为最新的栈顶元素，记录它并移除元素，然后交换 q1 q2 即可
复杂度：时间复杂度pop O(n)、其他O(1)；空间复杂度O(n)

class MyStack {
    private Queue q1 = new LinkedList<>();
    private Queue q2 = new LinkedList<>();
    private int top;


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

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

    public int pop() {
        int res;
        while (q1.size() > 1) {
            top = q1.remove();
            q2.add(top);
        }
        res = q1.remove();
        Queue tmp = q1;
        q1 = q2;
        q2 = tmp;
        return res;
    }

    public int top() {
        return top;
    }

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

0 赞同 0 条回复

晓宇普通 2023年8月17日上午8:12

class MyStack(object):

    def __init__(self):
        self._queue = collections.deque()

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        q = self._queue
        q.append(x)
        for _ in range(len(q)-1):
            q.append(q.popleft())



    def pop(self):
        """
        :rtype: int
        """
        return self._queue.popleft()


    def top(self):
        """
        :rtype: int
        """
        if len(self._queue)==0:
            return None
        else:
            return self._queue[0]


    def empty(self):
        """
        :rtype: bool
        """
        return len(self._queue)==0

The key of this problem is that queue doesn’t have pop only has popleft. So we need to make the last push thing at first. Every time we push we need to get all of elements out.
Space: O(N)
Compute:O(N) 一

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月16日下午10:01

class MyStack {
private:
    queue<int> q1, q2;
public:
    MyStack() {

<pre><code>}

void push(int x) {
    if(q1.empty()){
        q2.push(x);
    }
    else if(q2.empty()){
        q1.push(x);
    }
}

int pop() {
    // 元素在q2
    if(q1.empty()){
        while(q2.size() > 1){
            q1.push(q2.front());
            q2.pop();
        }
        int val = q2.front();
        q2.pop();
        return val;
    }
    else{
        while(q1.size() > 1){
            q2.push(q1.front());
            q1.pop();
        }
        int val = q1.front();
        q1.pop();
        return val;
    }
} 

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

bool empty() {
    return q1.empty() && q2.empty();
}
</code></pre>

};

0 赞同 0 条回复

逸兴遄飞普通 2023年8月16日上午10:32

空间复杂度：O(N),
时间复杂度：入栈O(N)，出栈、栈顶、空栈操作都是O(1)。

class MyStack {
    // 创建两个队列，1用于存储栈内的元素，2用作入栈操作的辅助队列
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    // 初始化栈函数
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }

    // 入栈操作，先将元素入队到2中，然后将1的全部元素依次出队并入队到2中
    public void push(int x) {
        queue2.offer(x);
        // 1=>2，此时2的前端元素即为新入栈的元素
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        // 此后将1和2互换，那么1中的元素即为栈内元素
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    // 出栈操作即为将队列1的元素依次输出并在队列中删除
    public int pop() {
        return queue1.poll();
    }

    // top指针即为将队列1的元素依次输出但不进行删除
    public int top() {
        return queue1.peek();
    }

    // 空栈指针即为查询队列1是否为空
    public boolean empty() {
        return queue1.isEmpty();
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月15日下午11:56

1、一个进去之后，前面的都出队插入队尾

class MyStack {
    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() {
        if(queue.size() == 0){
            return true;
        }
        return false;
    }
}

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月15日下午11:28

class MyStack {

    List<Integer> in;
    List<Integer> out;
    public MyStack() {
        in = new ArrayList<>();
        out = new ArrayList<>();
    }

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

    public int pop() {
        while (in.size() > 1){
            out.add(in.remove(0));
        }
        Integer remove = in.remove(0);
        while (!out.isEmpty()){
            in.add(out.remove(0));
        }
        return remove;
    }

    public int top() {
        while (in.size() > 1){
            out.add(in.remove(0));
        }
        Integer remove = in.remove(0);
        while (!out.isEmpty()){
            in.add(out.remove(0));
        }
        in.add(remove);
        return remove;

    }

    public boolean empty() {
        if(in.isEmpty() && out.isEmpty()){
            return true;
        }else {
            return false;
        }
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        System.out.println(myStack.top());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());
    }
}

添加元素在一个队列，弹出元素时，先将前面元素放入另一个队列保存，弹出完毕，将另一个队列中的元素返回第一个队列。

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月15日下午9:46

始终保持队列的第一个元素是待出栈的元素

class MyStack {
    private Queue<Integer> queue; 

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

    public void push(int x) {
        int num = queue.size();
        queue.add(x);
        for (int i = 0; i < num; i++) {
            queue.add(queue.remove());
        }
    }

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

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

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

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月15日下午9:18

“`python
from collections import deque
class MyStack:

<

pre>def init(self): self.inq = deque() self.outq = deque()


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

    self.inq.append(x)
def pop(self) -> int:

    while len(self.inq)>1:

        self.outq.append(self.inq.popleft())

    tmp = self.inq.popleft()

    self.inq,self.outq = self.outq,self.inq #一开始一直想的是挪元素，看了代码才发现挪来挪去其实值的顺序没变化的，可以直接赋值
return tmp

def top(self) -> int:

    #先获取到顶元素，此时inq为空

    while len(self.inq)>1:

        self.outq.append(self.inq.popleft())

    tmp = self.inq.popleft()

    #然后将这个元素再入栈

    self.outq.append(tmp)

    #最后再互换两个队列

    self.outq, self.inq = self.inq, self.outq
return tmp

def empty(self) -> bool:

    if len(self.inq)0:

        return True

    else:

        return False

```python

0 赞同 0 条回复

木木普通 2023年8月15日下午6:29

push: 時間複雜度 O(n), 空間複雜度 O(n)
pop, top, empty: 時間複雜度 O(1), 空間複雜度 O(1)


class MyStack {
public:
    MyStack() {

    }
    queue q1, q2;
    void push(int x) {
      q2.push(x);

      while (!q1.empty()) {
        q2.push(q1.front());
        q1.pop();
      }
      queue q = q1;
      q1 = q2;
      q2 = q;
    }
    
    int pop() {
      int res;
      if (!q1.empty()) {
        res = q1.front();
        q1.pop();
      }
      return res;
    }
    
    int top() {
      return q1.front();
    }
    
    bool empty() {
      return q1.empty();
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月15日下午4:05

// 两个队列
class MyStack {
public:
    MyStack() {

<pre><code>}

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

int pop() {
    if (!q1.empty()) {
        int val = q1.front();
        q1.pop();
        return val;
    }

    if (!q2.empty()) {
        int val = q2.front();
        q2.pop();
        return val;
    }
    return -1;
}

int top() {
    if (!q1.empty()) {
        int val = q1.front();
        return val;
    }

    if (!q2.empty()) {
        int val = q2.front();
        return val;
    }
    return -1;
}

bool empty() {
    return q1.empty() && q2.empty();
}
</code></pre>

private:
    std::queue<int> q1;
    std::queue<int> q2;
};

// 一个队列
class MyStack {
public:
    MyStack() {

<pre><code>}

void push(int x) {
    int size = que.size();
    que.push(x);
    while (size--) {
        que.push(que.front());
        que.pop();
    }
}

int pop() {
    int val = que.front();
    que.pop();
    return val;
}

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

bool empty() {
    return que.empty();
}
</code></pre>

private:
    std::queue<int> que;
};

0 赞同 0 条回复

c 普通 2023年8月15日下午3:45

//用两个队列实现栈
class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

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

    public void push(int x) {
        queue2.add(x);
        while (!queue1.isEmpty()){
            queue2.add(queue1.poll());
        }
        while (!queue2.isEmpty()){
            queue1.add(queue2.poll());
        }
    }

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

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

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

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

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

    public void push(int x) {
        int size = queue.size();
        queue.add(x);
        while (size!=0){
            queue.add(queue.poll());
            size--;
        }
    }

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

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

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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月15日下午3:16

//每次入队一个元素都需要将这个元素放在队头
// 时间O(n),空间O(n)
class MyStack {
    queue<int> Que1;
    queue<int> Que2;
public:
    MyStack() {

    }

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

    int pop() {
        int val = Que2.front();
        Que2.pop();
        return val;
    }

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

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

// 一个队列实现，每次都将元素置前面
// 时间O(n)，空间O(1)
class MyStack {
    queue<int> Que;
public:
    MyStack() {

    }

    void push(int x) {
        int n = Que.size();
        Que.push(x);
        while(n--)
        {
            Que.push(Que.front());
            Que.pop();
        }
    }

    int pop() {
        int val = Que.front();
        Que.pop();
        return val;
    }

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

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

0 赞同 0 条回复

【数据结构专题】LeetCode 225. 用队列实现栈

共以下 31 个回答

思路

解题方法1

解题方法2

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. 用队列实现栈

共以下 31 个回答

思路

解题方法1

解题方法2

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

# 回答此问题 取消回复

# 回答此问题取消回复