Stack

#DataStructure#Computer-Science#CS251

LIFO - Last In First Out §

• Data structure to store and remove data
• Last data pushed into the stack would be the first data popped off
  • Think of it like a stack of boxes, or stack of plates. The last one you put on top will also be the first one you take off. You wouldn’t take out the box from the bottom of the stack. Unless you were trying to break it. :)
• Standard methods for stacks
  • push() - Add an element to the top of the stack
  • pop() - Remove an element from the top of the stack and return it
  • isEmpty() - Returns whether or not the stack is empty
  • size() - Returns the number of elements on the stack
  • peek() - Returns the element at the top of the stack (doesn’t remove it)

Implementations of Stacks §

• Using Arrays
  • Using arrays has lower memory overhead, however you aren’t able to easily resize the array to accommodate for more elements
  • We can implement a stack by basically keeping track of the current “top” index of the stack
  • Every time we add to the stack, put that element in the array and then increase the “top” index by one
  • Every time we pop from the stack, decrease top by 1, remove the element at that location and return it
  • When we peek just return the element at “top” minus one
  • size/isEmpty are pretty self explanatory
• Using Linked Lists
  • Using linked lists involves pointers. Pointers will require more memory, but you can very easily expand the number of elements in the stack
  • Implementing a stack with linked lists is basically just a linked list but you have all the stack functions to add/remove/peek the head of the list
  • Continuously add to the head of the linked list, that way everything is done with constant time operation
    • You can add to the tail of the linked list as the “top” of the stack, but the operations will take longer
  • Keep track of the “top” of the stack, either by maintaining a head or tail pointer depending on implementation details
  • I have not personally implemented a stack this way, I just came up with this on the spot. It seems trivial but I could be way off