232.用栈实现队列

链接：232.用栈实现队列
难度：Easy
标签：栈、设计、队列
简介：使用栈实现队列的下列操作：push(x) -- 将一个元素放入队列的尾部。pop() -- 从队列首部移除元素。peek() -- 返回队列首部的元素。empty() -- 返回队列是否为空。

题解 1 - typescript

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

typedef struct Stack
{
    int size;
    int len;
    int *data;
} Stack;
Stack *createStack(int len)
{
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->size = 0;
    s->len = len;
    s->data = (int *)malloc(sizeof(int) * len);
    return s;
}
void push(Stack *s, int val)
{
    if (s->size == s->len)
        return;
    s->data[s->size++] = val;
}
void pop(Stack *s)
{
    if (s->size == 0)
        return;
    s->size--;
}
int isEmpty(Stack *s) {
    return s->size == 0;
}
int top(Stack *s)
{
    if (s->size == 0) return -1;
    return s->data[s->size - 1];
}
void freeStack(Stack *s)
{
    free(s->data);
    free(s);
}
typedef struct {
    Stack *s1, *s2;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));
    q->s1 = createStack(100);
    q->s2 = createStack(100);
    return q;
}
void myQueuePush(MyQueue* obj, int x) {
    push(obj->s1, x);
}
void check(MyQueue *obj){
    if (!obj->s2->size) {
        while(obj->s1->size) {
            push(obj->s2, top(obj->s1));
            pop(obj->s1);
        }
    }
}
int myQueuePop(MyQueue* obj) {
    check(obj);
    int val = top(obj->s2);
    pop(obj->s2);
    return val;
}
int myQueuePeek(MyQueue* obj) {
    check(obj);
    return top(obj->s2);
}
bool myQueueEmpty(MyQueue* obj) {
    return obj->s1->size + obj->s2->size == 0;
}
void myQueueFree(MyQueue* obj) {
    freeStack(obj->s1);
    freeStack(obj->s2);
    free(obj);
}

题解 2 - typescript

• 编辑时间：2021-03-05
• 执行用时：84ms
• 内存消耗：39.1MB
• 编程语言：typescript
• 解法介绍：利用两个栈维护。

class MyQueue {
  private inStack: number[] = [];
  private outStack: number[] = [];
  push(x: number): void {
    this.inStack.push(x);
  }
  pop(): number {
    if (this.empty()) return -Infinity;
    if (this.outStack.length > 0) {
      return this.outStack.pop()!;
    } else {
      this.inStackToOutStack();
      return this.pop();
    }
  }
  peek(): number {
    if (this.empty()) return -Infinity;
    if (this.outStack.length === 0) this.inStackToOutStack();
    return this.outStack[this.outStack.length - 1];
  }
  empty(): boolean {
    return this.outStack.length === 0 && this.inStack.length === 0;
  }
  inStackToOutStack(): void {
    while (this.inStack.length > 0) this.outStack.push(this.inStack.pop()!);
  }
}

题解 3 - java

• 编辑时间：2020-02-16
• 内存消耗：34.2MB
• 编程语言：java
• 解法介绍：使用 java 自带栈结构，使用两个栈，压栈放入 inStack，出栈时若 outStack 为空则先出栈 inStack 压倒 outStack。

class MyQueue {
	private Stack<Integer> inStack;
	private Stack<Integer> outStack;
    public MyQueue() {
        inStack = new Stack<Integer>();
		outStack = new Stack<Integer>();
    }
	public void push(int x) {
		inStack.push(x);
	}
	public int pop() {
		checkOutStack();
		return outStack.pop();
	}
	public int peek() {
		checkOutStack();
		return outStack.peek();
	}
	public boolean empty() {
		return inStack.isEmpty() && outStack.isEmpty();
	}
	private void checkOutStack() {
		if (outStack.isEmpty()) {
			while (!inStack.isEmpty()) {
				outStack.push(inStack.pop());
			}
		}
	}
}

题解 4 - python

• 编辑时间：2024-03-04
• 执行用时：40ms
• 内存消耗：16.55MB
• 编程语言：python
• 解法介绍：用两个栈模拟。

class MyQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []
    def push(self, x: int) -> None:
        self.s1.append(x)
    def pop(self) -> int:
        self.check()
        return self.s2.pop()
    def peek(self) -> int:
        self.check()
        return self.s2[-1]
    def empty(self) -> bool:
        return not self.s1 and not self.s2
    def check(self) -> bool:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())