[stacks & queues] stack

Stacks

• abstract data structure, collection - it's a concept
• LIFO(last in first out) principle
• Call stack! (recursion) 
• They are not a built in data structure in Javascript, but are relatively simple to implement

Where is it used

• Managing function invocations
• undo/redo (ctrl+Z)
• history object (routing is treated like a stack)
• trees, graphs

Array implementation

• more than one way of doing it, easiest way - array
  • push - pop (adding from the end) : more efficient
  • shift-unshift (adding from the beginning)
    • Big O is not good (because of index should all change)

 

Linked list implementation

• custom class
• it should be constant time

push

• define a function called push and it should accept a value.
• Create a new node with that value.
• If there are no nodes in the stack, set the first and last property to be that new node.
• If there is at least one node, create a variable that stores the current first and then
• reset the first to be the new node.
• And then all we need to do is connect everything together. So set the next property on the node to be the previously created variable and
• then increment the size by one.

 

pop

• if there are no nodes in the stack, if it's empty return null.
• Otherwise, we're going to take whatever the first property is on the stack and store that in a variable to return at the very end.
• If there's only one node set the first and last property to be null. Meaning if the first is now equal to the last set, the last and first to be null.
• If there's more than one node set the first property to be the next property on the current first 
• decrease the size by one return the value of the removed node so you could pause it if you want to implement

 

So just to reiterate why we did it this way, rather than using push and pop that we already wrote for a singly linked list.

Just to reiterate, remember, if we're adding to the end and removing from the end, it's not constant time to remove from the end because we had to iterate the entire list to get to the second to last item

 

And a stack is supposed to be constant time. So we're adding and removing from the beginning of our list, but we're calling it push and pop because it is a stack.

 

Big O of Stacks

• insertion - O(1): linked list
• Removal - O(1) : linked list
• Searching- O(N) : use array
• Access - O(N) : use array