Stack data structure and applications

Stacks data structure

What is stack data structure? Stack is a dynamic data structure, where information is stack over one another. In common terminology, we use the stack with same meaning like stack of trays or stack of pancakes. Extend the concept of stack in real life, you remove the tray at the top before moving tray below it. So the tray which goes last on to stack, come off the stack first. This pattern is called as Last In First Out or LIFO.

For any data structure, three operations should be considered : How data can be added to it, how data can be removed from it and how data can be read from it? Let’s discuss these operations on stack one by one.

Operations on stack

Write operation on stack is commonly known as push. Push operation writes information on to top of the stack.Complexity of push operation is O(1) as no iteration is required.

Read operation is known as pop, where element at the top of stack is removed. Complexity of pop is also O(1).
stack data structure

Another operation which is commonly used is isEmpty(), this checks if there are any elements in stack at present.

What if you just want to check the top element of stack but do not want to remove it from stack? Then operation called peek() is for you. It reads the top element, however does not remove it from stack.

Since stack can dynamically increase and decrease in size based on push and pop operation, we need to keep track of the top of the stack.

Stack can be represented as recursive structure i.e if we remove the top of the stack, remaining N-1 element is again a stack.

Let’s take an example to see how push and pop operations on stack actually follow Last In First Out pattern.

stack data structure

Implementation of stack data structure

Stacks can be implemented in two ways, first where underlying data storage is an array and second where underlying storage is linked list. Refer difference between array and linkedlist to understand more that impacts stack implementation.

1. In Array based implementation of stack implementation, underlying data structure used is an array. We keep an extra variable (top) to keep track of number of elements present in stack at given time. When we push an element on to stack, increase the top. When we pop an element from stack, we decrease the top.

In this implementation, top being -1 represents empty stack and top equal to N-1, N being the size of array, represents stack full. Push and pop operations are of O(1) complexity.

Drawback of this implementation is that we need to define stack size statically at the compile time and changing it at runtime dynamically would be overhead.

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

#define STACK_SIZE 100

typedef struct stack{
        int top;
        int items[STACK_SIZE];
}stack;
 
void push(stack *ms, int item){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = item;
   }
   else {
       printf("Stack is full\n");
   }
}

//Get the element at the top of stack and remove it from stack
int pop (stack *ms){
   if(ms->top > -1 ){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}

//Get the element at the top of stack without removing it.
int peek(stack ms){
  if(ms.top < 0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}

//Function to check if stack is empty or not?
int isEmpty(stack ms){
   if(ms.top < 0) return 1;
   else return 0;
}

2. In Linked List based implementation of stack implementation, underlying data structure used is linked list. Every node in the linked list represents an element in stack. Every push operation adds a node at the head of linked list and every pop operation removes a node from head of the linked list.

In this implementation too, push and pop operations are of O(1) complexity. Also stack can grow as much as required. Head being NULL represents empty stack.

Drawback is we need to store 4 bytes extra as next pointer for each element.

#include <stdio.h>

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

typedef struct node{
    int data;
    struct node *next;
} Node;

/* Create a node of linked list */
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
 
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
    Node *newNode  = createNode(data);
    newNode->next = *headRef;
    *headRef  = newNode;
}

/* This function removes node from the head of linked list */
Node * pop(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    Node * poppedNode = *headRef;
    *headRef = (*headRef)->next;
    return poppedNode;
}

/* This function return node at the head of linked list */
Node * peek(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    return (*headRef);
} 

int isEmpty(Node **headRef){
    return (*headRef == NULL);
}

Stack Overflow

You must have heard the term stack overflow. Why does it occur and how does it relates to stack data structure?
Stack supports function call paradigm in programming languages. When a function in your program calls another function (which can be the same function in case of recursion), program management module in operating system stores quite a few things to have safe return. This includes : parameters passed to function, return values, return pointers. As you go deep into function calls, one function calling second, then second calling third and so on, each of this successive call takes a frame of system stack as explained above. Depending on the size of information you are putting on stack frame in each call, sooner or later, stack will be full, as it has limited memory allocated in kernel.

Now when you try to add one more frame because you are calling another function, there is no space. That’s when stack overflow happens.

Why do you think function call information is store on stack and not on any other data structure? Let’s say your program calls function A from function B, which in turn was called from function C. When you are returning from function A, you want to return to calling address in function B and not function C. So, you want to return back in reverse order of calling sequence, LIFO, that why stack is best data structure.

It is recommended to implement production code in iterative way rather than recursive using application level stacks. As application stack is allocated from heap, it can grow much bigger than kernel stack. Also, you can select what to put on stack. If you look at iterative preorder traversal, iterative postorder traversal interview problems, they are nothing but to test your knowledge of stack data structure. To read more on stack overflow, please refer : stack overflow

Application of stack : browser back button

Let’s solve a problem and see how stack data structure can be used to solve problems. Problem statement is : Implement back button on browser. When you click on back button, you go to previous site you visited. You press it again, than you go to site prior to it and so on.

Do you see application stack here? When you go back, you want to land on the last site you visited. What pattern is this? Of course, it last in first out which can be implemented using stack.
So idea is to whenever you move to new site or page, current page is added to stack. If you press back button, top of the stack is popped and return to you as current page. If you press again, top of the stack contains now the page you visited before current page, so land there.

browser back button using stack

There can one more complexity added to this problem, which is you want to implement forward button too. In that case, whenever you pop out a page from back stack, put it into a new stack called forward stack. Can you run through some examples and see if that actually works?

Please share if there is something wrong or missing. If you are interested in taking personal coaching by our experienced teachers, please reach out to us at communications@algorithmsandme.com