Implement stack using array
The problem is to implement a stack using an array data structure. A stack is a linear data structure that follows the Last In First Out (LIFO) principle, where the last element inserted is the first one to be removed. In this implementation, we use an array to simulate the stack and provide operations to push (insert) elements, pop (remove) elements, check if the stack is empty or full, and display the elements in the stack.
Problem Statement
Implement a stack data structure using an array and provide functions to push, pop, display, check if the stack is empty, and check if the stack is full.
Explanation with Suitable Example
Let's consider the following operations on the stack:
- Push
- Pop
Idea to Solve the Problem
The main idea to implement a stack using an array is to keep track of the top element's index in the array. We initialize the top to -1 to indicate an empty stack. Whenever we push an element, we increment the top index and store the element at that index. Similarly, when we pop an element, we retrieve the element at the top index, decrement the top index, and remove the element.
Standard Pseudocode
// Define a constant SIZE to set the maximum size of the stack
CONSTANT SIZE = 10
// Declare an array to hold the stack elements and a variable to keep track of the top index
ARRAY element[SIZE]
VARIABLE top = -1
// Function to check if the stack is empty
FUNCTION isEmpty() RETURNS BOOLEAN
IF top == -1 THEN
RETURN TRUE
ELSE
RETURN FALSE
// Function to check if the stack is full
FUNCTION isFull() RETURNS BOOLEAN
IF top == SIZE - 1 THEN
RETURN TRUE
ELSE
RETURN FALSE
// Function to push an element onto the stack
FUNCTION push(value) RETURNS VOID
IF isFull() THEN
PRINT "Stack Is Full"
ELSE
top <- top + 1
element[top] <- value
PRINT "Push Stack element ", value
CALL display()
// Function to pop an element from the stack
FUNCTION pop() RETURNS VOID
IF isEmpty() THEN
PRINT "Empty Stack"
ELSE
PRINT "Pop Stack element ", element[top]
top <- top - 1
CALL display()
// Function to display the elements in the stack
FUNCTION display() RETURNS VOID
IF isEmpty() THEN
PRINT "Empty Stack"
ELSE
PRINT "Stack Element:"
FOR index <- top TO 0 STEP -1
PRINT element[index]
// Main function to test the stack implementation
FUNCTION main() RETURNS VOID
// Push elements onto the stack
CALL push(5)
CALL push(4)
CALL push(3)
CALL push(2)
CALL push(1)
// Pop elements from the stack
CALL pop()
CALL pop()
CALL pop()
CALL pop()
CALL pop()
// Call the main function to start the program
CALL main()
Algorithm
- Define an array of a fixed size to hold the stack elements and initialize the top index to -1 to indicate an empty stack.
- Implement functions to check if the stack is full and if the stack is empty.
- Implement the push function to add an element to the stack:
- Check if the stack is full.
- Increment the top index and store the element at that index in the array.
- Implement the pop function to remove an element from the stack:
- Check if the stack is empty.
- Retrieve the element at the top index in the array.
- Decrement the top index to remove the element from the stack.
- Implement the display function to print all the elements in the stack:
- Check if the stack is empty.
- Iterate through the array from the top index to 0 and print each element.
//Implement stack using array
#include<stdio.h>
//function prototype
void push(int);
void display();
void pop();
int isEmpty();
int isFull();
//Set size of stack
#define SIZE 10
int element[SIZE], top = -1;
//insert Stack element
void push(int value) {
if (isFull()) {
printf("Stack Is Full\n");
} else {
element[++top] = value;
printf("\nPush Stack element %d", value);
display();
}
}
//pop Stack element
void pop() {
if (isEmpty()) {
printf("Empty Stack\n");
} else {
printf("\nPop Stack element %d", element[top]);
top--;
display();
}
}
//display element of Stack
void display() {
if (isEmpty()) {
printf("\nEmpty Stack\n");
} else {
printf("\n Stack Element :");
int index = 0;
for (index = top; index >= 0; index--) {
printf(" %d", element[index]);
}
}
}
int isFull() {
if (top + 1 == SIZE) {
return 1;
} else {
return 0;
}
}
int isEmpty() {
if (top == -1) {
return 1;
} else {
return 0;
}
}
int main() {
//insert elements
push(5);
push(4);
push(3);
push(2);
push(1);
//delete elements
pop();
pop();
pop();
pop();
pop();
}
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
#include<iostream>
using namespace std;
class MyStack {
int size;
int *element;
int top;
public:
MyStack(int capacity) {
this->size = capacity;
this->element = new int [capacity];
this->top = -1;
}
void display() {
if (isEmpty()) {
cout << "\nEmpty Stack\n";
} else {
cout << "\n Stack Element :";
int index = this->top;
while (index >= 0) {
cout << " " << this->element[index];
index--;
}
}
}
bool isFull() {
if (this->top + 1 == this->size) {
return true;
} else {
return false;
}
}
bool isEmpty() {
if (this->top == -1) {
return true;
} else {
return false;
}
}
void push(int value) {
if (this->isFull()) {
cout << "Stack Is Full\n";
} else {
this->top++;
this->element[this->top] = value;
cout <<"\nPush Stack element "<< value;
this->display();
}
}
void pop() {
if (this->isEmpty()) {
cout <<"Empty Stack\n";
} else {
cout << "\nPop Stack element " << this->element[this->top];
this->top--;
this->display();
}
}
};
int main() {
MyStack obj(10);
obj.push(5);
obj.push(4);
obj.push(3);
obj.push(2);
obj.push(1);
obj.pop();
obj.pop();
obj.pop();
obj.pop();
obj.pop();
return 0;
}
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
/*
Java Program
Implement stack using array
*/
public class MyStack {
public int size;
private int []element;
private int top;
public MyStack(int capacity)
{
this.size = capacity;
this.element = new int[capacity];
this.top=-1;
}
//display element of Stack
public void display()
{
if(isEmpty())
{
System.out.print("\nEmpty Stack\n");
}else
{
System.out.print("\n Stack Element :");
int index=top;
while(index>=0)
{
System.out.print(" "+element[index]);
index--;
}
}
}
public boolean isFull()
{
if(top+1==size)
{
return true;
}else
{
return false;
}
}
public boolean isEmpty()
{
if(top==-1)
{
return true;
}else
{
return false;
}
}
//insert Stack element
public void push(int value)
{
if(isFull())
{
System.out.print("Stack Is Full\n");
}else
{
top++;
element[top]=value;
System.out.print("\nPush Stack element "+ value);
display();
}
}
//pop Stack element
public void pop()
{
if(isEmpty())
{
System.out.print("Empty Stack\n");
}else
{
System.out.print("\nPop Stack element "+ element[top]);
top--;
display();
}
}
public static void main(String[] args) {
MyStack obj = new MyStack(10);
//insert elements
obj.push(5);
obj.push(4);
obj.push(3);
obj.push(2);
obj.push(1);
//delete elements
obj.pop();
obj.pop();
obj.pop();
obj.pop();
obj.pop();
}
}
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
/*
C# Program
Implement stack using array
*/
using System;
public class MyStack {
public int size;
private int []element;
private int top;
public MyStack(int capacity)
{
this.size = capacity;
this.element = new int[capacity];
this.top=-1;
}
//display element of Stack
public void display()
{
if(isEmpty())
{
Console.Write("\nEmpty Stack\n");
}else
{
Console.Write("\n Stack Element :");
int index=top;
while(index>=0)
{
Console.Write(" "+element[index]);
index--;
}
}
}
public Boolean isFull()
{
if(top+1==size)
{
return true;
}else
{
return false;
}
}
public Boolean isEmpty()
{
if(top==-1)
{
return true;
}else
{
return false;
}
}
//insert Stack element
public void push(int value)
{
if(isFull())
{
Console.Write("Stack Is Full\n");
}else
{
top++;
element[top]=value;
Console.Write("\nPush Stack element "+ value);
display();
}
}
//pop Stack element
public void pop()
{
if(isEmpty())
{
Console.Write("Empty Stack\n");
}else
{
Console.Write("\nPop Stack element "+ element[top]);
top--;
display();
}
}
public static void Main(String[] args) {
MyStack obj = new MyStack(10);
//insert elements
obj.push(5);
obj.push(4);
obj.push(3);
obj.push(2);
obj.push(1);
//delete elements
obj.pop();
obj.pop();
obj.pop();
obj.pop();
obj.pop();
}
}
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
#Python3 Program
#Implement stack using list
class MyStack :
def __init__(self, capacity) :
self.size = capacity
self.element = [-1]*capacity
self.top = -1
def display(self) :
if (self.isEmpty()) :
print("Empty Stack")
else :
print("Stack Element : ",end=" ")
index = self.top
while (index >= 0) :
print(self.element[index],end=" ")
index -= 1
def isFull(self) :
if (self.top + 1 == self.size) :
return True
else :
return False
def isEmpty(self) :
if (self.top == -1) :
return True
else :
return False
def push(self, value) :
if (self.isFull()) :
print("Stack Is Full",end=" ")
else :
self.top += 1
self.element[self.top] = value
print("\nPush Stack element ", value)
self.display()
def pop(self) :
if (self.isEmpty()) :
print("Empty Stack")
else :
print("\nPop Stack element ", self.element[self.top])
self.top -= 1
self.display()
def main() :
obj = MyStack(10)
obj.push(5)
obj.push(4)
obj.push(3)
obj.push(2)
obj.push(1)
obj.pop()
obj.pop()
obj.pop()
obj.pop()
obj.pop()
if __name__ == "__main__":
main()
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
<?php
/*
Php Program
Implement stack using array
*/
class MyStack {
private $size;
private $element;
private $top;
function __construct($capacity) {
$this->size = $capacity;
$this->element = array_fill(0, $capacity, -1);
$this->top = -1;
}
public function display() {
if ($this->isEmpty()) {
echo("\nEmpty Stack\n");
} else {
echo("\n Stack Element :");
$index = $this->top;
while ($index >= 0) {
echo " ". $this->element[$index];
$index--;
}
}
}
public function isFull() {
if ($this->top + 1 == $this->size) {
return true;
} else {
return false;
}
}
public function isEmpty() {
if ($this->top == -1) {
return true;
} else {
return false;
}
}
public function push($value) {
if ($this->isFull()) {
echo("Stack Is Full\n");
} else {
$this->top++;
$this->element[$this->top] = $value;
echo "\nPush Stack element ". $value;
$this->display();
}
}
public function pop() {
if ($this->isEmpty()) {
echo("Empty Stack\n");
} else {
echo "\nPop Stack element ". $this->element[$this->top];
$this->top--;
$this->display();
}
}
}
function main() {
$obj = new MyStack(10);
$obj->push(5);
$obj->push(4);
$obj->push(3);
$obj->push(2);
$obj->push(1);
$obj->pop();
$obj->pop();
$obj->pop();
$obj->pop();
$obj->pop();
}
main();
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
#Ruby Program
#Implement stack using array
class MyStack
attr_reader :size, :element, :top
attr_accessor :size, :element, :top
def initialize(capacity)
self.size = capacity
self.element = Array.new(capacity,-1)
self.top = -1
end
def display()
if (self.isEmpty())
print("\nEmpty Stack\n")
else
print("\n Stack Element :")
location = @top
while (location >= 0)
print(" ", @element[location])
location -= 1
end
end
end
def isFull()
if (@top + 1 == @size)
return true
else
return false
end
end
def isEmpty()
if (@top == -1)
return true
else
return false
end
end
def push(value)
if (self.isFull())
print("Stack Is Full\n")
else
@top += 1
@element[@top] = value
print("\nPush Stack element ", value)
self.display()
end
end
def pop()
if (self.isEmpty())
print("Empty Stack\n")
else
print("\nPop Stack element " , @element[@top])
@top -= 1
self.display()
end
end
end
def main()
obj = MyStack.new(10)
obj.push(5)
obj.push(4)
obj.push(3)
obj.push(2)
obj.push(1)
obj.pop()
obj.pop()
obj.pop()
obj.pop()
obj.pop()
end
main()
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
/*
Node Js Program
Implement stack using array
*/
class MyStack {
constructor(capacity) {
this.size = capacity;
this.element = Array(capacity).fill(-1);
this.top = -1;
}
display() {
if (this.isEmpty()) {
process.stdout.write("\nEmpty Stack\n");
} else {
process.stdout.write("\n Stack Element :");
var index = this.top;
while (index >= 0) {
process.stdout.write(" " + this.element[index]);
index--;
}
}
}
isFull() {
if (this.top + 1 == this.size) {
return true;
} else {
return false;
}
}
isEmpty() {
if (this.top == -1) {
return true;
} else {
return false;
}
}
push(value) {
if (this.isFull()) {
process.stdout.write("Stack Is Full\n");
} else {
this.top++;
this.element[this.top] = value;
process.stdout.write("\nPush Stack element " + value);
this.display();
}
}
pop() {
if (this.isEmpty()) {
process.stdout.write("Empty Stack\n");
} else {
process.stdout.write("\nPop Stack element " + this.element[this.top]);
this.top--;
this.display();
}
}
}
function main() {
var obj = new MyStack(10);
obj.push(5);
obj.push(4);
obj.push(3);
obj.push(2);
obj.push(1);
obj.pop();
obj.pop();
obj.pop();
obj.pop();
obj.pop();
}
main();
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
/*
Swift 4 Program
Implement stack using array
*/
class MyStack {
var size: Int;
var element: [Int] ;
var top: Int;
init(_ capacity: Int) {
self.size = capacity;
self.element = Array(repeating:-1,count:capacity);
self.top = -1;
}
func display() {
if (self.isEmpty()) {
print("\nEmpty Stack\n");
} else {
print("Stack Element :" , terminator : " ");
var index: Int = self.top;
while (index >= 0) {
print(self.element[index],terminator : " ");
index -= 1;
}
}
}
func isFull() -> Bool {
if (self.top + 1 == self.size) {
return true;
} else {
return false;
}
}
func isEmpty() -> Bool{
if (self.top == -1) {
return true;
} else {
return false;
}
}
func push(_ value: Int) {
if (self.isFull()) {
print("Stack Is Full\n");
} else {
self.top += 1;
self.element[self.top] = value;
print("\nPush Stack element ", value);
self.display();
}
}
func pop() {
if (self.isEmpty()) {
print("Empty Stack\n");
} else {
print("\nPop Stack element ", self.element[self.top]);
self.top -= 1;
self.display();
}
}
}
func main() {
let obj: MyStack = MyStack(10);
obj.push(5);
obj.push(4);
obj.push(3);
obj.push(2);
obj.push(1);
obj.pop();
obj.pop();
obj.pop();
obj.pop();
obj.pop();
}
main();
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
/*
Scala Program
Implement stack using array
*/
class MyStack (var size: Int,
var top: Int,
var element: Array[Int]){
def this(capacity: Int) {
this(capacity,-1,Array.fill[Int](capacity)(0));
}
//display element of Stack
def display(): Unit = {
if (this.isEmpty()) {
print("\nEmpty Stack\n");
} else {
print("\n Stack Element :");
var index: Int = this.top;
while (index >= 0) {
print(" " + this.element(index));
index -= 1;
}
}
}
def isFull(): Boolean = {
if (this.top + 1 == this.size) {
return true;
} else {
return false;
}
}
def isEmpty(): Boolean = {
if (this.top == -1) {
return true;
} else {
return false;
}
}
//insert Stack element
def push(value: Int): Unit = {
if (this.isFull()) {
print("Stack Is Full\n");
} else {
this.top += 1;
this.element(this.top) = value;
print("\nPush Stack element " + value);
this.display();
}
}
//pop Stack element
def pop(): Unit = {
if (this.isEmpty()) {
print("Empty Stack\n");
} else {
print("\nPop Stack element " + this.element(this.top));
this.top -= 1;
this.display();
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyStack = new MyStack(10);
//insert elements
obj.push(5);
obj.push(4);
obj.push(3);
obj.push(2);
obj.push(1);
//delete elements
obj.pop();
obj.pop();
obj.pop();
obj.pop();
obj.pop();
}
}
Output
Push Stack element 5
Stack Element : 5
Push Stack element 4
Stack Element : 4 5
Push Stack element 3
Stack Element : 3 4 5
Push Stack element 2
Stack Element : 2 3 4 5
Push Stack element 1
Stack Element : 1 2 3 4 5
Pop Stack element 1
Stack Element : 2 3 4 5
Pop Stack element 2
Stack Element : 3 4 5
Pop Stack element 3
Stack Element : 4 5
Pop Stack element 4
Stack Element : 5
Pop Stack element 5
Empty Stack
Time Complexity
The time complexity of the push, pop, and display operations in the stack implementation using an array is O(1), constant time, as these operations involve basic array index manipulation and do not depend on the number of elements in the stack.
Resultant Output Explanation
For the given operations:
- Push 5 -> Stack: 5
- Push 4 -> Stack: 4 5
- Push 3 -> Stack: 3 4 5
- Push 2 -> Stack: 2 3 4 5
- Push 1 -> Stack: 1 2 3 4 5
- Pop -> Stack: 2 3 4 5
- Pop -> Stack: 3 4 5
- Pop -> Stack: 4 5
- Pop -> Stack: 5
- Pop -> Empty Stack
The output shows the stack after each push and pop operation, demonstrating the correct implementation of the stack using an array and the LIFO principle.
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