Trusted answers to developer questions

Implementing a stack in Solidity arrays

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

Every programming language consists of a way to represent collectionsThe collections are used to hold any type of primitive data types or objects. 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.

Stack
Stack

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.

  1. push(): An element is inserted at the top of the stack as the last element.

  2. pop(): An element is removed from the top of the stack.

  3. isEmpty(): A true value is obtained if the stack has no elements i.e., 0 length.

  4. isFull(): A true value is obtained if the stack is at its maximum capacity.

  5. 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 contract. 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;
}
}

Code explanation

  • Lines 4–5: Initially, we declare an empty dynamic array named stack and a capacitydefined using uint - unsigned integer i.e. length >= 0 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:

  1. Make sure to use the correct version pragma solidity >=0.5.0 <0.9.0.

  2. 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:

Let's call the pop function once now:

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)O(1)

  • Pop : O(1)O(1)

  • Peek : O(1)O(1)

  • Search : O(n)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.

RELATED TAGS

solidity
Did you find this helpful?