One of the first linear structures that we will be talking about is stacks. To re-iterate:
In a linear data structure all the elements are sequentially arranged one after the other. Therefore each element is connected to elements before and after. These are organized as a single level and users can traverse through the elements of a linear data structure in a single run. Linear data structures are mainly used in software applications.
Characteristics of Stack Data Structure
Stacks are an ordered list of elements. They follow the last in, first out (LIFO) principle. This means that the last element to be added to a stack is the first element that will be removed from it. Much like a stack of pancakes, the last pancake to be placed on the plate is the first to be eaten. A stack can have any abstract data type as an element contained within it which is why you will also notice it being categorized as an abstract data type. Taking short detour, an abstract data type is one whose implementation is hidden from us. Stacks have two principle operations, called push and pop which refer to adding and removing elements from a stack. These two operations happen at the same end of a stack. So the first element to be added to a stack will be the last one to be removed. Similarly, the last item to be added to the stack will be the first one to be removed.
Where are stacks used
Stacks are used to to process function calls, store variables in a computer’s memory, evaluate math expressions and more.
Stack operations
Keeping in mind the LIFO principle, the following are operations that can be done on a stack data structure. You may be acquainted with some of these operations such as push(), pop() etc:
- insertion/push(): adding elements to a stack. Adding and removing elements to a stack happens at the same location which is the top of the stack.
- deletion/pop(): removing elements from a stack. This happens at the same location as adding an element which is the top of the stack.
- peek(): taking a peek at the top most element in a stack without removing it
- isEmpty(): true will be returned is the stack is empty. Else false is returned
- clear(): removing all elements from a stack
- size(): returns the number of items in a stack
- display(): display all the elements in a stack
- change(): change an element at a given position in a stack
Implementation of stack data structure
A stack data structure can be implemented using a one-dimensional array and linked list.
Arrays
Let’s use some common stack operations on an array using JavaScript, starting with the insertion operation using the push() which adds an element to the end of an array:
Similarly we can use the pop() method for the deletion operation which will remove/pop off an element from the end of an array:
The peek operation lets us access the top post element of a stack:
We can clear all the elements in a stack by resetting the the array:
We can also iterate through the array and use the pop() method to keep removing the last element of an array for the length of the array. The length of an array refers to the number of items in an array. For example:
There is no native isEmpty() method in JavaScript to check whether an array is empty, instead we can check if the length property of the array is greater than 1:
To change the element at a particular position in an array, we will reference the particular array index and then change the value at said index:
With all the above information, now let’s construct a stack class in JavaScript in which we will implement all the above methods from scratch: