스택(Stack)이란?
쌓아 올린다는 것을 의미. 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료 구조이다.
특징
-
같은 구조와 크기르의 자료를 정해진 방향으로만 쌓을 수 있음.
-
top으로 정한 곳을 통해서만 접근 가능.
-
top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있음.
-
삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 됨.
-
스택에서 자료를 삭제할 때도 top을 통해서만 가능.
-
스택에서 top을 통해 삽입되는 연산을 'push', top을 통한 삭제하는 연산을 'pop'이라고 함.
=> 가장 마지막에 삽입된 자료가 가장 먼저 삭제됨.
후입선출(LIFO, Last-In-First-Out) 구조
- 비어있는 스택에서 원소를 추출하려고 하면 stack underflow라고 하며, 스택이 넘칠 경우에는 stack overflow라고 함.
활용
- 웹 브라우저 방문 기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여줌.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력.
- 실행 취소 : 가장 나중에 실행된 것부터 실행을 취소.
- 후위 표기법 계산
- 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)
큐(QUEUE)란?
줄을 서서 기다리는 것을 의미.
(놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First in first out) 방식의 자료 구조
특징
-
한쪽 끝에서 삽입 작업, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어짐.
-
삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행됨. 이때, 큐의 리어에서 이루어지는 삽입 연산을 인큐(enQueue) 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부름
-
큐의 가장 첫 원소를 front/ 가장 끝 원소를 rear
-
큐는 들어올 때 rear로 들어오지만 나올 때는 front부터 빠지는 특성
-
접근방법은 가장 첫 원소와 끝 원소로만 가능
-
가장 먼저 들어온 프론트 원소가 가장 먼저 삭제
활용
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS) 구현
- 캐시 구현
관련 문제
참고자료
