Array implementation of Stack

1. Overview

In this article, we will learn the Array implementation of Stack. To learn more about other data structure topics, refer to these articles.

2. Stack

Data structures are ways to store and organize data in computer memory. A Stack (LIFO – Last In First Out) is a data structure that allows the insertion or deletion of elements only at the top of the stack. It is same as organizing objects in the real world such as a stack of plates, a tower of Hanoi, and so on.

3. Stack implementation

You can implement stack by using any of the following popular ways:

1. Arrays
2. Linked Lists

This article focuses on stack implementation using Arrays.

3.1. Array implementation using stack

Here, the stack is formed by using the array. We perform all the operations regarding the stack using arrays. The stack provides the following functionalities:

1. push – Insertion of the element to the top of the stack
2. pop – Deletion of the element from the top of the stack
3. top – Get the element at the top of the stack.
4. isEmpty – To check whether the stack is empty

First, let’s declare two variables:

1. An array with initial capacity to store the elements
2. A top variable to hold the current index of the stack

Push operation

The push operation must perform the following steps to insert an element to the top of the stack:

• Increment the variable top to the next index
• Assign the value to the current top

begin   
    if top = n then stack full   
    top = top + 1  
    stack (top) : = item;  
end   

The push function must also handle the stack overflow scenario when the array fills up. It can either throw a stack overflow exception or create a new array double the size of current array and copy the elements to the new array.

Pop operation

The pop operation must decrement the current top variable by 1. If the stack is empty, then the top should be -1. It must not allow underflow when the stack is empty.

begin   
    if top != -1 then top = top - 1;  
end; 

Top operation

The top operation returns the element at the stack’s top but does not remove it. You can combine this with the pop operation.

begin   
    if top = -1 then stack empty;   
    return stack(top);  
end; 

isEmpty stack

You can check whether the stack is empty by implementing this functionality.

begin   
    if top = -1 then return true;   
    return false;  
end; 

4. Conclusion

To sum up, we have learned the Array implementation of Stack.