225.用队列实现栈

链接：225.用队列实现栈
难度：Easy
标签：栈、设计、队列
简介：使用队列实现栈的下列操作：push(x) -- 元素 x 入栈，pop() -- 移除栈顶元素，top() -- 获取栈顶元素，empty() -- 返回栈是否为空。

题解 1 - java

• 编辑时间：2020-02-16
• 内存消耗：40.8MB
• 编程语言：java
• 解法介绍：使用双端队列构建。

class MyStack {
    private Deque<Integer> deue;
    public MyStack() {
        deue=new LinkedList<Integer>();
    }
    public void push(int x) {
        deue.offerLast(x);
    }
    public int pop() {
    	return deue.pollLast();
    }
    public int top() {
        return deue.getLast();
    }
    public boolean empty() {
        return deue.isEmpty();
    }
}

题解 2 - python

• 编辑时间：2024-03-03
• 执行用时：36ms
• 内存消耗：16.42MB
• 编程语言：python
• 解法介绍：每次循环n-1次使队尾在头部。

class MyStack:
    def __init__(self):
        self.q = deque()
    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
    def pop(self) -> int:
        return self.q.popleft()
    def top(self) -> int:
        return self.q[0]
    def empty(self) -> bool:
        return not self.q

题解 3 - typescript

• 编辑时间：2021-11-24
• 内存消耗：5.7MB
• 编程语言：typescript
• 解法介绍：queue。

// #define DEBUG
#ifdef DEBUG
#define log(frm, args...)    \
    {                        \
        printf(frm, ##args); \
    }
#else
#define log(frm, args...)
#endif
typedef struct Node{
    int val;
    struct Node *prev, *next;
} Node;
Node *createNode(int val){
    Node *node = (Node *)malloc(sizeof(Node));
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}
typedef struct {
    int size;
    Node *head, *tail;
} Queue;
Queue *ceateQueue(){
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->size = 0;
    q->tail = q->head = NULL;
    return q;
}
void enQueue(Queue *q, int val){
    Node *node = createNode(val);
    if (q->size == 0) {
        q->head = q->tail = node;
    } else {
        node->prev = q->tail;
        q->tail->next = node;
        q->tail = node;
    }
    q->size++;
    log("enQueue %d success, head = %d, tail = %d\n", val, q->head->val, q->tail->val);
}
int isQueueEmpty(Queue *q) {
    return q->size == 0;
}
int queueTop(Queue *q){
    if (isQueueEmpty(q)) return -1;
    return q->head->val;
}
int deQueue(Queue *q) {
    if (isQueueEmpty(q)) return -1;
    if (q->size == 1) {
        Node *node = q->head;
        int val = node->val;
        q->tail = q->head = NULL;
        free(node);
        q->size = 0;
        return val;
    }
    Node *node = q->head;
    node->next->prev = NULL;
    int val = node->val;
    q->head = node->next;
    free(node);
    q->size--;
    return val;
}
void freeQueue(Queue *q){
    while(q->size) deQueue(q);
    free(q);
}
typedef struct {
    int size;
    Queue *q1, *q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack *s = (MyStack *)malloc(sizeof(MyStack));
    s->q1 = ceateQueue();
    s->q2 = ceateQueue();
    return s;
}
void myStackPush(MyStack* obj, int x) {
    log("push %d\n", x);
    enQueue(obj->q1, x);
    log("push %d successfully\n", x);
}
int myStackPop(MyStack* obj) {
    while(obj->q1->size > 1) enQueue(obj->q2, deQueue(obj->q1));
    int val = deQueue(obj->q1);
    while(obj->q2->size) enQueue(obj->q1, deQueue(obj->q2));
    return val;
}
int myStackTop(MyStack* obj) {
    return obj->q1->tail->val;
}
bool myStackEmpty(MyStack* obj) {
    return obj->q1->size == 0;
}
void myStackFree(MyStack* obj) {
    freeQueue(obj->q1);
    freeQueue(obj->q2);
    free(obj);
}