【基本数据结构】LeetCode 225. 用队列实现栈-跟着帅地玩副业，开拓第二曲线PlayOffer

mpweixin用户永久会员 2023年8月12日下午3:41

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

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

    public void push(int x) {
        //新入元素先放到q2
        q2.offer(x);
        //将q1中元素全部移到q2中，这样后入元素出现在队头
        while(!q1.isEmpty()){
            q2.offer(q1.poll());
        }
        //再将q2中的元素全部移回q1，便于下一次入栈
        while(!q2.isEmpty()){
            q1.offer(q2.poll());
        }
    }

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

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

    public boolean empty() {
        if(q1.isEmpty() && q2.isEmpty()) 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();
 */

0 赞同 0 条回复

山川湖海普通 2023年8月3日下午8:23

用队列实现栈 cpp

class MyStack {
public:

    queue<int> q1;
    queue<int> q2;

    MyStack() {

    }

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

    int pop() {
        int temp;
        while (q1.size() > 1) {
            temp = q1.front();
            q2.push(temp);
            q1.pop();
        }
        temp = q1.front();
        q1.pop();
        while (!q2.empty()) {
            int temp2 = q2.front();
            q2.pop();
            q1.push(temp2);
        }
        return temp;
    }

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

hi 普通 2023年7月23日下午11:01

同样加入一个缓存队列，弹出操作时，栈弹出的是最前的，而队列弹出的是最后的，所以需要先找到栈中需要弹出的这个数，把队列中之前的元素先保存在另一个队列中，只留下该需要弹出的数
top操作与pop操作类似，只是需要最后把删除的数重新加到队列中

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

    }

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

    int pop() {
        while(q.size() > 1)
        {
            c.push(q.front());
            q.pop();
        }
        int x = q.front();
        q.pop();
        while(c.size())
        {
            q.push(c.front());
            c.pop();
        }
        return x;
    }

    int top() {
        while(q.size() > 1)
        {
            c.push(q.front());
            q.pop();
        }
        int x = q.front();
        q.pop();
        while(c.size())
        {
            q.push(c.front());
            c.pop();
        }
        q.push(x);
        return x;
    }


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

Edenms-u 普通 2023年7月23日下午6:48

#define LEN 10

typedef struct {
    int* num;
    int head;
    int tail;
    int k;
} Queue;

typedef struct {
    Queue *a, *b;
} MyStack;

Queue* queueInit(int k){
    Queue* obj = (Queue*)malloc(sizeof(Queue));
    obj->num = (int*)malloc(sizeof(int) * k);
    obj->head = obj->tail = -1;
    obj->k = LEN;
    return obj;
}

void enQueue(Queue* obj, int x){
    if(obj->head == -1)
        obj->head = 0;
    obj->tail = (obj->tail + 1) % obj->k;
    obj->num[obj->tail] = x;
}

int deQueue(Queue* obj){
    int x = obj->num[obj->head];
    if(obj->head == obj->tail){
        obj->head = obj->tail = -1;
    }else{
        obj->head = (obj->head + 1) % obj->k;
    }
    return x;
}

int qEmpty(Queue* obj){
    return obj->head == -1;
}

MyStack* myStackCreate() {
    MyStack* obj= (MyStack*)malloc(sizeof(MyStack));
    obj->a = queueInit(LEN);
    obj->b = queueInit(LEN);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    if(qEmpty(obj->a)){
        enQueue(obj->b, x);
    }else{
        enQueue(obj->a, x);
    }
}

int myStackPop(MyStack* obj) {
    if(qEmpty(obj->a)){
        while(obj->b->head != obj->b->tail){
            enQueue(obj->a, deQueue(obj->b));
        }
        return deQueue(obj->b);
    }
    while(obj->a->head != obj->a->tail){
        enQueue(obj->b, deQueue(obj->a));
    }
    return deQueue(obj->a);
}

int myStackTop(MyStack* obj) {
    return qEmpty(obj->a) ? obj->b->num[obj->b->tail] : obj->a->num[obj->a->tail];
}

bool myStackEmpty(MyStack* obj) {
    if(obj->a->tail == -1 && obj->b->tail == -1)
        return true;
    return false;
}

void myStackFree(MyStack* obj) {
    free(obj->a->num);
    free(obj->b->num);
    obj->a->num = obj->b->num = NULL;
    free(obj->a);
    free(obj->b);
    obj->a = obj->b = NULL;
    free(obj);
    obj = NULL;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/
c写起来好复杂，哭死

0 赞同 0 条回复

今天没时间刷题普通 2023年7月23日下午2:18

入栈时间On，空间On
出栈O1
class MyStack {
public:
    queue<int> inQueue;
    queue<int> outQueue;

    MyStack() {

    }

    int pop() {
        int value = outQueue.front();
        outQueue.pop();
        return value;
    }

    void push(int x) {
        inQueue.push(x);
        while(!outQueue.empty())
        {
            inQueue.push(pop());
        }
        swap(inQueue, outQueue);
    }

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

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

0 赞同 0 条回复

wowo 普通 2023年7月23日上午12:27

用辅助队列完成入栈操作，队列A保存栈中的元素，新元素入栈时，将新元素放入空队列B，再将队列A中的元素依次出栈存入队列B，交换队列B和队列A，此时队列A中的元素按照从栈顶到栈底的顺序排列。时间复杂度O(n)，空间复杂度O(n)。
其他操作时间复杂度O(1)

class MyStack:

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


    def push(self, x: int) -> None:
        self.B.append(x)
        while self.A:
            ele = self.A.pop(0)
            self.B.append(ele)

        self.A = self.B
        self.B = []


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


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


    def empty(self) -> bool:
        if self.A: return False

        return True

0 赞同 0 条回复

新禾普通 2023年7月16日下午5:32

// queue
1

用于存储栈内的元素，queue2\textit{queue}_2queue
2

作为入栈操作的辅助队列。

入栈操作时，首先将元素入队到 queue2\textit{queue}_2queue
2

，然后将 queue1\textit{queue}_1queue
1

的全部元素依次出队并入队到 queue2\textit{queue}_2queue
2

，此时 queue2\textit{queue}_2queue
2

的前端的元素即为新入栈的元素，再将 queue1\textit{queue}_1queue
1

和 queue2\textit{queue}_2queue
2

// 空间复杂度on 时间复杂度入队on 其他都是o1
class MyStack {
Queue Qqueue1;
Queue Qqueue2;

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

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

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

public int top() {
    return Qqueue1.peek();

}

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

}

0 赞同 0 条回复

朱志刚普通 2023年7月15日下午9:42

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

    }

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

    }

    int pop() {
        int temp= que1.back();
        while(!que1.empty()){
            if(que1.front() != temp){
                que2.push(que1.front());
                que1.pop();
            }
            else{
                que1.pop();
            }
        }
        swap(que1,que2);
        return temp;

    }

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

    }

    bool empty() {
        return que1.empty();

    }
};

执行用时：
4 ms

0 赞同 0 条回复

ppopp 普通 2023年7月14日下午11:57

/*
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
*/

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 r = q1.front();
    q1.pop();
    return r;
}

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

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

Marshan 普通 2023年7月14日上午11:03

//击败100%,95%
class MyStack {
public:
    MyStack() {

    }

    void push(int x) {
        if(select == 1){
            queue1.push(x);
        }
        else if(select == 2){
            queue2.push(x);
        }
    }

    int pop() {
        int res;
        if(select == 1){
            while(queue1.size() > 1){
                queue2.push(queue1.front());
                queue1.pop();
            }
            res = queue1.front();
            queue1.pop();
            select = 2;
        }
        else if(select == 2){
            while(queue2.size() > 1){
                queue1.push(queue2.front());
                queue2.pop();
            }
            res = queue2.front();
            queue2.pop();
            select = 1;
        }
        return res;
    }

    int top() {
        int res;
        if(select == 1){
            while(queue1.size() > 1){
                queue2.push(queue1.front());
                queue1.pop();
            }
            res = queue1.front();
            queue2.push(queue1.front());
            queue1.pop();
            select = 2;

        }
        else if(select == 2){
            while(queue2.size() > 1){
                queue1.push(queue2.front());
                queue2.pop();
            }
            res = queue2.front();
            queue1.push(queue2.front());
            queue2.pop();
            select = 1;
        }
        return res;
    }

    bool empty() {
        return (queue1.empty() && queue2.empty());
    }
private:
    queue<int> queue1;
    queue<int> queue2;
    int select = 1;
};

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月13日下午9:54

class MyStack {
private:
queue q;

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

}

/** Push element x onto stack. */
void push(int x) {
    // 反转队列，将新元素插到队头

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

/** Removes the element on top of the stack and returns that element. */
int pop() {
    int popEle = q.front();
    q.pop();

    return popEle;
}

/** Get the top element. */
int top() {
    return q.front();
}

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

};

0 赞同 0 条回复

mpweixin用户普通 2023年7月13日下午2:08

//直接转换即可
class MyStack {
public:
    MyStack() {

    }

    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() {
        return q1.front();
    }

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

/**
 * 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年7月13日上午9:23

class MyStack {

public static Queue<Integer> q1,q2;

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

public void push(int x) {
    //先将x入q2，再将q1的其他元素入q2
    q2.add(x);
    while(!q1.isEmpty()) {
        q2.add(q1.poll());
    }
    //将q1队列与q2队列交换
    Queue<Integer> temp = new LinkedList<>();
    temp = q1;
    q1 = q2;
    q2 = temp;
}

public int pop() {
    //直接从q1弹出元素即可
    return q1.poll();
}

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

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

}

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月12日下午10:16

class MyStack {

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

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

    public void push(int x) {
        // 先将主队列内容导入辅助队列，之后将入栈元素放在主队列队头
        // 再将辅助队列内容，依次添加进主队列
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        // queue1为空了，作为辅助队列
        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 条回复

#00456B 普通 2023年7月12日下午8:35

两个队列实现：
class MyStack {
public:
    //用两个stack来完成
    //inQue主要用来存放数据，outQue作为pop过程中的中介
    queue<int> inQue,outQue;
    MyStack() {

    }

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

    int pop() {
        int stkTop = inQue.back();//记录栈顶的元素
        while(!inQue.empty()){
            if(inQue.front() != stkTop){
                outQue.push(inQue.front());//把inQue都放到outQue中，完成模拟的栈顶的pop
                inQue.pop();
            }
            else{
                inQue.pop();
            }
        }
        swap(inQue,outQue);//交换回来
        return stkTop;
    }

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

    bool empty() {
        return inQue.empty();
    }
};
单个队列实现：
class MyStack {
public:
    //单个队列实现
    queue<int> que;
    MyStack() {

    }

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

    int pop() {
        int stkTop = que.back();
        int size = que.size();
        size -= 1;
        //对模拟栈顶以外的元素都重新入队，所以次数为size-1
        while(size--){
            que.push(que.front());
            que.pop();
        }
        //当que.front() == stkTop时，弹出
        que.pop();
        return stkTop;
    }

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

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月12日下午5:38

//用一个队列做出栈
//另一个人做临时存储新来元素保持在出栈队列的头部就得用先把出栈队列所有元素放入临时存储队列再放新到出栈队列头
Queue out;
Queuein;
public MyStack() {
out = new LinkedList();
in = new LinkedList();
}

public void push(int x) { //放入
if(out.size()==0)
{
    out.add(x);
}else{
    while(out.size()!=0)
    {
        in.add(out.remove());
    }
   out.add(x);
   while(in.size()!=0)
   {
       out.add(in.remove());
   } 
}

}

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

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

public boolean empty() {
    if(out.size()!=0)
    {
        return false;
    }else
    {
        return true;
    }
}

}

0 赞同 0 条回复

momo 普通 2023年7月12日下午3:46

用队列实现栈

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

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

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

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

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

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

0 赞同 0 条回复

枫梓。普通 2023年7月12日上午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 r = q.front();
        q.pop();
        return r;
    }

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

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

入栈O(n) 其他都是O(1) 空间上O(n)

0 赞同 0 条回复

周小二普通 2023年7月11日下午11:55

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());
        }
        //交换A和B
        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 条回复

人生何处不青山普通 2023年7月11日下午11:04

TS,一直觉得这道题比另一个难理解

class MyStack {
    public q1: number[]
    public q2: number[]
    constructor() {
        this.q1 = []
        this.q2 = []
    }

    push(x: number): void {
        this.q2.push(x);
        while (this.q1.length) {
            this.q2.push(this.q1.shift());
        }
        [this.q1, this.q2] = [this.q2, this.q1];
    }

    pop(): number {
        return this.q1.shift();
    }

    top(): number {
        return this.q1[0];
    }

    empty(): boolean {
        return !this.q1.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 条回复

土豆芋泥包_ 普通 2023年7月11日下午10:19

代码

class MyStack {

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

    public void push(int x) {
        queue2.add(x);
        while(!queue1.isEmpty()){
            queue2.add(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 条回复

普通 2023年7月11日下午10:09

c++ 代码用双队列模拟栈
class MyStack {
queue inQueue,outQueue;
public:
MyStack() {
}

void push(int x)
 {
    inQueue.push(x);
}
int pop() 
{
  int value=inQueue.back();
  while(!inQueue.empty())
  {
    if(inQueue.front()!=value)
    {
       outQueue.push(inQueue.front());
       inQueue.pop();
    }
    else
    {
         inQueue.pop();
    }
  }
  while(!outQueue.empty())
  {
      inQueue.push(outQueue.front());
      outQueue.pop();
  }
    return value;
}
int top() 
{
    int v=inQueue.back();
   return v;
}
bool empty() 
{
    if(inQueue.empty())
    return true ;
    return false;
}

};
c++代码在之前的基础上做了些修改用单队列也可以实现
class MyStack {
queue inQueue,outQueue;
public:
MyStack() {
}

void push(int x)
 {
    inQueue.push(x);
}
int pop() 
{
  int value=inQueue.back();
  int l=inQueue.size();
    while(l>1)
    {
        inQueue.push(inQueue.front());
        inQueue.pop();
        l--;
    }
    inQueue.pop();
    return value;
}
int top() 
{
    int v=inQueue.back();
   return v;
}
bool empty() 
{
    if(inQueue.empty())
    return true ;
    return false;
}

};

0 赞同 0 条回复

艺普通 2023年7月11日下午9:57

“`c++
class MyStack {
public:
queue q;
MyStack() {

}

void push(int x) {

int s;
s=q.size();
q.push(x);
while(s–)//// 反转队列，将新元素插到队头
{
int t=q.front();
q.pop();
q.push(t);
}
}

int pop() {

int ans=q.front();
q.pop();
return ans;
}

int top() {

return q.front();
}

bool empty() {

return q.empty();
}
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月11日下午4:01

static class MyStack {

        // 每次都在in里面插入，出队等操作 插完了就swap就可以形成倒叙了
        // offer就是尾插，pop就是从头拿
        // 插入的时候一个一个的来 慢慢的保持栈的基本结构
        Queue<Integer> in;
        Queue<Integer> out;

        /** Initialize your data structure here. */
        public MyStack() {
            in = new LinkedList<Integer>();
            out = new LinkedList<Integer>();
        }

        /** Push element x onto stack. */
        public void push(int x) {
            in.offer(x);
            while (!out.isEmpty()) {
                out.offer(in.poll());
            }
            Queue<Integer> temp = in;
            in = out;
            out = temp;
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            return in.poll();
        }

        /** Get the top element. */
        public int top() {
            return in.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return in.isEmpty();
        }

    }

0 赞同 0 条回复

doordie. 普通 2023年7月11日下午3:13

用队列实现栈

这道题用两种队列可以实现，也可以用一种队列实现，但是其核心思想是一样的
那就是让队列进行反转，先进去队列的让其最后进去
最后实现队头表示栈顶，队尾表示栈底

public class QStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;
    Queue<Integer> queue3;

    public QStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    // 入栈
    public void push(int value) {
        //入队q2
        queue2.offer(value);
        // 把q1的元素全入队q2
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        // q1和q2互换元素
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    // 一个队列实现
    public void push2(int value) {
        int n = queue3.size();
        queue3.offer(value);
        for (int i = 0; i < n; ++i){
            queue3.offer(queue3.poll());
        }
    }
    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 条回复

小季同学普通 2023年7月11日下午1:37

stack2是存放新入对的数组，再将队列1中的数据压入2中，交换1 和 2 就可以实现一个栈的push操作

class MyStack {
    private queue1: number[] = []
    private queue2: number[] = []
    constructor() {
    }

    push(x: number): void {
        // 每次将新入队的加入2中，然后依次将1加入进去，在交换队列
        this.queue2.push(x);
        while(this.queue1.length) {
            this.queue2.push(this.queue1.shift())
        }
        // 交换队列
        let temp = this.queue1
        this.queue1 = this.queue2
        this.queue2 = temp
    }

    pop(): number {
        return this.queue1.shift();
    }

    top(): number {
        return this.queue1[0];
    }

    empty(): boolean {
        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 条回复

片言莫语普通 2023年7月11日上午10:22

class MyStack {  // 定义一个MyStack类
   Queue<Integer> queue;  //在类里声明一个队列，用于模拟栈的操作 

    public MyStack() {  // 初始化构造方法
        queue = new LinkedList<>(); // 在构造方法中实例化队列，选择用LinkedList实现 
    }

    public void push(int x) {   //定义push方法(向栈中插入一项)，输入一个整数x
        queue.offer(x);   // 首先将要插入的元素添加到队列的末尾
        //然后将队列的前面元素重新插入到末尾，模拟栈的后进先出特性
        for(int i = 1;i<queue.size();i++){  //遍历队列，注意这里从1开始是因为我们已经插入了一个新元素
            queue.offer(queue.poll());  //将队列头部元素取出并放置到队列尾部
        }
    }

    public int pop() {   //定义一个pop操作(移除栈顶的对象)
        return queue.poll();   // 直接返回并移除队列头部元素，即最后插入的元素
    }

    public int top() {   //定义一个top操作(获取栈顶对象，但不移除它)
        return queue.peek();  // 直接返回队列头部元素，而不移除它
    }

    public boolean empty() {  //定义一个判断是否为空的操作
        return queue.isEmpty();  // 如果队列为空，则栈也为空，返回true，否则返回false
    }
}

0 赞同 0 条回复

Terence💧 普通 2023年7月10日下午11:51

type MyStack struct {
    mainQueue []int
    tempQueue []int
}


func Constructor() MyStack {
    return MyStack{}
}


func (this *MyStack) Push(x int)  {
    this.tempQueue = append(this.tempQueue, x)
    for len(this.mainQueue) > 0 {
        this.tempQueue = append(this.tempQueue, this.mainQueue[0])
        this.mainQueue = this.mainQueue[1:]
    }
    this.tempQueue, this.mainQueue = this.mainQueue, this.tempQueue
}


func (this *MyStack) Pop() int {
    val := this.mainQueue[0]
    this.mainQueue = this.mainQueue[1:]
    return val
}


func (this *MyStack) Top() int {
    return this.mainQueue[0]
}


func (this *MyStack) Empty() bool {
    return len(this.mainQueue) == 0
}


/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

数组队尾为栈头，辅助数组负责存放历史数据

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日下午11:48

class MyStack {

     private Queue<Integer> a;//输入队列
        private Queue<Integer> b;//输出队列

    public MyStack() {
       a = new LinkedList<>();
       b = new LinkedList<>();

    }

    public void push(int x) {
        a.offer(x);
        //将b队列中的元素全部转给a队列
        while(!b.isEmpty())a.offer(b.poll());
        //交换a和b，使得a队列没有在push（）的时候始终为空队列
        Queue temp = a;
        a = b;
        b = temp;
    }

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

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

    public boolean empty() {
        return b.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年7月10日下午11:24

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

class MyStack {

    // queue1 栈，队头为栈顶，队尾为栈底
    // queue2 辅助栈，入栈时先将新元素置队头，在将栈里的元素依次入队
    LinkedList<Integer> queue1, queue2;

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

    }

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

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

    }

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

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

0 赞同 0 条回复

CKX 普通 2023年7月10日下午11:20

type MyStack struct {
    queue1, queue2 []int
}


func Constructor() MyStack {
    return MyStack{}
}


func (this *MyStack) Push(x int) {
    //主队列中有元素,将主队列元素放入辅助队列中
    for len(this.queue1) > 0 {
        this.queue2 = append(this.queue2, this.queue1[0])
        this.queue1 = this.queue1[1:]
    }
    //新元素放入主队列
    this.queue1 = append(this.queue1, x)

    ////辅助队列中有元素,将辅助队列元素放入主队列中
    for len(this.queue2) > 0 {
        this.queue1 = append(this.queue1, this.queue2[0])
        this.queue2 = this.queue2[1:]
    }
}


func (this *MyStack) Pop() int {
    value := this.queue1[0]
    this.queue1 = this.queue1[1:]
    return value
}


func (this *MyStack) Top() int {
    return this.queue1[0]
}


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

}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月10日下午10:54

Day4：下面是代码

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

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

June 普通 2023年7月10日下午10:48

class MyStack {

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

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

    public void push(int x) {
        q2.add(x);
        //把 q1 的全部出列并入列q2
        while(!q1.isEmpty())
        {
            int tmp = q1.peek();
            q1.remove();
            q2.add(tmp);
        }
        //交换 q1 和 q2
        Queue<Integer> qt = q1;
        q1 = q2;
        q2 = qt;
    }

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

Luminous 普通 2023年7月10日下午10:28

class MyStack {

    List<Integer> a;//主队列
    List<Integer> b;//辅助队列
    public MyStack() {
        a=new LinkedList<Integer>();
        b=new LinkedList<Integer>();
    }

    public void push(int x) {
        //1.将主队列中的数全部添加进辅助队列
        while(!a.isEmpty()){
            b.add(a.remove(0));
        }
        //2.将x添加进主队列
        a.add(x);
        //3.将辅助队列只的数添加进辅助队列中
        while(!b.isEmpty()){
            a.add(b.remove(0));
        }
    }

    public int pop() {
        return a.remove(0);
    }

    public int top() {
        return a.get(0);
    }

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

H、普通 2023年7月10日下午10:09

class MyStack {

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

    public void push(int x) {
        //入队到Q2
        queue2.offer(x);
        //把Q1的全部放入到Q2中
        while (!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;

    }

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

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

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

0 赞同 0 条回复

阿尚普通 2023年7月10日下午8:41

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

<pre><code>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 pollValue = queue1.poll();

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

    return pollValue;
}
//取队头元素
public int top() {
    while(queue1.size() > 1){
        queue2.offer(queue1.poll());
    }
    int peekValue = queue1.poll();
    queue2.offer(peekValue);

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

    return peekValue;
}

public boolean empty() {
    if(queue1.isEmpty() && queue2.isEmpty()) return true;
    return false;
}
</code></pre>

}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月10日下午7:34

”’java
class MyStack {
//使用两个队列实现先入后出的栈
Queue que1;
Queue que2;//用来备份
public MyStack() {
this.que1 = new LinkedList<>();
this.que2 = new LinkedList<>();
}

public void push(int x) {
    que2.offer(x);//先放在辅助队列中
    while(!que1.isEmpty()){
        que2.offer(que1.poll());
    }
    Queue<Integer> queueTemp;
    queueTemp = que1;
    que1 = que2;
    que2 = queueTemp;
}

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

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

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

}
”’

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日下午7:25

LeetCode 225. 用队列实现栈

class MyStack {
public:
    MyStack() {

    }

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

    int pop() {
        int size = queue1.size();
        while(size > 1) {
            queue2.push(queue1.front());
            queue1.pop();
            size--;
        }
        int res = queue1.front();
        queue1 = queue2;
        while(!queue2.empty()) {
            queue2.pop();
        }
        return res;
    }

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

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

0 赞同 0 条回复

V2ero 普通 2023年7月10日下午5:58

代码如下

class MyStack {
    queue: number[];
    _queue: number[]

    constructor() {
        this.queue = [];
        this._queue = [];
    }

    push(x: number): void {
        this.queue.push(x);
    }

    pop(): number {
        while(this.queue.length > 1){
            this._queue.push(this.queue.shift());
        }
        let ans = this.queue.shift();
        while(this._queue.length){
            this.queue.push(this._queue.shift());
        }
        return ans;
    }

    top(): number {
        return this.queue.slice(-1)[0];
    }

    empty(): boolean {
        return !this.queue.length;
    }
}

0 赞同 0 条回复

Mooby 普通 2023年7月10日下午5:48

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

波雅汉库克普通 2023年7月10日下午4:11

class MyStack {
public:
    queue<int> q;

    MyStack() {

    }

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

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

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

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

push 操作：O(1)
pop() 操作： O(n)
top() 操作： O(1)

0 赞同 0 条回复

桎梏普通 2023年7月10日下午3:36

class CQueue {

    Stack<Integer> stakcIn;
    Stack<Integer> stakcOut;

    public CQueue() {
        stakcIn = new Stack<>();
        stakcOut = new Stack<>();
    }

    public void appendTail(int value) {
        stakcIn.push(value);
    }

    public int deleteHead() {
        if(stakcOut.isEmpty()) {
            while(!stakcIn.isEmpty()) {
                stakcOut.push(stakcIn.pop());
            }
        }
        if(stakcOut.isEmpty()) {
            return -1;
        }
        return stakcOut.pop();
    }
}

入栈时将队列中的前n-1个元素出队并放入队尾这样队头就是栈顶元素

0 赞同 0 条回复

AD钙奶普通 2023年7月10日下午3:11

Deque既可以作为栈，又可以作为队列
所以今天打卡的两题，都可以用这个数据结构来解
值得学习！

class MyStack {
    Deque<Integer> deque = new ArrayDeque<>();
    public MyStack() {

    }

    public void push(int x) {
        deque.addFirst(x);
    }

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

    public int top() {
        return deque.peekFirst();
    }

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

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

0 赞同 0 条回复

ONE PIECE 普通 2023年7月10日下午2:19

class MyStack {
    Deque deq;

    public MyStack() {
        deq = new LinkedList<>();
    }
    
    public void push(int x) {
        deq.offerFirst(x);
    }
    
    public int pop() {
        return deq.pollFirst();
    }
    
    public int top() {
        return deq.peekFirst();
    }
    
    public boolean empty() {
        return deq.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 条回复

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

共以下 44 个回答

用队列实现栈

# 回答此问题取消回复

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

共以下 44 个回答

用队列实现栈

# 回答此问题 取消回复

# 回答此问题取消回复