Implementation of Stack using Array

Stacks is a key data structure in modern programming that facilitate efficient software development with Last In First Out (LIFO) principle. Stack is created using one-dimensional arrays. This method involves a ‘top’ variable, which tracks the latest element, ensuring that the last added item is the first to be removed. This article delves into implementing stacks with arrays, showcasing their practical use in programming.

Stack Implementation using an Array

Stack is one of the most commonly used data structures in today’s programming world. The major operations of the stack are as follows.

• push(value)
• pop()
• isEmpty()
• isFull()
• Peek()

Let’s discuss each of these operations in details:

push(value)

This operation is used to insert values into the stack. It inserts elements on top of the stack.

Algorithm

• Check if the top is equal to the size of the array. If true, print “Stack is Full” and return.
• If false, increment the top by one.
• Assign an item to the top of the stack.

Code

C++:

// Push function increases the stack size by 1
void push(int val) {
    // n: size of a stack
   if(top>=n-1) // Check whether a stack is full or not
       cout<<"Stack Overflow"<<endl;
    // Increase the top and push the element into the stack
   else {
      top++; 
      stack[top]=val;
   }
}

Java:

public void push(int item) {
    // Check whether a stack is full or not
    if (isFull()) {
        throw new RuntimeException("Stack is full.");
    }
    
    // Increase the top and push the element into the stack
    array[++top] = item;
}

Python:

def push(self, element):
       # Check whether a stack is full or not
       if self.isFull():
           print("Stack is Full")
           return
       # Push the element into the stack
       self.stack.append(element)

pop()

This operation is used to remove an element from the stack. It uses the LIFO property to remove elements from the stack, i.e., the element inserted last will be removed first from the stack. It returns the removed element from the stack.

Algorithm

• Check if the top is equal to -1. If true, then print “Stack is Empty” and return.
• If false, then store the top item in a variable.
• Decrement the top.
• Return the stored item through the variable.

Code

C++:

void pop() {
    // Check whether a stack is empty or not
    if(top<=-1)
        cout<<"Stack Underflow"<<endl;
    // Pop the element from a stack and decreases the top value by 1
    else {
      cout<<"The popped element is "<< stack[top] <<endl;
      top--;
    }
}

Java:

public int pop() {
    // Check whether a stack is empty or not
    if (isEmpty()) {
        throw new RuntimeException("Stack is empty.");
    }
    // Pop the element from a stack and decreases the top value by 1
    return array[top--];
}

Python

def pop(self):
       # Check whether a stack is empty or not
       if not self.isEmpty():
           item = self.stack[-1]
           # Pop the element from a stack
           del self.stack[-1]
           return item
       else:
           return "Stack Already Empty"

isEmpty()

This operation is used to check whether the stack is empty or not. It returns a boolean variable, True or False, indicating whether the stack is empty or has some elements in it.

Algorithm:

• Check if the top is equal to -1. If True, returns True.
• Else return false.

Code:

C++:

void isEmpty(){
    if(top<=-1){
        cout<<"Stack Underflow"<<endl;
    }
    else{
        cout<<"Stack Not Empty"<<endl;    
    }
}

Java:

private boolean isEmpty() {
    return top == -1;
}

Python:

def isEmpty(self):
       return self.stack == []

isFull()

This operation is used to check whether the stack is full or not. It returns a boolean variable, True or False, indicating whether the stack is full or some more elements can still be inserted.

Algorithm

• Check if the top is equal to the size of the array, i.e., n, then return True.
• Otherwise, return False.

Code:

C++:

void isFull(){
    if(top>=n-1){
        cout<<"Stack Overflow"<<endl;
    }
    else{
        cout<<"Stack Not Full"<<endl;    
    }
}

Java:

private boolean isFull() {
    return top == capacity - 1;
}

Python:

def isFull(self):
       return len(self.stack) == self.size

Peek()

This operation is used to see the top element of the stack. The Peek function will return the top element without removing it. It will work only when the stack is not empty.

Algorithm:

• Check if the stack top is equal to -1. If true, then print “Stack is Empty” and return.
• If false, store the top of the stack item in a variable.
• Return that variable.

Code:

C++:

void peek(){
    if(top<=-1){
        cout<<"Stack Underflow"<<endl;
    }
    else{
        cout<< stack[top] <<endl;    
    }
}

Java:

public int peek() {
    if (isEmpty()) {
        throw new RuntimeException("Stack is empty.");
    }
    return array[top];
}

Python:

def peek(self):
       if self.isEmpty():
           return "Stack Empty"
       return self.stack[-1]

Pros and Cons of a Stack Implementation using an Array

Pros

• The pointers in an array-based stack implementation can be stored without using any additional memory.
• It is more time-efficient than the stack implementation utilizing linked lists.
• The implementation of the stack using an array is more secure and reliable.
• Array implementation of Stack is highly recommended in allocation and deallocation.

Cons

• Because the stack’s size is constant, an array cannot be used to increase or decrease the stack’s size.
• Given that the items are stored in sequential memory locations, insertion and deletion in an array are fairly challenging.
• There is a high possibility of Stack Overflow.
• While using an Array, random access to stack positions is not possible.

Conclusion

Let’s summarise our topic, the implementation of stack using an array by mentioning some of the important points.

• A Stack is a linear data structure that uses LIFO functionality.
• A stack can be implemented using an array and supports functions like push, pop, peek, empty and full.
• The push and pop functions are used to insert and delete elements in the stack, respectively.
• In the stack implementation of the array, we maintain the top with a variable and the stack has a predefined size that cannot be increased later.
• Stack implementation using an array is much more time-efficient as compared to other methods.