Stack Program in C (Introduction)

Introduction to Stack

A stack is another type of Data Structure, generally implemented using arrays. Generally, the implementation is LIFO i.e. Last in First out, also used for FILO, i.e. First in Last out

Stacks

More about Stacks

  • Stack can be defined as a Data Structure that serves as saving the data in a particular fashion.
  • In linear data structures like an array and linked list a user is allowed to insert or delete any element to and from any location respectively.
  • However, in a Stack, both, insertion and deletion, is permitted at one end only.
  • A Stack works on the LIFO (Last In – First Out) basis, i.e, the first element that is inserted in the stack would be the last to be deleted; or the last element to be inserted in the stack would be the first to be deleted.

Stack Operations

  • Push: Adding a new item to the Stack Data Structure, in other words pushing new item to Stack DS.

If Stack is full, then it is said to be in an overflow condition

  • Pop: Removing an item from the stack, i.e. popping an item out.

If a stack is empty then it is said to be in an underflow condition

  • Peek: This basically returns the topmost item in the stack, in other words, peek that what is the topmost item.
  • IsEmpty: This returns True If the stack is empty else returns False

Representation of stack.

Stack as a data structure can be represented in two ways.

  • Stack as an Array.
  • Stack as a struct
  • Stack as a Linked List.

Operations on a Stack

There are a number of operations we can perform on a stack as per our need which are as follows:

  • Push().
  • Pop().
  • Top/Peak().
  • isEmpty().
The time complexity of each of these operations is constant time, i.e , O(1).

1. Push()

  • When we require to add an element to the stack we perform Push() operation.
  • Push() operation is synonymous of insertion in a data structure.

2. Pop()

  • When we require to remove an element to the stack we perform Pop() operation.
  • Pop() operation is synonymous of deletion in a data structure.

3. Top()

  • This operation returns the top most or peak element of the stack.
  • The value of top changes with each push() or pop() operation.

4. isEmpty()

  • This operation returns true if the stack is found to be empty.
  • Empty stack symbolizes that top = -1.

How stack works?

  • Top: An integer variable Top is used, to keep track of topmost element in the stack
  • When we initialise the stack, there is no element in a stack so, Top value is initialised to Top = -1 
  • The value is -1 as if use an array to implement stack if there is 1 element the location would be a[0], thus, for no element we use – 1.
  • Push: on pushing new element the Top value increments by 1, top++
  • Pop: on popping a new element the top value decrements by 1, top–
  • Before pushing we check if the stack is full or not
  • Before popping we check if the stack is empty or not

Code for Stack in C Program (using structure)

// C Program for Implmentation of stack (array) using structure
#include  <limits.h>
#include  <stdio.h>
#include  <stdlib.h>
  
// A structure to represent a stack 
struct Stack { 
    int top; 
    int maxSize; 
    int* array; 
}; 

struct Stack* create(int max) 
{ 
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); 
    stack->maxSize = max; 
    stack->top = -1; 
    stack->array = (int*)malloc(stack->maxSize * sizeof(int));
    //here above memory for array is being created
    // size would be 10*4 = 40
    return stack; 
} 

// Checking with this function is stack is full or not
// Will return true is stack is full else false 
//Stack is full when top is equal to the last index 
int isFull(struct Stack* stack) 
{ 
    if(stack->top == stack->maxSize - 1){
        printf("Will not be able to push maxSize reached\n");
    }
    // Since array starts from 0, and maxSize starts from 1
    return stack->top == stack->maxSize - 1; 
} 
  
// By definition the Stack is empty when top is equal to -1 
// Will return true if top is -1
int isEmpty(struct Stack* stack) 
{ 
    return stack->top == -1; 
}

// Push function here, inserts value in stack and increments stack top by 1
void push(struct Stack* stack, int item) 
{ 
    if (isFull(stack)) 
        return; 
    stack->array[++stack->top] = item; 
    printf("We have pushed %d to stack\n", item); 
}

// Function to remove an item from stack.  It decreases top by 1 
int pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top--]; 
} 
  
// Function to return the top from stack without removing it 
int peek(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top]; 
} 

int main()
{
struct Stack* stack = create(10); 
  
    push(stack, 5); 
    push(stack, 10); 
    push(stack, 15);
    
    int flag=1;
    while(flag)
    {
        if(!isEmpty(stack))
            printf("We have popped %d from stack\n", pop(stack));
        else
            printf("Can't Pop stack must be empty\n");
            
            printf("Do you want to Pop again? Yes: 1 No: 0\n");
            scanf("%d",&flag);
    }
    return 0;
}

O/P

We have pushed 5 to stack                         
We have pushed 10 to stack
We have pushed 15 to stack
We have popped 15 from the stack
Do you want to Pop again? Yes: 1 No: 0

Understanding the concept of Stack

Let us understand the concept of Stack. As we have learned about stack above, it stores the data in a particular fashion where the element can only be inserted or deleted at one end only.

Let us consider a stack of books as shown in the image. 

  • This pile of books would have been formed by placing one book on the other like first the blue book and then on top of it the red book then on top of the red book came the yellow book and so on.
  • The functioning of the Stack is similar to this.
  • If we look at the stack in the image.
    • First the element 42 would have been added to an empty stack.
    • Then on the top of it, the second element 18 would be added.
    • On the top of 18, the next element 12 would have been added and so on.
  • Similarly, if we pick out the books out of the stack we will have to begin from top. For instance if we want to remove the yellow book we will have to first remove the pink book, then the blue book and then the green book and then we will finally be able to remove the yellow book.
  • Same happens in the case of the stack. To delete the element 12 , we will have to first remove 22 then 34 and then we can delete the element 12.
  • With this example we can be certain that a stack structure works on a LIFO basis, i.e , the last element to be inserted would be deleted first.