Implementing a stack in Solidity arrays

Every programming language consists of a way to represent collections of entities in the real or coding world. Their representation i.e., syntax may differ from language to language, but the underlying concept remains the same. In technical jargon, we refer to these as data structures.

In this Answer, we'll learn to implement the stack data structure in Solidity. It is the top contender when it comes to the Blockchain. Before that, let's go through stacks in general.

What is a stack?

A stack is a linear architecture that does not have a cycle, a definite beginning, or an end. Further, a Last In First Out (LIFO) order forms the basis of such an architecture. The most recently added element is removed first. This also works vice versa, the first element to enter is the last to leave.

The figure makes it clear that stacks allow adding and removing elements through one end only, similar to a pile of objects.

Various implementations of stacks

We can implement the stack through either an array or a linked list. Since an array is one of the most widely used data structures, we will be using them to implement our stack in Solidity.

Note: Arrays are contiguous linear memory spaces. We may predefine their capacity to explicitly state an upper bound for the number of elements.

Stack operations

We will now be exploring some of the most commonly used operations performed on stacks.

push(): An element is inserted at the top of the stack as the last element.
pop(): An element is removed from the top of the stack.
isEmpty(): A true value is obtained if the stack has no elements i.e., 0 length.
isFull(): A true value is obtained if the stack is at its maximum capacity.
peek(): The most recently added element is returned, and no change to the stack is made.

Implementation

We will now implement our own stack in a Solidity c ontract. For this purpose, we will be using the Remix IDE to deploy our Solidity stack contract:

// SPDX-License-Identifier: MIT
pragma solidity >= 0.5 .0 < 0.9 .0;
contract SolidityStack{
    int[] private stack;
    uint private capacity;
    // Initializes the stack capacity to 3
    constructor () public{
        capacity = 3;
    }
    
    // Adds a new element at the top of the stack
    function push(int num) public returns(string memory){   
        // Checks if the stack has reached maximum capacity
        if (stack.length == capacity){
            return "Maximum Capacity Reached";
        }
        stack.push(num);
        return "Element Added";
    }
    
    // Removes the latest element from the stack
    function pop() public returns(string memory){   
        // Checks if the stack is empty
        if (stack.length == 0){
            return "Empty Stack";
        }
        stack.pop();
        return "Element Removed";
    }
    // Returns the stack array
    function getStack() public view returns(int[] memory){   
        return stack;
    }
    // Returns the size of the stack array
    function getLen() public view returns(uint){ 
        return stack.length;
    }
    
    // Returns true if the stack has reached maximum capacity
    function isFull() public view returns(bool){  
        if (stack.length == capacity){
            return true;
        }
        return false;
    }
    
    // Returns true if the stack array has no elements
    function isEmpty() public view returns(bool){
        if (stack.length == 0){
            return true;
        }
        return false;
    }
    
    // Returns the latest element of the stack array 
    // if it is not empty
    function peek() public view returns(int){
        if (stack.length > 0){
            return (stack[stack.length - 1]);
        }
        return -99;
    }
}

A stack implemented as a Solidity contract

Code explanation

Lines 4–5: Initially, we declare an empty dynamic array named stack and a capacity variable to define the maximum size.
Lines 8–10: We use the constructor() to initialize the capacity to 3.
Lines 13–20: We define the push() function that receives a value i.e., num from the user. It first checks the capacity of the stack and then adds the new element in it if there is space.
Lines 23–30: We define the pop() function that deletes the most recently pushed value from the stack if the stack is not empty.
Lines 33–35: We define the getStack() function that returns all values of the stack.
Lines 38–40: We define the getLen() function that returns the total count of values in the stack.
Lines 43–48: We define the isFull() function that compares the capacity and the length of the array. The function returns true if the stack reaches the maximum capacity.
Lines 51–56: We define the isEmpty() function that returns true if the stack is empty.
Lines 60–65: We define the peek() function that returns the most recently pushed value from the stack if it is not empty. Otherwise, it returns -99 as an empty stack alert.

Note:
Make sure to use the correct version pragma solidity >=0.5.0 <0.9.0.
The view functions are used when the data is not to be manipulated. All functions except push() and pop() are view functions.

Output

Let’s push three values 5, 10, and 15, into the stack. Now, if we call the getStack() function, it will return all the values of the stack [5,10,15], and the getLen() function will return the size of the stack i.e., 3. Similarly, we can call the peek(), isEmpty(), and isFull() functions and see their results as shown in the image below:

It can be observed that the most recently pushed value i.e., 15, is now removed from the stack. The stack now becomes [5,10], and the length of the stack is decremented to 2.

We have succeeded in constructing a fully functioning stack in Solidity through dynamic arrays.

Time complexities

Let's take a look at the time complexities of different operations on stacks.

Push : $O(1)$
Pop : $O(1)$
Peek : $O(1)$
Search : $O(n)$

Push and Pop will always be implemented in the constant time since only the top of the stack i.e., one position, is being affected.

When to use stacks

We may choose to opt for stacks when the order of actions is of considerable importance. Let's take into account a few use cases where such a data structure may be beneficial:

Mathematical expression evaluation
Last visited site tracking
Syntax parsing e.g., XML
Parenthesis validation
String reversal

Learning data structures like stacks to manipulate data more efficiently is an excellent way to get started with Blockchain.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

License: Creative Commons-Attribution NonCommercial-ShareAlike 4.0 (CC-BY-NC-SA 4.0)