Implement Stacks in C – Example

In the previous post, we implemented linked list in C. In the same way, now we are going to implement stacks in c programming language by an example. We will be using a self-referential structure which stores an integer.

Let’s see the example first,

#include <stdio.h>
#include <stdlib.h>

// Self-referential structure
struct stackNode {
    int data;  // A integer data in the stack
    struct stackNode *nextPtr;   // Pointer to next element of stack
}; // end struct stackNode

typedef struct stackNode StackNode; // alias for the struct
typedef StackNode *StackNodePtr;  // alias for StackNode*

// Declarations
// Pointer to the top plays the main role
void push(StackNodePtr *topPtr, int info);
int pop(StackNodePtr *topPtr);
int isEmpty(StackNodePtr topPtr);
void showStack(StackNodePtr currentPtr);
void showMenu(void);

int main() {
    // Points to stack top
    StackNodePtr stackPtr = NULL;
    // User's choice
    unsigned int ch;
    // User's entered character
    int item;
    
    // Display the menu
    showMenu();
    printf("? ");
    scanf("%u", &ch);
    
    // Loop unless user chooses 3
    while(ch != 3) {
        switch(ch) {
            case 1:
                printf("Enter an integer: ");
                scanf("%d", &item);
                
                // insert the item in the top of stack
                push(&stackPtr, item);
                showStack(stackPtr);
                break;
            case 2:
                // if stack is not empty
                if(!isEmpty(stackPtr)) {
                    printf("The popped integer is %d.\n", pop(&stackPtr));
                } // end if 
                showStack(stackPtr);
                break;
            default:
                printf("Invalid choice.\n");
                showMenu();
                break;
        }
        showMenu();
        printf("? ");
        scanf("%u", &ch);
    }
    printf("Thank You!\n");
    return 0;
}

// Display Menu Function
void showMenu(void) {
    printf("Enter your choice:\n"
        "   1 to push integer into the stack.\n"
        "   2 to pop integer from the stack.\n"
        "   3 to end" );
}

// insert a node to the top of stack
void push(StackNodePtr *topPtr, int value) {
    StackNodePtr newPtr; // pointer to new node
    
    newPtr = malloc(sizeof(StackNode)); // Allocate memory for StackNode
    
    // if allocated
    if (newPtr != NULL) {
        newPtr->data = value;   // put value in the node
        newPtr->nextPtr = *topPtr;
        *topPtr = newPtr; // new node is top
    } // end if
    else {
        printf("%d is not inserted. Memory error!\n", value);
    }
}

// pop from the stack
int pop(StackNodePtr *topPtr) {
    StackNodePtr tmpPtr; // temporary node pointer
    int popValue; // node value
    
    tmpPtr = *topPtr;
    popValue = tmpPtr->data;
    
    *topPtr = tmpPtr->nextPtr; 
    free(tmpPtr);
    
    return popValue;
}

// return 1 if the stack is empty, otherwise 0
int isEmpty(StackNodePtr topPtr) {
    return topPtr == NULL;
}

// show the list
void showStack(StackNodePtr currentPtr) {
    // if stack is empty
    if (isEmpty(currentPtr)) {
        printf("The stack is empty!\n");
    }
    else {
        printf("The stack is: \n");
        
        // while not the end of stack
        while(currentPtr != NULL) {
            printf("%d ==> ", currentPtr->data);
            currentPtr = currentPtr->nextPtr;
        }
        printf("NULL\n");
    }
}

It is a bit easier to implement than that of stack since, we just have push and pop operation. Moreover, these operations are performed from the top of stack, so the implementation is quite easy. Let’s elaborate the example to implement stacks in C. Let’s see from the declaration of the stackNode structure.

// Self-referential structure
struct stackNode {
    int data;  // A integer data in the stack
    struct stackNode *nextPtr;   // Pointer to next element of stack
}; // end struct stackNode

Here, we declared a structure which contains integer data, and a pointer which points to the similar node, i.e. nextPtr contains the memory reference to a stackNode.

typedef struct stackNode StackNode; // alias for the struct
typedef StackNode *StackNodePtr;  // alias for StackNode*

// Declarations
// Pointer to the top plays the main role
void push(StackNodePtr *topPtr, int info);
int pop(StackNodePtr *topPtr);
int isEmpty(StackNodePtr topPtr);
void showStack(StackNodePtr currentPtr);
void showMenu(void);

The above codes are self explanatory. Without ado, let’s look into the push and pop operations.

push(&stackPtr, item);

The above line of code sends the memory address of the top of stack along with the item entered by the user to the push function.

Now, we have to create a new node to the top of the stack, which we did by the following lines of code:

StackNodePtr newPtr; // pointer to new node
newPtr = malloc(sizeof(StackNode)); // Allocate memory for StackNode

After this, we have to assign the value to the new node and assign stack pointer to the node.

// if allocated
    if (newPtr != NULL) {
        newPtr->data = value;   // put value in the node
        newPtr->nextPtr = *topPtr;
        *topPtr = newPtr; // new node is top
    } // end if

At first, we have to know that (*newPtr).data and newPtr->data are the same thing. Therefore, in the above code, we assigned the data of new node of the stack to the entered value by the user. Also, we pointed the topPtr to the address of newPtr. In this way, push operation is completed.

So, you know how to implement the push operation. In the same way, you can easily understand the pop operation.

In any event, you can find the gist here.