Stack
쌓다, 쌓이다, 포개지다 와 같은 뜻
데이터(data)를 순서대로 쌓는 자료구조
Stack의 특징
1. LIFO(Last In First Out)
먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조
2. 하나의 입출력 방향
Stack 자료구조는 데이터를 넣고 뺄 수 있는 곳이 스택의 가장 최상단, 한 군데
3. 데이터는 하나씩 넣고 뺄 수 있다.
스택에 한개 씩 여러 번 데이터를 넣어 스택 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 스택의 가장 최상단에서 한 번에 한 개의 데이터만을 뺄 수 있다.
Stack의 실사용 예제
- 웹 브라우저 뒤로가기 : 가장 나중에 열린 페이지부터 뒤로 가기를 실행합니다.
- 문서작업에서 Ctrl+Z : 가장 나중에 수정한 내역부터 되돌립니다.
- 역순 문자열 만들기 : 맨 끝의 문자열부터 차례대로 만들어집니다.
- 후위 표기법 계산
- 재귀적 알고리즘
Queue
줄을 서서 기다리다, 대기행렬이라는 뜻
놀이기구를 기다리는 줄, 음식점 번호표 같은 것을 예시
Queue의 특징
1. FIFO (First In First Out)
먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조
2. 두 개의 입출력 방향
데이터를 입력할 때는 큐의 맨 끝(tail)으로만 입력이 가능하며 데이터를 출력할 때는 큐의 맨 앞(head)으로만 출력이 가능
3. 데이터는 하나씩 넣고 뺄 수 있다.
에 한 개 씩 여러 번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 큐의 맨 앞에서 한 번에 한 개의 데이터만을 뺄 수 있다.
Queue의 실사용 예제
- 은행창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 봅니다.
- 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력됩니다.
- 컴퓨터 운영체제의 테스크 스케쥴링 : 가장 간단한 형태의 선입선 처리 스케쥴링 정책
- 너비 우선 탐색(BFS) 알고리즘
