Stack using Array – An Efficient Implementation

A stack data structure can be realised using a one-dimensional array as the implementation method. Nevertheless, a stack that is implemented using an array can only store a predetermined number of data values. This implementation is extremely straightforward. Simply define a one-dimensional array with a fixed size, and then insert or delete values from that array employing the LIFO principle with the assistance of a variable named ‘top’. At the beginning, the value -1 is assigned to the top. When we want to add a value to the stack, we must first increase the value at the top of the stack by one and then add the new value. When we want to remove a value from the stack, we must first remove the value at the top of the stack, and then we must reduce that value by one.

To store the elements of the stack, an empty array of the specified size should be initialised.
Setting the value of the variable top to -1 will allow you to keep track of which element is currently on top of the stack.

Implementing Stack using Array

Let STACK is the name of the array representing stack. SIZE defines the size of the stack. TOP is the variable which keeps track of STACK.

push(item)

To add a new element to the stack, first, increment the top variable by one and then add the new element to the array at the index of the top variable. This is known as the push operation.

• Step 1: First check if the stack is full by comparing TOP with SIZE – 1
• Step 2: If TOP == SIZE – 1, then display the message “Stack is Full” and exit, else goto step 3
• Step 3: Increment TOP pointer by 1 and insert item on STACK[TOP] location

pop()

Before removing an item from the stack, you must first determine whether or not the stack is empty (i.e., if the top is -1). If this is not the case, the element at the top of the stack (i.e., the index of the top) will be returned, and the top variable will have its value decreased by 1.

• Step 1: First check if the stack is empty or not
• Step 2: if TOP == -1 or size(STACK) == 0, then print “Stack is Empty” and exit, else goto step 3
• Step 3: Return element STACK[TOP] and reduce TOP by 1

peek():

Simply return the element that is located at the index of the top to retrieve the element that is currently on top of the stack without removing it.

• Step 1: First check if the stack is empty or not
• Step 2: if TOP == -1 or size(STACK) == 0, then print “Stack is Empty” and exit, else goto step 3
• Step 3: Read the element at STACK[TOP]

is_empty()

Verify that the top variable is the value -1. If this is the case, the stack consists of nothing; if not, it does not.

• Step 1: If TOP == -1, or size(STACK) ==0, then return True else return False

is_full()

Check if stack is full or not by comparing TOP with SIZE

• Step 1: If TOP == size(STACK) – 1, then return True else return False

size():

Return the value that is obtained by adding one to the value of the top. This value represents the number of elements that are contained in the stack.

• Step 1: Return (TOP + 1)

display():

• Step 1: If is_empty() returns True then exit else go to step 2
• Step 2: Iterate from k = 0 to TOP and print STACK[k]

Python code to implement Stack using Array

class Stack:
    SIZE = 5
    def __init__(self):
        self.STACK = [None] * 5
        self.TOP = -1
        
    def push(self, item):
        if (self.is_full()):
            print('Stack Overflow')
        else:
            self.TOP += 1
            self.STACK[self.TOP] = item
            
    def is_full(self):
        if (self.TOP == self.SIZE - 1):
            return True
        else:
            return False
        
    def pop(self):
        if(self.is_empty()):
            return 'Stack Underflow'
        else:
            item = self.STACK[self.TOP]
            self.TOP -= 1
            return item
        
    def is_empty(self):
        if(self.TOP == -1):
            return True
        else:
            return False
        
    def display(self):
        if (self.is_empty()):
            print('Stack is Empty')
        else:
            i = 0
            print('Stack Content :--> ', end = '')
            while(i <= self.TOP):
                print(self.STACK[i], end=' ')
                i += 1
            print('')
            
    def size(self):
        return (self.TOP + 1)
            
        
S = Stack()
print('Is Empty ? :', S.is_empty())
print('Current Size of Stack :--> ', S.size())
S.push(11)
S.push(22)
S.push(33)
S.push(44)
S.push(55)
S.push(66)
print('Is Full ? :', S.is_full())
print('Current Size of Stack :--> ', S.size())
S.display()

print('Poped Item: ', S.pop())
print('Poped Item: ', S.pop())
print('Poped Item: ', S.pop())
print('Poped Item: ', S.pop())
print('Poped Item: ', S.pop())
print('Poped Item: ', S.pop())

Output:

Is Empty ?  True
Current Size of Stack :-->  0
Stack Overflow
Is Full ?  True
Current Size of Stack :-->  5
Stack Content :--> 11 22 33 44 55 
Poped Item:  55
Poped Item:  44
Poped Item:  33
Poped Item:  22
Poped Item:  11
Poped Item:  Stack Underflow