Stacks

‘Stack’ data structure is also known as ‘Last In First Out’ (LIFO) data structure. Stack is an abstract data type which serves as the collection of elements, with the two principle operations:-

i. PUSH : adds an element to collection
ii. POP : removes the last element that was added to the collection

Time complexity for both of these functions is O(1) since these operations are performed only at the end of the stack (i.e. only on one location or element).
Since these operations are done at the end of this collection of data, stack is considered as ‘linear data structure’.



A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items or results in an empty stack, but, if the stack is empty, it goes into underflow state, which means no items are present in stack to be removed.

Stack can be implemented using:
i. Arrays
ii. Singly linked lists

In the implementation of stack, I have used singly linked list.

Applications of Stack
1. Converting decimal number into binary number
2. Towers of Hanoi
3. Expression evaluation and syntax parsing
4. Rearranging railroad cars
5. Quicksort
6. The stock span problem
7. Backtracking
8. Runtime memory management


Implementation of stack (Using singly linked list)

Code:
 
#include "stdio.h"
#include "stdlib.h"
 
struct stack{
                int num;
                struct stack *below;
};
 
int size, currentsize;
 
void Push(struct stack **newstack){
                struct stack *ptr = NULL;
                if(currentsize == size){
                                printf("\nError: stack is full!!");
                }
                else{
                                ptr = (struct stack*)malloc(sizeof(struct stack));
                                printf("\nEnter value to be pushed onto the stack: ");
                                scanf("%d", &ptr->num);
                               
                                if(*newstack == NULL){
                                                ptr->below = NULL;                       
                                }
                                else{
                                                ptr->below = *newstack;
                                }
                                *newstack = ptr;
                                currentsize++;
                }
}
 
void GetStackData(struct stack *newstack){
                struct stack *ptr = newstack;
                if(ptr == NULL){
                                printf("\nError: stack is empty!!");
                }
                else{
                                printf("\nStack is as follows: ");
                                while(ptr!=NULL){
                                                printf("\n| %d |", ptr->num);
                                                printf("\n-----");
                                                ptr = ptr->below;
                                }
                }
}
 
void Pop(struct stack **newstack){        
                if(*newstack == NULL){
                                printf("\nError: stack is empty!!");
                }
                else{
                                struct stack *ptr = *newstack;
                                printf("\n%d is popped out of the stack", ptr->num);
                                if(ptr->below == NULL){
                                                *newstack = NULL;
                                }
                                else{
                                                *newstack = ptr->below;
                                }
                                currentsize--;
                }
}
 
void main(){
                struct stack *newstack = NULL;
                int option;
                char con, c;
               
                do{
                                printf("\nWhat is the size of stack ?: ");
                                scanf("%d", &size);
                                newstack = NULL;
                                currentsize = 0;
                               
                                do{
                                                printf("\n\nWhat do you want to do?");
                                                printf("\n1. Push\n2. Pop\n3. Get size\n4. GetStackData\n5. Exit\nOption : ");
                                                scanf("%d", &option);
                                               
                                                switch(option){
                                                                case 1:
                                                                                Push(&newstack);
                                                                                break;
                                                                case 2:
                                                                                Pop(&newstack);
                                                                                break;
                                                                case 3:
                                                                                printf("\nSize of the stack is %d", currentsize);
                                                                                break;
                                                                case 4:
                                                                                GetStackData(newstack);
                                                                                break;
                                                                case 5:
                                                                                goto exit;
                                                                                break;
                                                                default:
                                                                                break;  
                                                }
                                }while(1);
                               
                                exit:
                                               
                                printf("\nDo you want to continue (y/n) ?:");
                                getchar();
                                con = getchar();
                }while(con == 'y' || con == 'Y');
               
}
 
 

Output:
 
What is the size of stack ?: 3
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 1
 
Enter value to be pushed onto the stack: 10
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 1
 
Enter value to be pushed onto the stack: 20
  
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 1
 
Enter value to be pushed onto the stack: 30
  
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 1
 
Error: stack is full!!
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 3
 
Size of the stack is 3
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 4
 
Stack is as follows:
| 30 |
-----
| 20 |
-----
| 10 |
-----
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 2
 
30 is popped out of the stack
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 4
 
Stack is as follows:
| 20 |
-----
| 10 |
-----
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 2
 
20 is popped out of the stack
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 2
 
10 is popped out of the stack
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 2
 
Error: stack is empty!!
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 3
 
Size of the stack is 0
 
What do you want to do?
1. Push
2. Pop
3. Get size
4. GetStackData
5. Exit
Option : 5
 
Do you want to continue (y/n) ?:n

No comments :

Post a Comment