Day 38 - Implementation of Stack Data Structure
What all did we see till now?
Now that we are proceeding towards the phase 2 of Daily Codes initiative, here are the things that we focused on phase 1,
- Basic questions
- String Manipulation programs
- Recursion
- Array based programs
- Time and space complexity in various programs
- Searching algorithms
- Sorting algorithms
- Applications based on searching and sorting algorithms
Help us improve
It’s been a long journey, and I hope the people who are following this initiative daily are getting benefitted. Moreover, we would love to have your valuable feedback, and suggestions
Just comment on issue #244 - https://github.com/CodeToExpress/dailycodebase/issues/244 - whatever you would like us to know
Thanks for being a part, we love you all. Let’s make this world a better place through code
Today’s question - Implement a Stack
Stack is a linear data structure which 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)
There are many real-life examples of a stack, like a stack of books, where you can add another book at top and remove the book at the top. Another example can be a stack of plates kept one over the other in the kitchen, one can remove the plate kept at top and remove the element kept at the top.
A stack has various methods -
isEmpty()- To check whether the stack is emptyisFull()- To check whether the stack is fullpush()- To add a new element to the stackpop()- To remove the topmost element from the stackpeek()- To view the topmost element in the stack
Try to implement a stack 😁
Solution
JavaScript Implementation
Solution 1
Implementation by using JS’s array push and pop methods
/**
* Implemntation of Stack Data Structure in JavaScript
* @author MadhavBahl
* @date 11/02/2019
* Method 1 - Using JavaScript's push and pop methods
*/
class Stack {
// constructor to initialize the stack and it's capacity
constructor (limit) {
this.myStack = [];
this.top = limit;
}
// isEmpty method to check whether the stack is empty
isEmpty () {
if (this.myStack.length === 0) return true;
else return false;
}
// isFull method to check whether the stack is full
isFull () {
if (this.myStack.length === this.top) return true;
else return false;
}
// push method to add a record to the stack
push (record) {
if (!this.isFull()) {
console.log (`Pushing ${record} to the stack!`);
this.myStack.push (record);
} else {
console.log ('Sorry! The Stack is full!');
}
}
// pop method to remove an element from the stack
pop () {
if (!this.isEmpty()) {
console.log (`Popped element is: ${this.myStack[this.myStack.length-1]}`);
return this.myStack.pop ();
} else {
console.log ('Sorry! The Stack is empty');
}
}
// peek method to view the top element
peek () {
console.log (`Current element is: ${this.myStack[this.myStack.length - 1]}`);
}
}
const stk = new Stack (10);
stk.pop ();
stk.push (1);
stk.push (2);
stk.pop ();
stk.peek ();
Solution 2
Implementation without using JS’s array push and pop methods
/**
* Implemntation of Stack Data Structure in JavaScript
* @author MadhavBahl
* @date 11/02/2019
* Method 2 - Stack implementation from scratch (without push() and pop() methods)
*/
class Stack {
// Constructor function to initialize the stack
constructor (capacity) {
this.myStack = [];
this.cap = capacity;
this.first = 0;
this.last = 0;
this.size = -1;
}
// isEmpty() method to check whether the stack is empty
isEmpty () {
if (this.size === -1) return true;
return false;
}
//isFull() method to check whether the stack is full
isFull () {
if (this.size === this.cap -1) return true;
return false;
}
// push() method to add an element to the stack
push (element) {
if (this.isFull()) {
console.log ('OVERFLOW!');
return 0;
}
console.log (`Pushing ${element} to the stack!`);
this.size++;
this.myStack[this.size] = element;
return 1;
}
// pop() method to remove topmost element
pop () {
if (this.isEmpty()) {
console.log ('UNDERFLOW!');
return 0;
}
console.log (`Popped element is: ${this.myStack[this.size]}`);
this.size--;
return 1;
}
// peek() method to view the toopmost element
peek () {
if (this.isEmpty()) {
console.log ('Stack is empty!');
return 0;
}
console.log (`Current Element is: ${this.myStack[this.size]}`);
}
}
const stk = new Stack (10);
stk.pop ();
stk.push (1);
stk.push (2);
stk.pop ();
stk.peek ();
Java Implementation
Solution
/**
* @date 11/02/19
* @author SPREEHA DUTTA
*/
import java.util.*;
public class Stack {
static int st[]=new int[5];
static int top=0;
public static void push(int n)
{
if(top<5)
{
st[top]=n;
top++;
}
else
isFull();
}
public static void pop()
{
if(top<=5 && top>0)
{
top--;
System.out.println("Popped element is "+st[top]);
}
else
isEmpty();
}
public static void isEmpty()
{
if(top<=0)
System.out.println("Stack is empty");
}
public static void isFull()
{
if(top>=5)
System.out.println("Stack is full");
}
public static void peek()
{
if(top-1>=0 && top-1<5)
System.out.println("The topmost element of the stack is "+st[top-1]);
else
System.out.println("Stack is empty");
}
public static void display()
{
System.out.println("All the elements present in the stack are:");
for(int i=0;i<top;i++)
System.out.print(st[i]+" ");
System.out.println();
}
public static void main(String []args)
{
Scanner sc=new Scanner(System.in);
int ch;int c=0;
do
{
c=0;
System.out.println("Enter choice ");
System.out.println("1. Add new element"
+ "\n"+"2. Remove topmost eleemnt"
+"\n3. To view the topmost element"+"\n4. To view all the elements");
ch=sc.nextInt();
switch(ch)
{
case 1:
System.out.println("Enter element to be added to stack ");
int n=sc.nextInt();
push(n);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
default:
System.out.println("Invalid choice :");
}
System.out.println("Enter 1 if you wish to continue");
c=sc.nextInt();
}
while(c==1);
}
}
C++ Implementation
Solution by @profgrammer
/*
* @author profgrammer
* @date 17-2-2019
*/
#include <bits/stdc++.h>
using namespace std;
class MyStack{
private:
int top;
int stack[100];
int size;
public:
MyStack(int _size){
top = -1;
size = _size;
}
bool isEmpty(){
return top == -1;
}
bool isFull(){
return top == size - 1;
}
int peek(){
if(isEmpty()) {cout<<"Stack empty..\n"; return -1;}
return stack[top];
}
void push(int x){
if(isFull()) cout<<"Stack full..\n";
else stack[++top] = x;
}
void pop(){
if(isEmpty()) cout<<"Stack empty..\n";
else top--;
}
};
int main(){
MyStack stack(2);
stack.push(1);
stack.push(2);
stack.push(3); // err
cout<<stack.peek()<<endl;
stack.pop();
stack.pop();
stack.pop(); // err
cout<<stack.peek()<<endl;
}