Jul 262013
 

A better implementation of Stack is usually using linked list unless you are sure of the number of elements in array. But if you are just starting with data structures and are not familiar with linked list, you can try implementing stack in an array.

While using array to implement stack is easy, it has limitation that the stack cannot grow beyond a fixed size (of array). 

Operations

There can be many operations on stack like this post, but we will discuss only three basic operations on the stack

Push – inserting element at the top of stack.
Pop – removing the top element of stack.
isEmpty – check is stack is empty or not.

Code

For simplicity reason lets assume the array (which hold stack) to be global and accessible to all the functions.

// Max number of elements a stack can hold
#define MAX 100

// Array to hold the stack
int s[MAX];

// will hold the index of top element of the stack.
// top == -1 means stack is empty
int top = -1;

/** Push the element if there is a space in the Stack
 * If Stack is full then does nothing.
 */
void  push(int value)
{
    if (top == MAX-1) 
    {
        printf("Stack is full cannot push more elements.");
        return;
    }
    s[++top] = value;
}

/** Pop the top element from stack and returns it. If stack is empty return -1.
 */
int pop()
{
    if (top == -1)
    {
        printf("Empty Stack. Nothing to return.");
        return -1;
    }
    return s[top--];
}
/** returns true if stack is empty, else false.
 */
bool isEmpty()
{
    return (top == -1);
}

Understanding above code

Above code is in way a good code. There are lot of problems, to start with pop returns -1 when stack is empty which means that -1 cannot be a valid member of the stack.

Push function should ideally return something to tell its calling function whether or not it was able to insert element in the stack. printf is not a good way in production code, because most often it ends up printing in logs.

The size of Array is 100, if we just need 10 element stack, then 90 element memory will be wasted. In other case, if we want a stack with 500 element, we will have to change MAX value, which means program need to be compiled again. The solution to this can be to get the size of stack from the calling function and allocate memory using malloc (or new in C++). But then we should be cautious about deallocating memory when done, else it will leave memory leaks.

Time Complexity

All the above operations are constant time operations and takes O(1) time. In fact, almost all the operations of Stack and Queue are constant time operations, except for operations like printing all elements, etc.

Also Read: Optimized Implementing of two stacks in a Single Array

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)