ADT Stack

Idea Like You Are 10

A stack is like a pile of books.

You can:

But you cannot remove the book from the middle first.

This rule is called:

LIFO = Last In, First Out

Top
 |
 v
[10]
[20]
[30]

If top = -1, the stack is empty.

push(stack, x):
    if top == MAX - 1:
        overflow
    top = top + 1
    stack[top] = x

Time: O(1)

pop(stack):
    if top == -1:
        underflow
    x = stack[top]
    top = top - 1
    return x

Time: O(1)

peek(stack):
    if top == -1:
        underflow
    return stack[top]

Time: O(1)

isEmpty():
    return top == -1

Time: O(1)

isFull():
    return top == MAX - 1

Time: O(1)

display(stack):
    for i from top down to 0:
        print stack[i]

Time: O(n)