Stacks in JavaScript
Don’t use an Array when a Stack will do
A stack is a basic linear data structure, in which the insertion and deletion of items happens at one end called top of the stack. It follows the order of LIFO (last in first out) or FILO (first in last out), the last element added to the stack will be the first element removed from the stack. The classic real-life example for stack is the stack of plates in a buffet, the plate at the top is always the first one to be removed. The stack data structure is commonly used in managing function invocations, undo/redo, and routing.
There is no built-in stack data structure in JavaScript, but it is relatively simple to implement.
Array Implementation
Even though there is no built-in stack data structure in JavaScript, we use array data structure with the help of the push(), pop(), unshift(), and shift() methods to create stacks. Amongst these methods, unshift() and shift() need to reindex the elements in the array, thus it increases the time complexity. So push() and pop() are our first choices. To understand the array implementation of stacks better, let’s apply it to the leetcode problem below.
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
Usually, when we are dealing with valid parentheses problems, we use stack data structure as part of the solution.
Linked List Implementation
To implement stacks with a linked list, we create Stack class and Node class.
How can we push a new node to the stack? First, we need a value for creating a new node. If there are no nodes in the stack, set the first and last property to be the newly created node. If there is at least one node, create a variable that stores the current first property on the stack and reset the first property to be the newly created node. Set the next property on the new first property to be the previously created variable. Don’t forget to increment the size of the stack by one.
How do we pop the node? If there are no nodes in the stack, it returns null. If there are nodes in the stack, create a temporary variable to store the first property on the stack. If there is only one node, set the first and last property to be null. If there is more than one node, set the first property to be the next property on the current first. Decrement the size by one and return the value of the node that was removed.
The Big O of Stacks
