Stack and Queue

Stack is a linear data structure where elements can only be added or removed from one end. Because of this structure, the last item you insert is the first one removed. Think of a stack of plates to wash. Naturally, you will grab the top one and clean it, one by one. This is Stack and we say it follows LIFO (Last-In, First-Out).

• insert -> O(1)
• delete -> O(1)
• access top element -> O(1)
• random access -> O(n)

Queue is another linear data structure where insertion happens at one end, but deletion happens in the other end. Think of people lining up waiting to pay for their groceries in a market. If you’re the first one in the line, you’ll pay for your groceries first. That’s Queue; first come, first served. But instead, we say Queue follows FIFO (First-In, First-Out).

• insert -> O(1)
• delete -> O(n)
  • linked list implementation -> O(1)
• access front element -> O(1)
• random access -> O(n)