Stack and Queue

by Jii
…
note
|
diary

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 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)