**Stacks data structure**

What comes to find when we first hear stack? A stack of books or stack of boxes.right? How can you take out a book from stack of books? Yes, by first removing all the books those are above desired book. Stack data structure has this unique property called as LIFO, last in first out. LIFO means whatever goes in first is last one to come out.Item that has gone first will be at the stack for longest. Stack data structure is used when you have to track all previous visited elements and process them in reverse them. This is typical in problems related to binary tree like non-recursive implementation of traversals of tree, parenthesis matching, print a word in reverse order etc. Whenever we encounter a problem which requires some sort of reversing on the already existing arrangement, we go for stacks.

**Basic operations allowed on stack data structure.**

1. Push() : With this operation, an element is added to stack.

2. Pop() : With this operation, element at the top of the stack is taken out.

Other operations which are commonly used during stack usage are :

1. isEmpty() : This checks if there are some elements present in stack.

2. peek(): This operation return the element at the top, but unlike pop, it does not remove element 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. Notice that, 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 see an example to understand reversal order of stack, that means whatever is entered in stack is taken out in reverse order.

This reversal property is used to maintain called and calling function relationships, web browsers back button history etc.

**Stack operations**

** Push operation **

1. Checks if the stack is full.This check applicable for fixed sized stacks, like array based implementation. 2. If stack is full, throw an error and exit. 3. If stack is not full, increment top. 4. Add new element to stack where top is pointing. 5. Returns success.

** Pop operation **

1. Checks if the stack is empty. 2. If stack is empty, throw an error and exit 3. If the stack is not empty, take element at the top. 4. Decrement top by 1. 5. Returns popped element.

**Implementation of stack data structure**

Stacks can be implemented in two ways : array based implementation and linked list based implementation.

** 1. Array based implementation of stack.**

In this 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 add an element to stack, we increase the top. When we pop an element from stack, we decrease the top.

In array based implementation of stack, 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.

#define STACK_SIZE 10 typedef struct stack{ int top; int items[STACK_SIZE]; }stack; void push(stack *ms, int element){ if(ms->top < STACK_SIZE-1){ ms->items[++(ms->top)] = element; } else { printf("Stack is full\n"); } } int pop (stack *ms){ if(ms->top > 0){ return ms->items[(ms->top)--]; } else{ printf("Stack is empty\n"); } } int peek(stack ms){ if(ms.top < 0){ printf("Stack empty\n"); return 0; } return ms.items[ms.top]; } int isEmpty(stack ms){ if(ms.top < 0) return 1; else return 0; }

Drawback of this implementation is that we need to define stack size before hand and increasing and decreasing dynamically would be overhead.

**2. Linked List based implementation of stack.**

In linked list base implementation of stack, 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 the linked list and every pop operation removes the node from the 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.

Stacks are used for supporting recursive paradigm in programming languages. During program management, parameters passed to functions, return values, return pointers are stored in stack.

typedef struct node{ int item; struct Node * next; }Node ; void push(Node **head, int element){ Node *newNode = (Node *)malloc(sizeof(Node)); if(!newNode){ newNode->item = element; newNode->next = *head; *head = newNode; } else{ printf("Node could not be allocated\n "); } } int pop(Node **head){ int element; if(!(*head)){ printf("Stack is empty\n"); return -1; } else{ Node *currentNode = *head; *head = (*head)->next; element = currentNode->item; free(currentNode); return element; } } int isEmpty(Node *head){ return (!head); } int peek(Node *head){ if(head) return head->item; else return -1; }

Problems which can be solved efficiently using stack data structure

1. Converting a decimal number to binary number.

2. Tower of Hanoi

3. Parenthesis matching.

4. Infix to postfix conversion

5. Tree traversals.

6. Stock span problem.

7. Implement queue with two stacks.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us.

Pingback: zig zag traversal of binary search tree – Algorithms and Me()

Pingback: Stock span problem implementation - Algorithms and Me()

Pingback: Implement queue data structure using array - Algorithms and Me()

Pingback: Next greater number for every element - Algorithms and Me()

Pingback: Next greater number in array - Algorithms and Me()