[자료구조 및 알고리즘] CH4. Stack and Queue

 

Stack이란?

• LIFO(Last In First Out) order를 따르는 자료구조
• 예) 쌓여있는 책더미

Stack 구현의 두 가지 방법(item container로 어떤 것을 선택할지)

• Linked list로 구현(head에만 삽입하고 head만 지워 이를 stack의 top처럼 활용)
• Dynamic array로 구현(head를 포인터가 아닌 index 값으로 사용)

Queue란?

• FIFO(First In First Out) order를 따르는 자료구조
• 예) 줄서기(waiting line)

Queue 구현의 두 가지 방법

• Linked list로 구현
• Dynamic array로 구현
  • 이 때, false-overflow 문제 발생 : 실제로는 빈 공간이 있는데 다 찬 것처럼 보이는 현상
  • 그래서 나온 해결책이 circular queue