.png)
In this blog, we will discuss the most common topic Stacks. It is very very important in the placement point of view.
Introduction to Stacks
A Stack is s linear data structure(abstract data type) that follows a particular order in which the operations are performed.
The order may be LIFO(Last In First Out) or FILO(First In Last Out).
LIFO order says that the element which is inserted at the end in the Stack will be the first to be removed. This means insertion takes place at the rear end of the stack and deletion occurs at the front of the stack.
FILO order says that the element which is inserted at the first in the Stack will be the last one to be removed. In FILO order insertion takes place at the rear end of the stack and deletion occurs at the front of the stack.
There are three basic operations performed in the stack:
Push: Adds an element in the stack. If it is full then it is said to be an Overflow condition.
Pop: Removes an element from the stack. The items are popped in reversed order in which they are being pushed. If it is empty, then it is said to be an Underflow condition.
Peek or Top: It returns the top element of the stack.
isEmpty: Returns true if the stack is empty, else false.
Time Complexities of operations on stack: The operations push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.
Implementation: There are two ways to implement a stack.
Using array
Using a linked list
Implementing Stack using Arrays:
#include <stdio.h>
#define CAPACITY 10
#define STACKOVERFLOW -99
#define STACKUNDERFLOW -100
int s[CAPACITY];
int tos=-1;
//checks if the stack is empty or not
//if empty, then return 1 , else return 0
int isEmpty()
{
if(tos==-1)
return 1;
return 0;
}
//checks if the stack is full or not
//if full, then return 1 , else return 0
int isFull()
{
if(tos==CAPACITY-1)
return 1;
return 0;
}
int push(int element)
{
if(isFull())
return STACKOVERFLOW;
tos++;
s[tos]=element;
return 1;
}
int pop()
{
int result;
if(isEmpty())
return STACKUNDERFLOW;
result=s[tos];
tos--;
return result;
}
int peek()
{
if(isEmpty())
return STACKUNDERFLOW;
return s[tos];
}
int main()
{
int choice,ele;
do{
printf("\nEnter your choice : 1.Push 2.Pop 3.Peek 4.Exit");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter element");
scanf("%d",&ele);
int r=push(ele);
if(r==1)
printf("\nPush Successful");
else
printf("\nStack Overflow");
break;
case 2:
r=pop();
if(r==STACKUNDERFLOW)
printf("\nStack underflow");
else
printf("\n%d popped ",r);
break;
case 3:
r=peek();
if(r==STACKUNDERFLOW)
printf("\nStack underflow");
else
printf("\nTop of stack element=%d",r);
break;
case 4:
exit(0);
}
}while(1);
return 0;
}Pros: Easy to implement. Memory is saved as pointers are not involved.
Cons: It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.
Implementing Stack using Linked List:
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;
void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;
}
printf("Item pushed");
}
}
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}Pros: The linked list implementation of the stack can grow and shrink according to the needs at runtime.
Cons: Requires extra memory due to the involvement of pointers.
Applications of the stack:
Infix to Postfix/Prefix conversion.
Stacks can be used to check for the balancing of parenthesis in an expression.
Redo-undo features at many places like editors, photoshop.
Forward and backward feature in web browsers
Implementing Stack using built-in-classes
Stack in C++ STL:
The C++ STL offers a built-in-class named stack for implementing the stack data structure easily and efficiently.
It offers almost all functions needed to perform the standard stack operation like push(), pop(), peek(), remove() etc..
Syntax:
stack< data_Type > stack_Name;
Here,
data_Type: This defines the type of data to be
stored in the stack.
stack_Name: This specifies the name of the stack.Some Basic functions of Stack class in C++:
push(e) – Adds the element ‘e’ at the top of the stack.
pop() – Deletes the topmost element of the stack.
empty() – Returns whether the stack is empty.
size() – Returns the size of the stack.
top() – Returns a reference to the topmost element of the stack.
All of the above functions work in O(1) time complexity.
Implementation:
#include <iostream>
#include <stack>
using namespace std;
void printStack(stack <int> s)
{
while (!s.empty())
{
cout << '\t' << s.top();
s.pop();
}
cout << '\n';
}
int main ()
{
stack <int> s;
s.push(100);
s.push(300);
s.push(200);
s.push(50);
s.push(10);
cout << "The stack is : ";
printstack(s);
cout << "\ns.size() : " << s.size();
cout << "\ns.top() : " << s.top();
cout << "\ns.pop() : ";
s.pop();
printstack(s);
return 0;
} Output:
The stack is : 10 50 200 300 100
s.size() : 50
s.top() : 10
s.pop() : 50 200 300 100Stack class in Java:
Java Collection framework provides a Stack class that models and implements the Stack data structure.
In addition to the basic push and pop operations, the class provides three more functions of empty, search, and peek.
The class can also be said to extend Vector and treats the class as a stack with the five mentioned functions. The class can also be referred to as the subclass of Vector.
The class supports one default constructor Stack()which is used to create an empty stack.
Creating a Stack
In order to create a stack, we must import the java.util.Stack package first. After importing,
Stack <Type> stacks = new Stack<>();Methods in Stack class:
Object push(Object element): Pushes an element on the top of the stack.
Object pop(): Removes and returns the top element of the stack. An 'EmptyStackException' exception is thrown if we call pop() when the invoking stack is empty.
Object peek(): Returns the element on the top of the stack, but does not remove it.
int search(Object element): It determines whether an object exists in the stack. If the element is found, it returns the position of the element from the top of the stack. Else, it returns -1.
boolean empty(): It returns true if nothing is on the top of the stack. Else, returns false.
Implementation:
import java.io.*;
import java.util.Stack;
class Main{
public static void main(String[] args){
Stack<String> tech = new Stack<>();
tech.push("PC");
tech.push("Mouse");
tech.push("Keyboard");
System.out.println("Initial Stack: "+ tech);
String ele = tech.pop();
System.out.println("Removed Element: "+ ele);
String ele1 = tech.peek();
System.out.pritln("Element at the top: "+ ele1);
int pos = tech.search("Mouse");
System.out.pritln("Position of Mouse" "+pos);
boolean res = tech.empty();
System.out.pritln("Is stack empty? "+res);
}
}Output:
Initial Stack: [PC, Mouse, Keyboard]
Removed Element: Keyboard
Element at the top: Mouse
Position of Mouse: 2
Is stack empty? falseHappy Coding!
Follow us on Instagram @programmersdoor
Join us on Telegram @programmersdoor
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Follow Programmers Door for more.