선형구조에 속해있는 큐, 스택 그리고 이 둘의 장점을 합쳐놓은 데크에 대하여 알아보겠습니다.
선형구조 - 자료를 구성하는 데이터를 순차적으로 나열시킨 형태
큐 (Queue)
큐의 사전적인 의미는 줄, 혹은 줄을 서서 기다리는 것을 의미한다.
한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조이다.
제일 처음으로 들어온 데이터가 제일 먼저 삭제가 되는 방식이다.
--> FIFO (First In First Out) --> 스트리밍 등 소프트웨어 개발에 응용되는 편이다.
- front(프론트) : 삭제가 일어나는 곳 (제일 앞 쪽)
- rear(리어) : 삽입이 일어나는 곳 (제일 뒤 쪽)
- dnQueue(디큐) : front에서 이루어지는 삭제연산
- enQueue(인큐) : rear에서 이루어지는 삽입연산
접근 방법은 front와 rear에서만 가능하다.
ex)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
스택(Stack)
스택은 쌓아올린다라는 의미를 갖고있다.
top으로 정한 곳을 통해서만 접근할 수 있다.
top에는 가장 최근에 들어온 데이터가 존재하고 즉 새로운 데이터가 들어올 경우에는 top에 쌓인다는 것이다.
top에서만 접근이 가능하기에 삭제도 top에서만 가능하다.
- push : top을 통해 삽입하는 연산
- pop : top을 통해 삭제하는 연산
- stack underflow : 비어있는 스택에서 데이터를 추출하려고 할 때
- stack overflow : 스택이 넘치는 경우
스택은 큐와 반대로 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
--> LIFO(Last In First Out) --> 뒤로가기 등에 응용 가능!
ex)
- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
데크(Deque)
데크는 큐와 스택의 장점을 모두 갖고 있는 것이다.
삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조이다.
- scroll : 입력 제한 데크
- shelf : 출력 제한 데크
정리하기
큐는 선입선출 스택은 후입선출이다.
큐는 맨 앞인 프론트에서 디큐가 일어나는(삭제되는) 것이고 맨 뒤인 리어에서 인큐(삽입)가 되는 것이다.
스택에서는 푸쉬로 넣어주는 밀어주는 것이고 팝으로 삭제하는 것이다. 터지는 느낌..
스택의 가장 흔하게 접하는 것이 뒤로가기라서 너무 신기했다.
데크는 둘 다의 장점을 가진 리스트 양 끝에서 모두 양방향으로 발생되는 것이다!
마치며
이번에는 선형구조에 대해 공부를 마쳤는데 순차적인 데이터라 그런지 차분한 느낌이 많이 드는 자료구조 같다! 다음에는 비선형구조에 대하여 알아보겠습니다.
