스택(Stack), 큐(Queue)

 

스택(Stack)	큐(Queue)
LIFO(Last-in-First-Out) 마지막에 들어온 원소부터 반환함 -> 쌓인 접시를 생각해보자	FIFO(First-in-First-Out) 첫번째로 들어온 원소를 첫번째로 반환함 -> 줄서기
push() : 요소를 컬렉션에 추가함 pop() :아직 제거 되지 않은 가장 최근에 삽입된 요소를 제거함	데크(Deque)나 우선순위 큐(Priority Queue) 같은 변형이 존재함 너비 우선 탐색(Breadth-First Search)이나 캐시 구현에 사용

 

• 리스트는 스택과 큐의 모든 연산을 지원함.
• 다만, 리스트는 동적 배열로 구성되어 있어 큐의 연산을 수행하기에 효율적이지 않기 때문에 큐는 데크(Deque)라는 별도의 자료형을 사용하는 것이 좋은 성능을 낼 수 있음 -> O(1)
• 스택이나 큐 ADT(추상 자료형)을 실제로 구현할 때는 일반적으로 스택- 연결리스트/큐- 배열로 함

 

https://codeinside23.tistory.com/8

데크(Deque), 우선순위 큐(Priority Queue)