Overview

Stacks and queues are linear data structures with flexible sizes that represent a sequence of nodes. The main difference comes in how elements are removed from the data structure

Stacks

• LIFO: Last In First Out
• Elements can be inserted and deleted only from one side of the list
• The last element inserted into the list is tracked using a pointer
• Insertion is called push
• Deletion is called pop

Queue

• FIFO: First In First Out
• Elements are inserted only to one side of the list, and are removed only from the other side of the list
• Two pointers are maintained, one to the front and one to the rear
• Insertion is called enqueue
• Deletion is called dequeue

Why?

• Stacks are used in solving problems with recursion
  • Ex: ‘undo’ operation
  • Ex: ‘back’ button in the browser
• Queue is used in problems with sequential processing
  • Ex: Breadth-First Search (BFS) in a Graph
  • Ex: Call center phones
  • Ex: Spotify song order
• Both are used when you want a certain usage pattern of the data structure. When you’re debugging a problem, you won’t have to wonder if someone randomly inserted an element into the middle of the list