Check if two stacks are equal
The task is to check if two stacks are equal, i.e., they contain the same elements in the same order.
Problem Statement
Given two stacks s1
and s2
, the task is to determine whether they are equal or not.
Example
Consider the following two stacks:
s1: 1 2 3
s2: 1 2 3
Both s1
and s2
are equal as they contain the same elements in the same order.
Another example:
s1: 4 3 1
s2: 5 1 1
In this case, s1
and s2
are not equal as they contain different elements.
Idea to Solve the Problem
To check if two stacks are equal, we can follow the following approach:
- Compare the sizes of the two stacks. If they have different sizes, they cannot be equal, so return
false
. - Create two backup stacks
b1
andb2
to store the elements temporarily. - While both
s1
ands2
are not empty, compare the top elements of both stacks. a. If the top elements are different, set a flagstatus
tofalse
, indicating that the stacks are not equal. b. Otherwise, push the top elements intob1
andb2
, and pop them froms1
ands2
. - After the comparison, restore the original stacks
s1
ands2
by pushing the elements back fromb1
andb2
. - Return the value of
status
, which indicates whether the stacks are equal or not.
Pseudocode
Function compareStack(s1, s2):
If s1.getSize() is not equal to s2.getSize():
Return false
Create two empty stacks b1 and b2
Set status as true
While s1 and s2 are not empty and status is true:
If s1.peek() is not equal to s2.peek():
Set status as false
Else:
Push s1.peek() into b1 and s2.peek() into b2
Pop elements from s1 and s2
While b1 is not empty:
Push b1.peek() into s1 and b2.peek() into s2
Pop elements from b1 and b2
Return status
Algorithm
- Create two empty stacks
s1
ands2
. - Push elements into
s1
ands2
. - Create an object of class
Compares
calledtask
. - Perform the following operations:
a. Print the elements of
s1
ands2
using theprintStack()
function of thetask
object. b. Iftask.compareStack(s1, s2)
istrue
, print "Stacks are equal." c. Otherwise, print "Stacks are not equal." - Push elements into
s1
ands2
. - Repeat the above operations to compare
s1
ands2
again.
Code Solution
/*
C Program
Check if two stacks are equal
*/
#include <stdio.h>
#include <stdlib.h>
// Define stack node
struct StackNode
{
int element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
// Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = stack->top;
}
// Add stack element
stack->top = node;
stack->size++;
}
// return top element of stack
int peek(struct MyStack *stack)
{
return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Determine that given stacks are equal or not
int compareStack(struct MyStack*s1,struct MyStack*s2)
{
if(s1->size != s2->size)
{
// When number of elements are not same
return 0;
}
// This is backup stack
struct MyStack*b1=newStack();
struct MyStack*b2=newStack();
int status = 1;
// When both stack contains elements
// And status are active
while(isEmpty(s1)==0 && isEmpty(s2)==0 && status == 1)
{
if(peek(s1) != peek(s2))
{
// When data elements are not same
status = 0;
}
else
{
// Backup the actual elements
push(b1,peek(s1));
push(b2,peek(s2));
// Remove top element of stack
pop(s1);
pop(s2);
}
}
// Puts the all pop element into actual stack
while(isEmpty(b1)==0)
{
push(s1,peek(b1));
push(s2,peek(b2));
pop(b1);
pop(b2);
}
return status;
}
// Print stack element
void printData(struct MyStack *s)
{
if(isEmpty(s)==1)
{
return;
}
int data = peek(s);
printf(" %d", data);
pop(s);
printData(s);
push(s,data);
}
// Handle request to print stack elements
void printStack(struct MyStack*s1,struct MyStack*s2)
{
printf("\n Stack 1 \n");
printData(s1);
printf("\n Stack 2 \n");
printData(s2);
}
int main()
{
// Create two empty stack
struct MyStack*s1 = newStack();
struct MyStack*s2 = newStack();
// First stack
push(s1,1);
push(s1,2);
push(s1,3);
// Second stack
push(s2,1);
push(s2,2);
push(s2,3);
printStack(s1,s2);
if(compareStack(s1,s2)==1)
{
printf("\n Stack are equal\n");
}
else
{
printf("\n Stack are not equal\n");
}
push(s1,4);
push(s2,5);
printStack(s1,s2);
if(compareStack(s1,s2)==1)
{
printf("\n Stack are equal\n");
}
else
{
printf("\n Stack are not equal\n");
}
return 0;
}
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 2 1
Stack 2
5 3 2 1
Stack are not equal
/*
Java Program for
Check if two stacks are equal
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
public int getSize()
{
return this.size;
}
}
public class Compares
{
// Determine that given stacks are equal or not
public boolean compareStack(MyStack s1, MyStack s2)
{
if (s1.getSize() != s2.getSize())
{
// When number of elements are not same
return false;
}
// This is backup stack
MyStack b1 = new MyStack();
MyStack b2 = new MyStack();
boolean status = true;
// When both stack contains elements
// And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
{
if (s1.peek() != s2.peek())
{
// When data elements are not same
status = false;
}
else
{
// Backup the actual elements
b1.push(s1.peek());
b2.push(s2.peek());
// Remove top element of stack
s1.pop();
s2.pop();
}
}
// Puts the all pop element into actual stack
while (b1.isEmpty() == false)
{
s1.push(b1.peek());
s2.push(b2.peek());
b1.pop();
b1.pop();
}
return status;
}
// Print stack element
public void printData(MyStack s)
{
if (s.isEmpty() == true)
{
return;
}
int data = s.peek();
System.out.print(" " + data );
s.pop();
printData(s);
s.push(data);
}
// Handle request to print stack elements
public void printStack(MyStack s1, MyStack s2)
{
System.out.print("\n Stack 1 \n");
printData(s1);
System.out.print("\n Stack 2 \n");
printData(s2);
}
public static void main(String[] args)
{
// Create two empty stack
MyStack s1 = new MyStack();
MyStack s2 = new MyStack();
Compares task = new Compares();
// First stack
s1.push(1);
s1.push(2);
s1.push(3);
// Second stack
s2.push(1);
s2.push(2);
s2.push(3);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
System.out.print("\n Stack are equal\n");
}
else
{
System.out.print("\n Stack are not equal\n");
}
s1.push(4);
s2.push(5);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
System.out.print("\n Stack are equal\n");
}
else
{
System.out.print("\n Stack are not equal\n");
}
}
}
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Check if two stacks are equal
*/
// Define stack node
class StackNode
{
public:
int element;
StackNode *next;
StackNode(int element, StackNode *top)
{
this->element = element;
this->next = top;
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
delete temp;
temp = NULL;
this->size--;
}
}
// return top element of stack
int peek()
{
if (this->top == NULL)
{
return -1;
}
return this->top->element;
}
int getSize()
{
return this->size;
}
};
class Compares
{
public:
// Determine that given stacks are equal or not
bool compareStack(MyStack s1, MyStack s2)
{
if (s1.getSize() != s2.getSize())
{
// When number of elements are not same
return false;
}
// This is backup stack
MyStack b1 = MyStack();
MyStack b2 = MyStack();
bool status = true;
// When both stack contains elements
// And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
{
if (s1.peek() != s2.peek())
{
// When data elements are not same
status = false;
}
else
{
// Backup the actual elements
b1.push(s1.peek());
b2.push(s2.peek());
// Remove top element of stack
s1.pop();
s2.pop();
}
}
// Puts the all pop element into actual stack
while (b1.isEmpty() == false)
{
s1.push(b1.peek());
s2.push(b2.peek());
b1.pop();
b1.pop();
}
return status;
}
// Print stack element
void printData(MyStack s)
{
if (s.isEmpty() == true)
{
return;
}
int data = s.peek();
cout << " " << data;
s.pop();
this->printData(s);
s.push(data);
}
// Handle request to print stack elements
void printStack(MyStack s1, MyStack s2)
{
cout << "\n Stack 1 \n";
this->printData(s1);
cout << "\n Stack 2 \n";
this->printData(s2);
}
};
int main()
{
// Create two empty stack
MyStack s1 = MyStack();
MyStack s2 = MyStack();
Compares task = Compares();
// First stack
s1.push(1);
s1.push(2);
s1.push(3);
// Second stack
s2.push(1);
s2.push(2);
s2.push(3);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
cout << "\n Stack are equal\n";
}
else
{
cout << "\n Stack are not equal\n";
}
s1.push(4);
s2.push(5);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
cout << "\n Stack are equal\n";
}
else
{
cout << "\n Stack are not equal\n";
}
return 0;
}
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 2 1
Stack 2
5 3 2 1
Stack are not equal
// Include namespace system
using System;
/*
C# Program for
Check if two stacks are equal
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
public int getSize()
{
return this.size;
}
}
public class Compares
{
// Determine that given stacks are equal or not
public Boolean compareStack(MyStack s1, MyStack s2)
{
if (s1.getSize() != s2.getSize())
{
// When number of elements are not same
return false;
}
// This is backup stack
MyStack b1 = new MyStack();
MyStack b2 = new MyStack();
Boolean status = true;
// When both stack contains elements
// And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
{
if (s1.peek() != s2.peek())
{
// When data elements are not same
status = false;
}
else
{
// Backup the actual elements
b1.push(s1.peek());
b2.push(s2.peek());
// Remove top element of stack
s1.pop();
s2.pop();
}
}
// Puts the all pop element into actual stack
while (b1.isEmpty() == false)
{
s1.push(b1.peek());
s2.push(b2.peek());
b1.pop();
b1.pop();
}
return status;
}
// Print stack element
public void printData(MyStack s)
{
if (s.isEmpty() == true)
{
return;
}
int data = s.peek();
Console.Write(" " + data);
s.pop();
printData(s);
s.push(data);
}
// Handle request to print stack elements
public void printStack(MyStack s1, MyStack s2)
{
Console.Write("\n Stack 1 \n");
printData(s1);
Console.Write("\n Stack 2 \n");
printData(s2);
}
public static void Main(String[] args)
{
// Create two empty stack
MyStack s1 = new MyStack();
MyStack s2 = new MyStack();
Compares task = new Compares();
// First stack
s1.push(1);
s1.push(2);
s1.push(3);
// Second stack
s2.push(1);
s2.push(2);
s2.push(3);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
Console.Write("\n Stack are equal\n");
}
else
{
Console.Write("\n Stack are not equal\n");
}
s1.push(4);
s2.push(5);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
Console.Write("\n Stack are equal\n");
}
else
{
Console.Write("\n Stack are not equal\n");
}
}
}
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
<?php
/*
Php Program for
Check if two stacks are equal
*/
// Define stack node
class StackNode
{
public $element;
public $next;
function __construct($element, $top)
{
$this->element = $element;
$this->next = $top;
}
}
// Define a custom stack
class MyStack
{
public $top;
public $size;
function __construct()
{
//Set node values
$this->top = null;
$this->size = 0;
}
// Add node at the top of stack
public function push($element)
{
$this->top = new StackNode($element, $this->top);
$this->size++;
}
public function isEmpty()
{
if ($this->size > 0 && $this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public function pop()
{
if ($this->size > 0 && $this->top != null)
{
$temp = $this->top;
// Change top element of stack
$this->top = $temp->next;
// remove previous top
$temp = null;
$this->size--;
}
}
// return top element of stack
public function peek()
{
if ($this->top == null)
{
return -1;
}
return $this->top->element;
}
public function getSize()
{
return $this->size;
}
}
class Compares
{
// Determine that given stacks are equal or not
public function compareStack($s1, $s2)
{
if ($s1->getSize() != $s2->getSize())
{
// When number of elements are not same
return false;
}
// This is backup stack
$b1 = new MyStack();
$b2 = new MyStack();
$status = true;
// When both stack contains elements
// And status are active
while ($s1->isEmpty() == false && $s2->isEmpty() == false && $status == true)
{
if ($s1->peek() != $s2->peek())
{
// When data elements are not same
$status = false;
}
else
{
// Backup the actual elements
$b1->push($s1->peek());
$b2->push($s2->peek());
// Remove top element of stack
$s1->pop();
$s2->pop();
}
}
// Puts the all pop element into actual stack
while ($b1->isEmpty() == false)
{
$s1->push($b1->peek());
$s2->push($b2->peek());
$b1->pop();
$b1->pop();
}
return $status;
}
// Print stack element
public function printData($s)
{
if ($s->isEmpty() == true)
{
return;
}
$data = $s->peek();
echo " ". $data;
$s->pop();
$this->printData($s);
$s->push($data);
}
// Handle request to print stack elements
public function printStack($s1, $s2)
{
echo "\n Stack 1 \n";
$this->printData($s1);
echo "\n Stack 2 \n";
$this->printData($s2);
}
}
function main()
{
// Create two empty stack
$s1 = new MyStack();
$s2 = new MyStack();
$task = new Compares();
// First stack
$s1->push(1);
$s1->push(2);
$s1->push(3);
// Second stack
$s2->push(1);
$s2->push(2);
$s2->push(3);
$task->printStack($s1, $s2);
if ($task->compareStack($s1, $s2) == true)
{
echo "\n Stack are equal\n";
}
else
{
echo "\n Stack are not equal\n";
}
$s1->push(4);
$s2->push(5);
$task->printStack($s1, $s2);
if ($task->compareStack($s1, $s2) == true)
{
echo "\n Stack are equal\n";
}
else
{
echo "\n Stack are not equal\n";
}
}
main();
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
/*
Node Js Program for
Check if two stacks are equal
*/
// Define stack node
class StackNode
{
constructor(element, top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
getSize()
{
return this.size;
}
}
class Compares
{
// Determine that given stacks are equal or not
compareStack(s1, s2)
{
if (s1.getSize() != s2.getSize())
{
// When number of elements are not same
return false;
}
// This is backup stack
var b1 = new MyStack();
var b2 = new MyStack();
var status = true;
// When both stack contains elements
// And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
{
if (s1.peek() != s2.peek())
{
// When data elements are not same
status = false;
}
else
{
// Backup the actual elements
b1.push(s1.peek());
b2.push(s2.peek());
// Remove top element of stack
s1.pop();
s2.pop();
}
}
// Puts the all pop element into actual stack
while (b1.isEmpty() == false)
{
s1.push(b1.peek());
s2.push(b2.peek());
b1.pop();
b1.pop();
}
return status;
}
// Print stack element
printData(s)
{
if (s.isEmpty() == true)
{
return;
}
var data = s.peek();
process.stdout.write(" " + data);
s.pop();
this.printData(s);
s.push(data);
}
// Handle request to print stack elements
printStack(s1, s2)
{
process.stdout.write("\n Stack 1 \n");
this.printData(s1);
process.stdout.write("\n Stack 2 \n");
this.printData(s2);
}
}
function main()
{
// Create two empty stack
var s1 = new MyStack();
var s2 = new MyStack();
var task = new Compares();
// First stack
s1.push(1);
s1.push(2);
s1.push(3);
// Second stack
s2.push(1);
s2.push(2);
s2.push(3);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
process.stdout.write("\n Stack are equal\n");
}
else
{
process.stdout.write("\n Stack are not equal\n");
}
s1.push(4);
s2.push(5);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
process.stdout.write("\n Stack are equal\n");
}
else
{
process.stdout.write("\n Stack are not equal\n");
}
}
main();
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
# Python 3 Program for
# Check if two stacks are equal
# Define stack node
class StackNode :
def __init__(self, element, top) :
self.element = element
self.next = top
# Define a custom stack
class MyStack :
def __init__(self) :
# Set node values
self.top = None
self.size = 0
# Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True
# Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = None
self.size -= 1
# return top element of stack
def peek(self) :
if (self.top == None) :
return -1
return self.top.element
def getSize(self) :
return self.size
class Compares :
# Determine that given stacks are equal or not
def compareStack(self, s1, s2) :
if (s1.getSize() != s2.getSize()) :
# When number of elements are not same
return False
# This is backup stack
b1 = MyStack()
b2 = MyStack()
status = True
# When both stack contains elements
# And status are active
while (s1.isEmpty() == False and s2.isEmpty() == False and status == True) :
if (s1.peek() != s2.peek()) :
# When data elements are not same
status = False
else :
# Backup the actual elements
b1.push(s1.peek())
b2.push(s2.peek())
# Remove top element of stack
s1.pop()
s2.pop()
# Puts the all pop element into actual stack
while (b1.isEmpty() == False) :
s1.push(b1.peek())
s2.push(b2.peek())
b1.pop()
b1.pop()
return status
# Print stack element
def printData(self, s) :
if (s.isEmpty() == True) :
return
data = s.peek()
print(" ", data, end = "")
s.pop()
self.printData(s)
s.push(data)
# Handle request to print stack elements
def printStack(self, s1, s2) :
print("\n Stack 1 ")
self.printData(s1)
print("\n Stack 2 ")
self.printData(s2)
def main() :
# Create two empty stack
s1 = MyStack()
s2 = MyStack()
task = Compares()
# First stack
s1.push(1)
s1.push(2)
s1.push(3)
# Second stack
s2.push(1)
s2.push(2)
s2.push(3)
task.printStack(s1, s2)
if (task.compareStack(s1, s2) == True) :
print("\n Stack are equal")
else :
print("\n Stack are not equal")
s1.push(4)
s2.push(5)
task.printStack(s1, s2)
if (task.compareStack(s1, s2) == True) :
print("\n Stack are equal")
else :
print("\n Stack are not equal")
if __name__ == "__main__": main()
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
# Ruby Program for
# Check if two stacks are equal
# Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :element, :next
attr_accessor :element, :next
def initialize(element, top)
self.element = element
self.next = top
end
end
# Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :size
attr_accessor :top, :size
def initialize()
# Set node values
self.top = nil
self.size = 0
end
# Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end
end
# Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = nil
self.size -= 1
end
end
# return top element of stack
def peek()
if (self.top == nil)
return -1
end
return self.top.element
end
def getSize()
return self.size
end
end
class Compares
# Determine that given stacks are equal or not
def compareStack(s1, s2)
if (s1.getSize() != s2.getSize())
# When number of elements are not same
return false
end
# This is backup stack
b1 = MyStack.new()
b2 = MyStack.new()
status = true
# When both stack contains elements
# And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
if (s1.peek() != s2.peek())
# When data elements are not same
status = false
else
# Backup the actual elements
b1.push(s1.peek())
b2.push(s2.peek())
# Remove top element of stack
s1.pop()
s2.pop()
end
end
# Puts the all pop element into actual stack
while (b1.isEmpty() == false)
s1.push(b1.peek())
s2.push(b2.peek())
b1.pop()
b1.pop()
end
return status
end
# Print stack element
def printData(s)
if (s.isEmpty() == true)
return
end
data = s.peek()
print(" ", data)
s.pop()
self.printData(s)
s.push(data)
end
# Handle request to print stack elements
def printStack(s1, s2)
print("\n Stack 1 \n")
self.printData(s1)
print("\n Stack 2 \n")
self.printData(s2)
end
end
def main()
# Create two empty stack
s1 = MyStack.new()
s2 = MyStack.new()
task = Compares.new()
# First stack
s1.push(1)
s1.push(2)
s1.push(3)
# Second stack
s2.push(1)
s2.push(2)
s2.push(3)
task.printStack(s1, s2)
if (task.compareStack(s1, s2) == true)
print("\n Stack are equal\n")
else
print("\n Stack are not equal\n")
end
s1.push(4)
s2.push(5)
task.printStack(s1, s2)
if (task.compareStack(s1, s2) == true)
print("\n Stack are equal\n")
else
print("\n Stack are not equal\n")
end
end
main()
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
/*
Scala Program for
Check if two stacks are equal
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
// return top element of stack
def peek(): Int = {
if (this.top == null)
{
return -1;
}
return this.top.element;
}
def getSize(): Int = {
return this.size;
}
}
class Compares
{
// Determine that given stacks are equal or not
def compareStack(s1: MyStack, s2: MyStack): Boolean = {
if (s1.getSize() != s2.getSize())
{
// When number of elements are not same
return false;
}
// This is backup stack
var b1: MyStack = new MyStack();
var b2: MyStack = new MyStack();
var status: Boolean = true;
// When both stack contains elements
// And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
{
if (s1.peek() != s2.peek())
{
// When data elements are not same
status = false;
}
else
{
// Backup the actual elements
b1.push(s1.peek());
b2.push(s2.peek());
// Remove top element of stack
s1.pop();
s2.pop();
}
}
// Puts the all pop element into actual stack
while (b1.isEmpty() == false)
{
s1.push(b1.peek());
s2.push(b2.peek());
b1.pop();
b1.pop();
}
return status;
}
// Print stack element
def printData(s: MyStack): Unit = {
if (s.isEmpty() == true)
{
return;
}
var data: Int = s.peek();
print(" " + data);
s.pop();
this.printData(s);
s.push(data);
}
// Handle request to print stack elements
def printStack(s1: MyStack, s2: MyStack): Unit = {
print("\n Stack 1 \n");
this.printData(s1);
print("\n Stack 2 \n");
this.printData(s2);
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create two empty stack
var s1: MyStack = new MyStack();
var s2: MyStack = new MyStack();
var task: Compares = new Compares();
// First stack
s1.push(1);
s1.push(2);
s1.push(3);
// Second stack
s2.push(1);
s2.push(2);
s2.push(3);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
print("\n Stack are equal\n");
}
else
{
print("\n Stack are not equal\n");
}
s1.push(4);
s2.push(5);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
print("\n Stack are equal\n");
}
else
{
print("\n Stack are not equal\n");
}
}
}
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
/*
Swift 4 Program for
Check if two stacks are equal
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ top: StackNode? )
{
self.element = element;
self.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
// return top element of stack
func peek()->Int
{
if (self.top == nil)
{
return -1;
}
return self.top!.element;
}
func getSize()->Int
{
return self.size;
}
}
class Compares
{
// Determine that given stacks are equal or not
func compareStack(_ s1: MyStack, _ s2: MyStack)->Bool
{
if (s1.getSize() != s2.getSize())
{
// When number of elements are not same
return false;
}
// This is backup stack
let b1: MyStack = MyStack();
let b2: MyStack = MyStack();
var status: Bool = true;
// When both stack contains elements
// And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
{
if (s1.peek() != s2.peek())
{
// When data elements are not same
status = false;
}
else
{
// Backup the actual elements
b1.push(s1.peek());
b2.push(s2.peek());
// Remove top element of stack
s1.pop();
s2.pop();
}
}
// Puts the all pop element into actual stack
while (b1.isEmpty() == false)
{
s1.push(b1.peek());
s2.push(b2.peek());
b1.pop();
b1.pop();
}
return status;
}
// Print stack element
func printData(_ s: MyStack)
{
if (s.isEmpty() == true)
{
return;
}
let data: Int = s.peek();
print(" ", data, terminator: "");
s.pop();
self.printData(s);
s.push(data);
}
// Handle request to print stack elements
func printStack(_ s1: MyStack , _ s2 : MyStack )
{
print("\n Stack 1 ");
self.printData(s1);
print("\n Stack 2 ");
self.printData(s2);
}
}
func main()
{
// Create two empty stack
let s1: MyStack = MyStack();
let s2: MyStack = MyStack();
let task: Compares = Compares();
// First stack
s1.push(1);
s1.push(2);
s1.push(3);
// Second stack
s2.push(1);
s2.push(2);
s2.push(3);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
print("\n Stack are equal");
}
else
{
print("\n Stack are not equal");
}
s1.push(4);
s2.push(5);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
print("\n Stack are equal");
}
else
{
print("\n Stack are not equal");
}
}
main();
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
/*
Kotlin Program for
Check if two stacks are equal
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, top: StackNode ? )
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size > 0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
// return top element of stack
fun peek(): Int
{
if (this.top == null)
{
return -1;
}
return this.top!!.element;
}
fun size(): Int
{
return this.size;
}
}
class Compares
{
// Determine that given stacks are equal or not
fun compareStack(s1: MyStack , s2 : MyStack): Boolean
{
if (s1.size() != s2.size())
{
// When number of elements are not same
return false;
}
// This is backup stack
var b1: MyStack = MyStack();
var b2: MyStack = MyStack();
var status: Boolean = true;
// When both stack contains elements
// And status are active
while (s1.isEmpty() == false && s2.isEmpty() == false && status == true)
{
if (s1.peek() != s2.peek())
{
// When data elements are not same
status = false;
}
else
{
// Backup the actual elements
b1.push(s1.peek());
b2.push(s2.peek());
// Remove top element of stack
s1.pop();
s2.pop();
}
}
// Puts the all pop element into actual stack
while (b1.isEmpty() == false)
{
s1.push(b1.peek());
s2.push(b2.peek());
b1.pop();
b1.pop();
}
return status;
}
// Print stack element
fun printData(s: MyStack): Unit
{
if (s.isEmpty() == true)
{
return;
}
var data: Int = s.peek();
print(" " + data);
s.pop();
this.printData(s);
s.push(data);
}
// Handle request to print stack elements
fun printStack(s1: MyStack , s2 : MyStack): Unit
{
print("\n Stack 1 \n");
this.printData(s1);
print("\n Stack 2 \n");
this.printData(s2);
}
}
fun main(args: Array < String > ): Unit
{
// Create two empty stack
var s1: MyStack = MyStack();
var s2: MyStack = MyStack();
var task: Compares = Compares();
// First stack
s1.push(1);
s1.push(2);
s1.push(3);
// Second stack
s2.push(1);
s2.push(2);
s2.push(3);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
print("\n Stack are equal\n");
}
else
{
print("\n Stack are not equal\n");
}
s1.push(4);
s2.push(5);
task.printStack(s1, s2);
if (task.compareStack(s1, s2) == true)
{
print("\n Stack are equal\n");
}
else
{
print("\n Stack are not equal\n");
}
}
Output
Stack 1
3 2 1
Stack 2
3 2 1
Stack are equal
Stack 1
4 3 1
Stack 2
5 1 1
Stack are not equal
Time Complexity
The time complexity of comparing two stacks of size n
each is O(n). The function iterates through
both stacks once and performs constant-time operations for each element. Therefore, the overall time complexity
of the algorithm is O(n).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment