A stack that knows its minimum

Build a stack that can report its smallest item at any moment without searching.

What to build

A stack with a min command that takes O(1) time.

Requirements

push x adds x to the stack.
pop removes the top item and prints it, or prints empty.
min prints the smallest item in the stack, or empty. It must not loop over the items.

Input

The first line has q. Each of the next q lines has one command.

Output

One line for each pop and each min.

Constraints

1 ≤ q ≤ 1000.

Example

Input:

7
push 5
push 3
push 8
min
pop
pop
min

Output:

Why it works

The minimum of a stack can change only when its top changes. Remembering the minimum at every height means a pop simply uncovers the answer that was correct before the push.

Examples

Example 1 · Input

7
push 5
push 3
push 8
min
pop
pop
min

Expected output

Example 2 · Input

2
min
pop

Expected output

empty
empty

Hints

Hint 1

Keep a second array, the same height as the stack.

Hint 2

At each level, store the smallest value among that item and everything below it.

Hint 3

When you push x, the new minimum is x or the minimum just below, whichever is smaller. Popping needs no extra work.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#include <string.h>

int items[1000], mins[1000];
int top = -1;

int main(void) {
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char cmd[10];
        scanf("%9s", cmd);
        if (strcmp(cmd, "push") == 0) {
            int x;
            scanf("%d", &x);
            top++;
            items[top] = x;
            if (top == 0 || x < mins[top - 1]) mins[top] = x;
            else mins[top] = mins[top - 1];
        } else if (strcmp(cmd, "pop") == 0) {
            if (top == -1) printf("empty\n");
            else printf("%d\n", items[top--]);
        } else {
            if (top == -1) printf("empty\n");
            else printf("%d\n", mins[top]);
        }
    }
    return 0;
}

Lesson: Stacks →