Implementation of stack
Implementation of stack: The stack can be implemented in two ways: using array and using a linked list. The pop and push operations in the array are simpler than the linked list. But dynamic memory allocation is not possible with the array.
Push operation
Push operation is used to insert a new element in the stack.
In case, the array is full, and no new item can be added in the array. This condition is also called an OVERFLOW (STACK_FULL).
Algorithm of the push operation
Step 1: Check whether the stack is full. Step 2: If the stack is full, it will print the "overflow" message, and the program will terminate. Step 3: If the stack is not full, the stack-array will increment [top + 1], and a new item will be added to the stack-array. |
// Assuming that array can hold maximum N element Top = -1 Read item // item, which is to be pushed if (Top == size - 1) then // if top is at end of stack-array { print (“overflow”); } else { Top++; // increment top to move to next empty position to hold new item Stack [Top] = element; } end
Pop operation
Pop operation is used to delete an element in the stack.
In case, the last item is popped, the stack becomes empty. If one tries to delete an item from an empty stack, this condition is also called an UNDERFLOW (STACK_EMPTY).
Algorithm of the pop operation
Step 1: Check whether the stack is empty. Step 2: If the stack is empty, it will print the "underflow" message, and the program will terminate. Step 3: If the stack is not empty, the delete-item will be printed, and the top will contain a decrement [top - 1].
// firstly, check for underflow condition if top == -1 then{print(“underflow”); // exit the program } else { element = stack[top]Top --; } end
Peek operation
When the data is received from a particular location in the stack, that operation is called peep operation.
Algorithm of peek operation
PEEK (STACK, TOP) Begin if top = -1 then stack empty item = stack[top] return item End
Stack program in C language:
#include <stdio.h> #include <stdlib.h> #define MAX 10 int count = 0; // Creating a stack struct stack { int items[MAX]; int top; }; typedef struct stack st; void createEmptyStack(st *s) { s->top = -1; } // Check if the stack is full int isfull(st *s) { if (s->top == MAX - 1) return 1; else return 0; } // Check if the stack is empty int isempty(st *s) { if (s->top == -1) return 1; else return 0; } // Add elements into stack void push(st *s, int newitem) { if (isfull(s)) { printf("STACK FULL"); } else { s->top++; s->items[s->top] = newitem; } count++; } // Remove element from stack void pop(st *s) { if (isempty(s)) { printf("\n STACK EMPTY \n"); } else { printf("Item popped= %d", s->items[s->top]); s->top--; } count--; printf("\n"); } // Print elements of stack void printStack(st *s) { printf("Stack: "); for (int i = 0; i < count; i++) { printf("%d ", s->items[i]); } printf("\n"); } // Driver code int main() { int ch; st *s = (st *)malloc(sizeof(st)); createEmptyStack(s); push(s, 1); push(s, 3); push(s, 4); printStack(s); pop(s); printf("\nAfter popping out\n"); printStack(s); }