Implementation of a stack

An implementation of stack is similar to that of a Linked List. We will try to discuss the basic operations in a stack discussed in this post.

MAIN OPERATIONS ON A STACK:-

• push( int ) :- Inserts a data into the stack
• pop :- Returns the topmost data from the stack

AUXILIARY OPERATIONS ON A STACK

• int Top( ) :- returns the topmost element on the stack
• int Size( ) :- returns the total size of the stack
• int isStackEmpty( ) :- returns true if the stack is empty

The data structure for a stack can be made as the same as that of a single Linked List. We need a node with a next element.

struct stackNode
{
    int data;
    struct stackNode * next;
};

Now we need to define the basic function of pushing a node in the stack. A PUSH operation, adds a new node in the stack and points the TOP of the stack to this new node.

// defining the generic function to PUSH an element into the stack
struct stackNode * push(struct stackNode * top, int element)
{
    //creating a temporary node and assigning the element to be PUSHED
    struct stackNode * temp = (struct stackNode *)malloc(sizeof(struct stackNode));
    temp -> data = element;

    // we need to point the NEXT of this node to the previous TOP
    temp -> next = top;

    // we need to update the TOP node and then return it
    // we can simply return the 'temp' node as it points to the new TOP node.
    return temp;
}

Now let us define a function to check if the stack is empty. A stack is empty, if the top node points to a NULL location

// defining a function to check if a stack is empty
int isStackEmpty(struct stackNode * top)
{
    if(top == NULL)
        return 1;
    else
        return 0;
}

Now to define the POP function. To define the POP function, we must check if the stack is empty or not. If the stack is empty, that means we cannot POP any value and it is a case of stack underflow. However, if the stack is not empty, we simply print the TOP value and delete the top node.

// defining a function to pop an element from a stack
struct stackNode * pop(struct stackNode * top)
{
    // check if the stack is empty
    if(isStackEmpty(top))
    {
        printf("STACK IS EMPTY...Stack underflow");
        return NULL;
    }
    else
    {
        printf("POP element = %d",top -> data);

        // we need to delete the top and move to the next element.

        struct stackNode * temp = top;

        // move to the next node
        top = top -> next;

        // delete the original top
        free(temp);

        // return the new top
        return top;
    }
}

The last function to get the number of elements in the stack is same as calculating the length of a single Linked List.

// function to get the size of the stack
int getStackSize(struct stackNode * top)
{
    int count = 0;
    while(top)
    {
        count++;
        top = top -> next;
    }
    return count;
}

These were the basic functions used in implementing a stack and being generic functions can be used anytime we need to implement stacks. Here is a working demo of the code that utilizes all the above function. Use your favorite editor to edit it. (gEdit, vim, notepad++)