Stack in JavaScript (Data Structures)
Short and Precise Js code to create a stack.
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Implementing stack using arrays:
- Using the push/pop method (last in first out)
2. Using the shift/unshift method
Note: Out of these two methods, shift/unshift is highly inefficient because adding/removing elements from the beginning of an array is very costly.
Creating a stack using a linked list:
Todos:
- push and pop
- peek
Creating a node: It contains a value and a pointer.
Stack class: it contains the first value, last value, and length.
Push: add a value to the top of the stack. (technically unshifting in a linked list)
- The function should accept a value.
- Create a new node using that value.
- If there are no nodes in the stack, set the first and last property of the stack 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.
- Reset the first property to be the newly created node.
- Set the next property on the node to be the previously created variable.
- Increment the length of the stack by one.
Pop: remove from the beginning/top of the stack (Technically shift in the linked list)
- If there are no nodes in the stack, return null.
- Create a temporary variable to store the first property in 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.
- Return the value of the node removed.
Peek: returns the topmost value in the stack
Time Complexity of a Stack:
- Access: O(n)
- Search: O(n)
- Insertion: O(1)
- Removal: O(1)
Summary:
The Stack data structure is based on the LIFO (Last In First Out) principle. The element in the last can be accessed first.