Thread: Stacks and time

Considering there are no loops or recursion, and all I see are simple comparisons, increment, assignment, decrement, I'd say the best, average and worst case complexity for both is constant time.

If I added an operation called peek that would look at the next item below the top of the stack... wouldn't that add more steps?

No matter how large the stack, peek (or pop and push, for that matter) would still take roughly the same number of operations.

hmm... okay, this is how I might implement the stack operations you mentioned:

Code:

void stack::push(int x) {
    // Implemented with fixed size array, so no expansion.
    if (size < MAX_SIZE) {
        stackArray[size] = x;
        ++size;
    }
}

void stack::pop() {
    if (size > 0) {
        --size;
    }
}

int& stack::peek() {
    return stackArray[size - 1];
}

const int& stack::peek() const {
    return stackArray[size - 1];
}

Look at push(). Suppose the array has no elements. We know that(size < MAX_SIZE) will be true, hence we have an assignment and an increment. Suppose the array has MAX_SIZE-1 elements. We still have an assignment and an increment. If the array has MAX_SIZE elements, the only operation performed is the comparison. So, the size of the array does not change the complexity of push().

Look at pop(). Suppose the array has no elements. We know that (size > 0) is false, so the only operation is the comparison. Suppose the array has MAX_SIZE elements. (size > 0) is true, so besides the comparison we have a decrement. That's all, so the size of the array does not change the complexity of pop().

For your implementation of pop() this is true as well. It does not matter how large is the array, the same sequence of:

Code:

int x = stackArray[top];
top--;
size--;
return x;

will be performed.

It is clear that both non-const and const versions of peek() run in constant time since they just access the array by index, and arrays have random access.

If, on the other hand, you implemented the stack as a linked list, and made a "peek(x)" function that gives you the xth element, this function would be O(n), as you'd have to search through the list to find the xth element.

--
Mats