Why we use top== -1 for implementation of stack using simple array?

Question

I am a newbie at data structures.

I have read an implementation of a stack using a simple array. The algorithm for this implementation is presented below.

Stack implementation in terms of an array

Before implementing actual operations, first follow the below steps to create an empty stack.

1. Include all the header files which are used in the program and define a constant SIZE with specific value.
2. Declare all the functions used in stack implementation.
3. Create a one dimensional array with fixed size (int stack[SIZE])
4. Define a integer variable top and initialize with -1. (int top = -1)
5. In main method display menu with list of operations and make suitable function calls to perform operation selected by the user on the stack.

push(value) - Insert a value into the stack

In a stack, push() is a function used to insert an element into the stack. In a stack, the new element is always inserted at the top position. Push function takes one integer value as parameter and inserts that value into the stack. We can use the following steps to push an element on to the stack...

1. Check whether stack is FULL. (top == SIZE-1)
2. If it is FULL, then display "Stack is FULL!!! Insertion is not possible!!!" and terminate the function.
3. If it is NOT FULL, then increment top value by one (top++) and set stack[top] to value (stack[top] = value).

pop() - Delete a value from the stack

In a stack, pop() is a function used to delete an element from the stack. In a stack, the element is always deleted from top position. Pop function does not take any value as parameter. We can use the following steps to pop an element from the stack...

1. Check whether stack is EMPTY. (top == -1)
2. If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not possible!!!" and terminate the function.
3. If it is NOT EMPTY, then delete stack[top] and decrement top value by one (top--).

display() - Display elements of the stack

We can use the following steps to display the elements of a stack...

1. Check whether stack is EMPTY. (top == -1)
2. If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function.
3. If it is NOT EMPTY, then define a variable i and initialize with top. Display stack[i] value and decrement i value by one (i--).
4. Repeat above step until i value becomes 0.

My question is why we use top == -1 in stack instead of top == 1?

• Philip Kendall: I suggest you implement this as specified, then try changing the initial value of top to 1 and seeing which bits break.
• CodesInChaos: You could also use count instead, where count - 1 corresponds to your top.

Answer 1

In C, arrays are zero-based. So when top == 0 it means there is one element on the stack. By consequence, if the stack is empty, the top index is set to -1 so that when the first element is added, it is incremented to 0.

Answer 2

You need a variable that keeps track of how much your stack is filled. You need to decide what the exact meaning of that variable is and what it's name should be.

There are two obvious possibilities: You call it "top" and it is the index of the highest used position in the stack. Since initially no positions are used, you start with top = -1. After pushing the first item, the highest used position is top = 0.

Or you call it "next" and it is the index of the highest unused position in the stack. Since initially no positions are used, you start with next = 0. After pushing the first item, the highest unused position is next = 1.

It's your choice, both solutions are equally good.