2-1. 큐(Queue)
- 개념
- 특징
- 활용큐란?
줄서기라고 생각하면 된다.
은행같은 곳에서 업무를 볼 때 창구에서 먼저 온 사람이 처리되고 그 다음으로 넘어가듯이 말이다.
특징
-
top이 정해져 있는 stack과는 달리 한 쪽이 삽입작업이 되는 곳이면 다른 한 쪽이 삭제작업을 하는 구조 이다.
-
삽입, 연산 작업만 이루어지는 곳을 rear라고 한다.
-
삭제 작업만 이루어 지는 곳을 front라고 한다.
-
rear에서 이루어 지는 삽입 연산을 enQueue라고 한다.
-
front에서 이루어 지는 삭제 연산을 dnQueue라고 한다.
따라서 처음 들어간 자료는 제일 우선으로 삭제되어진다.
FIFO ( First In First Out ) -
접근법은 첫 원소와 끝 원소로만 가능하다. (연산이 되고 삭제가 되는 부분이 두 부분이라..)
-
가장 처음 들어온 자료 원소가 첫번째 마지막이 마지막.. stack은 첫번째가 마지막 마지막이 첫번째..
활용
큐는 데이터가 입력된 시간 순서대로 처리해야하는 부분
- 콜센터 고객 대기
- 캐시 구현
- 프린터 인쇄 대기
- 예약 번호
문제점
rear값이 점차 증가하게 되면 full 상태가 되며 이 때 큐에 원소가 가득 차 있지 않은 상태일 수 있다. front에서 삭제가 일어났다면 그만큼 공간이 비어 있는 상태이기 때문에..
full 상태가 되었을 때는 첫번째 원소의 위치를 큐의 front 0번 인텍스로 이동 시키고 이 기준으로 rear의 위치도 다시 잡아주어야 하기 때문에 원소 이동으로 인한 시간 낭비가 생긴다.
2-2. 스택(Stack)
- 개념
- 특징
- 활용스택이란?
말 어원 그대로 쌓아 올리다.
어떠한 상자 안에 차곡차곡 쌓아올리는 모습의 자료구조를 상상하면 될 것 같다.
특징
-
같은 구조와 크기의 자료들을 정해진 방향으로만 정리 할 수 있다. (쌓을 수 있다.)
-
push (자료를 저장소에 넣는 과정) 와 pop (저장소에서 자료를 빼는 과정)으로 자료를 저장 관리한다.
-
top으로 정해 놓은 곳을 통해서만 접근 탐색이 가능하다.
-
물론 자료를 삭제할 때도 top을 통해서만 가능.
따라서 스택의 특징은 시간순으로 쌓인 자료 중 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
(LIFO : Last In First Out)
- 비어있는 스택에 자료를 추출 할 때 stack underflow 라고 한다.
- 자료가 넘칠 경우에는 stack overflow 라고 한다.
활용
stack의 특징이라 볼 수 있는 LIFO를 활용하여 여러 분야에 활용이 가능하다.
- 웹 브라우저 방문기록 : 가장 마지막에 열린 페이지부터 다시 보여줌.
- 실행 취소 : 가장 마지막에 했던 작업을 취소 시킨다.
- 우선순위 : 연산자중 우선순위 표현을 위한 검사
- 문자열 만들기(역순) : 가장 나중에 입력되어진 (역순) 문자부터 출력한다.
So ..
개념에 비유할만한 것들이 정해져 있다.
큐는 줄 서기 한 줄 서기 에스컬레이터 같은 느낌이고
스택은 안좋게 보면 필요한 물건을 제일 먼저 넣어버린 수납함이고 좋게 보면 제일 자주 쓰는 것들을 맨 나중에 넣어서 필요할 때마다 빠르게 쓰기 좋은 수납함의 느낌이다.
