[002] [LeetCode刷题记录] 225-用队列实现栈

[002] [LeetCode刷题记录] 225-用队列实现栈

[LeetCode刷题记录] 225-用队列实现栈

• 1 题目描述
• 2 解题思路及代码
• • 2.1 C语言实现
  • 2.2 Python3语言实现

1 题目描述

LeetCode原题链接：225. 用队列实现栈

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

实现 MyStack 类：

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

注意：

• 你只能使用队列的基本 *** 作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些 *** 作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列 *** 作即可。

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

2 解题思路及代码 2.1 C语言实现

 
#define MAXSIZE (101)

typedef struct{     // 采用顺序循环队列
    int *queue;
    int front;
    int rear;
}Queue;

Queue* queueCreate(int capacity){
    Queue* ret = (Queue*)malloc(sizeof(Queue));
    ret->queue = malloc(sizeof(int) * capacity);
    ret->front = ret->rear = 0;
    return ret;
}

bool isQueueEmpty(Queue* obj){
    return obj->front == obj->rear;
}

void queuePush(Queue* obj, int x){
    obj->queue[obj->rear] = x;
    obj->rear = (obj->rear + 1) % MAXSIZE;
}

void queuePop(Queue* obj){       // 出队
    obj->front = (obj->front + 1) % MAXSIZE;
}

int queuePeek(Queue* obj){       // 取队头元素
    return obj->queue[obj->front];
}

void queueFree(Queue* obj){
    free(obj->queue);
}

typedef struct {
    Queue* queue1;
    Queue* queue2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* ret = (MyStack*)malloc(sizeof(MyStack));
    ret->queue1 = queueCreate(MAXSIZE);
    ret->queue2 = queueCreate(MAXSIZE);
    return ret; 
}

void myStackPush(MyStack* obj, int x) {
    while(!isQueueEmpty(obj->queue1)){  // 队列1元素先出队并且入队列2
        queuePush(obj->queue2, queuePeek(obj->queue1));
        queuePop(obj->queue1);
    }

    queuePush(obj->queue1, x);          // 新元素成为队列1的队头

    while(!isQueueEmpty(obj->queue2)){  // 队列1元素先出队并且入队列2
        queuePush(obj->queue1, queuePeek(obj->queue2));
        queuePop(obj->queue2);
    }
}

int myStackPop(MyStack* obj) {  // d栈(需记录栈顶元素)
    int x = queuePeek(obj->queue1);
    queuePop(obj->queue1);
    return x;
}

int myStackTop(MyStack* obj) {   // 取栈顶元素
    return queuePeek(obj->queue1);
}

bool myStackEmpty(MyStack* obj) {
    return isQueueEmpty(obj->queue1);
}

void myStackFree(MyStack* obj) {
    queueFree(obj->queue1);
    queueFree(obj->queue2);
}

复杂度分析：

• 时间复杂度：入栈 *** 作为O(n)，其余 *** 作为O(1)。
  每次入栈时，都需要将queue1中n个元素出队并入队到queue2，然后入队1个新元素到queue1，再将queue2中n个元素出队并入队到queue1，因此入栈 *** 作时间复杂度为O(n)。
• 空间复杂度：O(n)。
  一共需要开辟两个含有n个元素的队列。

2.2 Python3语言实现

from collections import deque

'''
1. 使用双端队列
2. 在插入新元素之前，获取队列长度，然后将队列元素出队再入队
3. 如此 *** 作后，队列的前端和后端分别对应栈顶和栈底
'''


class MyStack:

    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        n = len(self.queue)
        self.queue.append(x)
        for _ in range(n):
            self.queue.append(self.queue.popleft())  # popleft 删除并返回队列中的第一个(最左边的)元素

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

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

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

END