◽ 큐(Queue)
- 줄을 서서 기다리는 것. 시간 순서대로 처리해야하는 경우에 사용한다.
- 선입선출(FIFO, First-In-Fisrt-Out) 구조로 가장 먼저 삽입된 자료가 가장 먼저 삭제된다.
- 작업구역이 한 곳인 스택과 달리 큐는 한쪽 끝에서 삽입/다른 쪽 끝에서 삭제가 되어 양쪽에서 이루어진다.
- 삭제연산이 수행되는 곳은 프론트(또는 머리, Front)이며 삭제연산을 디큐(dnQueue)라고 한다.
- 삽입연산만 이루어지는 곳은 리어(또는 꼬리, Rear)이며 삽입연산을 인큐(enQueue)라고 한다.
예시) 메표소 대기열, 은행 업무, 게임 대전 매칭 시스템 등
◽ 스택(Stack)
- 차곡차곡 쌓는 것. 자료가 시간 순서에 따라 층층이 겹쳐 쌓인다.
- 후입선출(LIFO, Last-In-First-Out) 구조로 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
- top 한 곳에서 삽입, 삭제가 이루어진다.
- 삽입하는 연산을 'Push', 삭제하는 연산을 'Pop'이라고 한다.
- 비어있는 스택에서 원소를 추출하는 경우 stack underflow, 스택이 넘치는 경우 stack overflow라 한다.
예시) 웹 브라우저의 방문기록(뒤로 가기), 역순 문자열 만들기, 실행 취소 등
◽ FIFO & LILO 및 LIFO & FILO 원칙
대기열: FIFO(First In First Out): 대기열에 들어가는 첫 번째 개체는 대기열에서 사용되는 첫 번째 개체입니다.
스택: LIFO(Last In First Out): 스택에 들어가는 마지막 개체는 스택에서 사용되는 첫 번째 개체입니다.
또는
스택: FILO(First In Last Out): 스택의 첫 번째 개체 또는 항목은 스택을 떠나는 마지막 개체 또는 항목입니다.
대기열: LILO(Last In Last Out): 대기열의 마지막 개체 또는 항목은 대기열을 떠나는 마지막 개체 또는 항목입니다.
'개념 창고 > 자료 구조' 카테고리의 다른 글
자료 구조의 중요성 (1) | 2023.01.10 |
---|