容器与迭代接口设计

class MyQueue:
    """A FIFO queue built from two stacks (LC 232)."""

    def __init__(self):
        self.inbox: list[int] = []  # new items go on top here
        self.outbox: list[int] = []  # items leave from here, oldest on top

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

    def _refill(self) -> None:
        if not self.outbox:  # only when empty, or the order breaks
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self) -> int:
        self._refill()
        return self.outbox.pop()

    def peek(self) -> int:
        self._refill()
        return self.outbox[-1]

    def empty(self) -> bool:
        return not self.inbox and not self.outbox

// A FIFO queue built from two stacks (LC 232).
class MyQueue {
    stack<int> inbox, outbox;  // new items go on inbox; items leave from outbox, oldest on top

    void refill() {
        if (outbox.empty())  // only when empty, or the order breaks
            for (; !inbox.empty(); inbox.pop()) outbox.push(inbox.top());
    }

public:
    void push(int x) { inbox.push(x); }
    int pop() {
        refill();
        int x = outbox.top();
        outbox.pop();
        return x;
    }
    int peek() {
        refill();
        return outbox.top();
    }
    bool empty() const { return inbox.empty() && outbox.empty(); }
};

// A FIFO queue built from two stacks (LC 232).
class MyQueue {
    private final Deque<Integer> inbox = new ArrayDeque<>(); // new items go on top here
    private final Deque<Integer> outbox = new ArrayDeque<>(); // items leave from here, oldest on top

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

    int pop() {
        refill();
        return outbox.pop();
    }

    int peek() {
        refill();
        return outbox.peek();
    }

    boolean empty() {
        return inbox.isEmpty() && outbox.isEmpty();
    }

    private void refill() {
        if (outbox.isEmpty()) // only when empty, or the order breaks
            while (!inbox.isEmpty()) outbox.push(inbox.pop());
    }
}

// MyQueue is a FIFO queue built from two stacks (LC 232).
type MyQueue struct {
	inbox, outbox []int // new items go on inbox; items leave from outbox, oldest on top
}

func (q *MyQueue) Push(x int) { q.inbox = append(q.inbox, x) }

func (q *MyQueue) refill() {
	if len(q.outbox) == 0 { // only when empty, or the order breaks
		for len(q.inbox) > 0 {
			q.outbox = append(q.outbox, q.inbox[len(q.inbox)-1])
			q.inbox = q.inbox[:len(q.inbox)-1]
		}
	}
}

func (q *MyQueue) Pop() int {
	q.refill()
	x := q.outbox[len(q.outbox)-1]
	q.outbox = q.outbox[:len(q.outbox)-1]
	return x
}

func (q *MyQueue) Peek() int {
	q.refill()
	return q.outbox[len(q.outbox)-1]
}

func (q *MyQueue) Empty() bool { return len(q.inbox) == 0 && len(q.outbox) == 0 }

class MinStack:
    """A stack with O(1) get_min (LC 155)."""

    def __init__(self):
        self.items: list[tuple[int, int]] = []  # (value, minimum of it and everything below)

    def push(self, x: int) -> None:
        low = min(x, self.items[-1][1]) if self.items else x
        self.items.append((x, low))

    def pop(self) -> None:
        self.items.pop()

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

    def get_min(self) -> int:
        return self.items[-1][1]

// A stack with O(1) getMin (LC 155).
class MinStack {
    vector<pair<int, int>> items;  // {value, minimum of it and everything below}

public:
    void push(int x) {
        int low = items.empty() ? x : min(x, items.back().second);
        items.push_back({x, low});
    }
    void pop() { items.pop_back(); }
    int top() const {
        return items.back().first;
    }
    int getMin() const {
        return items.back().second;
    }
};

// A stack with O(1) getMin (LC 155).
class MinStack {
    private final Deque<int[]> items = new ArrayDeque<>(); // {value, minimum of it and everything below}

    void push(int x) {
        items.push(new int[] {x, items.isEmpty() ? x : Math.min(x, items.peek()[1])});
    }

    void pop() {
        items.pop();
    }

    int top() {
        return items.peek()[0];
    }

    int getMin() {
        return items.peek()[1];
    }
}

// MinStack is a stack with O(1) GetMin (LC 155).
type MinStack struct {
	items [][2]int // {value, minimum of it and everything below}
}

func (s *MinStack) Push(x int) {
	low := x
	if n := len(s.items); n > 0 {
		low = min(x, s.items[n-1][1])
	}
	s.items = append(s.items, [2]int{x, low})
}

func (s *MinStack) Pop()        { s.items = s.items[:len(s.items)-1] }
func (s *MinStack) Top() int    { return s.items[len(s.items)-1][0] }
func (s *MinStack) GetMin() int { return s.items[len(s.items)-1][1] }