The Stack in C programming

Stacks

A stack can be implemented as a constrained version of a linked list. New nodes can be added to a stack and removed from a stack only at the top. For this reason, a stack is referred to as a last-in, first-out (LIFO) data structure.

A stack is referenced via a pointer to the top element of the stack. The link member in the last node of the stack is set to NULL to indicate the bottom of the stack.

The difference between stacks and linked lists is that insertions and deletions may occur anywhere in a linked list, but only at the top of a stack.

The primary functions used to manipulate a stack:

push creates a new node and places it on top of the stack.
pop removes a node from the top of the stack, frees the memory that was allocated to the popped node and returns the popped value.

Functions push and pop

The program provides three options:

push a value onto the stack (function push)
pop a value off the stack (function pop)
terminate the program


        // A simple stack program
    #include <stdio.h>
    #include <stdlib.h<
    
    // self-referential structure                     
    struct stackNode {                                   
    int data; // define data as an int             
    struct stackNode *nextPtr; // stackNode pointer
    }; // end structure stackNode                     
    typedef struct stackNode StackNode; // synonym for struct stackNode
    typedef StackNode *StackNodePtr; // synonym for StackNode*
    
    // prototypes
    void push( StackNodePtr *topPtr, int info );
    int pop( StackNodePtr *topPtr );
    int isEmpty( StackNodePtr topPtr );
    void printStack( StackNodePtr currentPtr );
    void instructions( void );
    
    // display program instructions to user
    void instructions( void ){ 
    puts( "Enter choice:\n"
      "1 to push a value on the stack\n"
      "2 to pop a value off the stack\n"
      "3 to end program" );
    } // end function instructions
    
    // insert a node at the stack top
    void push( StackNodePtr *topPtr, int info ) { 
    StackNodePtr newPtr; // pointer to new node
    newPtr = malloc( sizeof( StackNode ) );
    
    // insert the node at stack top
    if ( newPtr != NULL ) {           
      newPtr->data = info;           
      newPtr->nextPtr = *topPtr;     
      *topPtr = newPtr;              
    } // end if                    
    else { // no space available
      printf( "%d not inserted. No memory available.\n", info );
    } // end else
    } // end function push
    
    // remove a node from the stack top
    int pop( StackNodePtr *topPtr ) { 
    StackNodePtr tempPtr; // temporary node pointer
    int popValue; // node value
    tempPtr = *topPtr;             
    popValue = ( *topPtr )->data;  
    *topPtr = ( *topPtr )->nextPtr;
    free( tempPtr );               
    return popValue;
    } // end function pop
    
    // print the stack
    void printStack( StackNodePtr currentPtr ) { 
    
    // if stack is empty
    if ( currentPtr == NULL ) {
      puts( "The stack is empty.\n" );
    } // end if
    else { 
      puts( "The stack is:" );
    
    // while not the end of the stack
     while ( currentPtr != NULL ) { 
         printf( "%d --> ", currentPtr->data );
         currentPtr = currentPtr->nextPtr;
      } // end while
      puts( "NULL\n" );
      } // end else
    } // end function printList
    
    // return 1 if the stack is empty, 0 otherwise
    int isEmpty( StackNodePtr topPtr )
    { 
    return topPtr == NULL;
    } // end function isEmpty


    Output:
    Enter choice:
    1 to push a value on the stack
    2 to pop a value off the stack
    3 to end program
   
    Enter choice: 1
    Enter an integer: 10
    The stack is:
    10 --> NULL
    
    Enter choice: 1
    Enter an integer: 15
    The stack is:
    15 --> 10 --> NULL
    
    Enter choice: 2
    The popped value is 15.
    The stack is:
    10 --> NULL

Note: to run the program you need to build first a main menu using the switch (choice) statement.

Ads Right