[Vssue]0225.用队列实现栈.md

[youngyangyang04]

https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

[Du1in9]

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }
    public void push(int x) {
        queue.add(x);
        int size = queue.size();
        while (size > 1) {
            queue.add(queue.poll());
            size--;
        }
    }
    public int pop() {
        return queue.poll();
    }
    public int top() {
        return queue.peek();
    }
    public boolean empty() {
        return queue.isEmpty();
    }
}

[MaiXiming]

Python使用list实现：

class MyStack:

    def __init__(self):
        self.q_in, self.q_out = [], []

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

    def pop(self) -> int:
        if self.empty():
            return None
        for _ in range(len(self.q_in)-1):
            self.q_out.append(self.q_in.pop(0))
        output = self.q_in.pop(0)

        for _ in range(len(self.q_out)):
            self.q_in.append(self.q_out.pop(0))
        return output

    def top(self) -> int:
        if self.empty():
            return None
        output = self.pop()
        self.push(output)
        return output

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

[sheep112]

c语言

#define LEN 20
typedef struct queue {
    int *data;
    int head;
    int rear;
    int size;
} Queue;

Queue* initQueue(int k)
{
    Queue *obj = (Queue *)malloc(sizeof(Queue));
    obj->data = (int*)malloc(k * sizeof(int));
    obj->head = -1;
    obj->rear = -1;
    obj->size = k;
    return obj;
}

// 检查队列是否已满
int isFull(Queue *obj) {
    return (obj->rear + 1) % obj->size == obj->head;
}

void enQueue(Queue *obj, int e)
{
    if (isFull(obj)) {
        printf("Queue is full\n");
        return;
    }
    if (obj->head == -1) {
        obj->head = 0;
    }
    obj->rear = (obj->rear + 1) % obj->size;
    obj->data[obj->rear] = e;
}

int deQueue(Queue *obj)
{
    if (isEmpty(obj)) {
        printf("Queue is empty\n");
        return -1;
    }
    int a = obj->data[obj->head];
    if (obj->head == obj->rear) {
        obj->rear = -1;
        obj->head = -1;
    } else {
        obj->head = (obj->head + 1) % obj->size;
    }
    return a;   
}

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

void rotateQueue(Queue *obj) {
    if (isEmpty(obj) || obj->rear == obj->head) {
        return;
    }

    int temp = deQueue(obj); // 取出队首元素
    enQueue(obj, temp);      // 将队首元素插入到队尾
}

typedef struct {
    Queue *queue;
} MyStack;

MyStack* myStackCreate() {
    MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
    obj->queue = initQueue(LEN);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    enQueue(obj->queue, x);
    int size = (obj->queue->rear - obj->queue->head + obj->queue->size) % obj->queue->size;
    for (int i = 0; i < size; i++) {
        rotateQueue(obj->queue);
    }
}

int myStackPop(MyStack* obj) {
    return deQueue(obj->queue);
} 

int myStackTop(MyStack* obj) {
    // 修改为直接返回队列头部的元素
    return obj->queue->data[obj->queue->head];
}

bool myStackEmpty(MyStack* obj) {
    return isEmpty(obj->queue);
}

void myStackFree(MyStack* obj) {
    free(obj->queue->data);
    free(obj->queue);
    free(obj);
}

[NineFourths]

cpp

class MyStack {
private:
    queue<int> main_queue,sub_queue;
public:
    MyStack() {

    }

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

    int pop() {
        int cnt=main_queue.size();
        --cnt;
        while(cnt--){
            sub_queue.push(main_queue.front());
            main_queue.pop();
        }

        int res=main_queue.front();
        main_queue.pop();

        main_queue=sub_queue;
        while(!sub_queue.empty()){
            sub_queue.pop();
        }

        return res;
    }

    int top() {
        int ret = pop();
        push(ret);
        return ret;
    }

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