[자료구조 기초] Data Structure 2
지난번 해시테이블에 이어 오늘 포스팅에서는 스택(Stack), 큐(Queue)에 대해 간단히 정리하겠습니다.
1. Stack
Stack과 Queue는 둘 다 데이터를 일렬로 나열함과 동시에 데이터 조작 위치가 정해진 자료구조입니다.
Stack의 경우 서류더미나 입출구가 하나인 컵과 같은 구조로 생각하면 편리합니다. 데이터는 밑에서부터 차례로 쌓여가며 가장 위(최신)의 영역에서만 데이터의 추가(push), 추출(pop)가 가능합니다.
이런 형태이기에 가장 마지막에 입력한 데이터부터 추출이 가능한 후입선출(Last In First Out)의 구조를 가지며, 중간에 위치한 데이터는 위에 존재하는 최신데이터가 모두 pop될 때까지 건드릴 수 없습니다.
형태는 단순해도 사용처가 까다로워 보이는 자료구조지만, 최신 데이터만 접근가능한 특성으로 인해 의외로 자주 보이는 기능들의 구현에 사용됩니다. 대표적인 예시들은 다음과 같습니다.
* 브라우저 뒤로가기 / 앞으로가기 버튼
* 워드나 포토샵 등 ctrl + z (undo / redo) 기능
* 복잡한 괄호() 대응관계 판별
추가로 뒤에 나올 탐색 알고리즘에서 깊이우선탐색의 후보관리(최신순으로 유지)에 사용되기도 합니다.
Stack은 후입선출(LIFO)의 자료구조로서 깊이우선탐색, 브라우저 뒤로가기 기능 등에 사용됩니다.
2. Queue
Queue는 파이프나 일반 대기행렬을 생각하면 편한 자료구조입니다. Stack이 입구가 곧 출구의 구조라면
Queue는 입구 반대편이 출구이기에 Stack과 반대로 먼저 들어온 데이터가 먼저 추출이 됩니다.
(Queue의 데이터 추가는 enqueue, 추출은 dequeue이며 Java에서 메서드명은 offer, poll입니다.)
이런 선입선출(First In First Out)의 구조지만 Stack과 마찬가지로 중간 데이터에는 접근하지는 못하고 필요한 데이터 추출을 위해서는 입력 순서대로 차례로 추출해나가야 합니다.
사용 사례는 다음과 같습니다.
* 최근 작업 문서와 같은 대기목록
* Buffer
마찬가지로 뒤의 탐색 알고리즘에서 큐의 경우 너비우선탐색의 후보관리(오래된 순서)에 사용됩니다.
참고사항으로 Java의 경우 Stack은 클래스로 구현된 반면에 Queue는 인터페이스로 정의되어 있습니다.
따라서 필요한 경우 API 문서를 참조해 적절한 구현클래스를 선택해야합니다. (LinkedList 등)
Queue 선입선출(FIFO)의 자료구조로서 너비우선탐색, Buffer 기능 등에 사용됩니다.
또한 큐의 응용 형태로 우선순위 큐(Priority Queue)와 덱(Deque, Double Ended Queue)가 있습니다.
Priority Queue의 경우 뒤에 나오는 Heap이라는 자료구조를 통해 구현되는데, 데이터 추가는 자유롭되,
데이터 추출은 항상 최솟값부터 이뤄지는 자료구조입니다.
Deque은 기존 Queue의 파이프 구조에서 양쪽을 모두 추가와 추출이 가능한 입출구로 만든 형태입니다. 물론 입출구의 기능을 양쪽에 둔 것뿐, 중간 데이터를 바로 취하는건 여전히 불가능합니다.
언제나 읽어주셔서 감사합니다.^^
개인 공부용 블로그입니다.
잘못된 부분에 언제든지 댓글이나 메일로 지적해주시면 감사하겠습니다.
Leave a comment