Posted on by Kalkicode
Code Stack

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:

  1. Push
  2. 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

  1. Define an array of a fixed size to hold the stack elements and initialize the top index to -1 to indicate an empty stack.
  2. Implement functions to check if the stack is full and if the stack is empty.
  3. 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.
  4. 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.
  5. 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:

  1. Push 5 -> Stack: 5
  2. Push 4 -> Stack: 4 5
  3. Push 3 -> Stack: 3 4 5
  4. Push 2 -> Stack: 2 3 4 5
  5. Push 1 -> Stack: 1 2 3 4 5
  6. Pop -> Stack: 2 3 4 5
  7. Pop -> Stack: 3 4 5
  8. Pop -> Stack: 4 5
  9. Pop -> Stack: 5
  10. 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.

Comment

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





Categories
Relative Post