해당 글에서는 자료구조론 중 선형 구조인 큐(Queue)와 스택(Stack), 덱(Deque)에 대해서 이해하고 언제 사용하며 각각의 장단점이 무엇인지에 대해 알아보기 위한 작성한 글입니다.
💡 [참고] 자료구조의 전체 구조
- 해당 글에서는 선형 구조 >> 스택, 큐, 덱에 대해 알아봅니다.
1) 선형 구조(Linear Structure)
💡 선형 구조(Linear Structure) - 데이터를 저장하기 위한 기본적인 형태로 데이터가 '일렬로 나열'되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미합니다.
- 선형구조에는 큐(Queue), 스택(Stack), 덱(deque)이 있습니다. - 큐는 선입선출(FIFO, First-In-First-Out)의 특성을 가지며 스택은 후입선출(LIFO, Last-In-First-Out)의 특성을 가지고 덱(deque)은 양쪽 끝에서 삽입과 삭제가 가능한 형태의 구조를 가집니다.
- 선형 구조의 형태이며 데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로 선입선출(FIFO, First-In-First-Out)의 특성을 의미합니다.
- Java에서 큐는 인터페이스의 역할을 수행하며 ArrayDeque, LinkedList, PriorityQueue 등을 통해서 구현체를 구현합니다.
💡 큐의 동작 과정
- 큐에서의 삽입(Enqueue)과 추출(Dequeue) 과정은 front와 rear 포인터를 기준으로 작동합니다. - 결론적으로 데이터가 저장되는 곳은 ‘rear’ 부분이며 데이터가 추출되는 부분은 ‘front’에서만 수행을 합니다. (*rear와 front 부분은 포인터로 상황에 따라 바뀌게 됩니다.)
💡 큐에 데이터 요소가 ‘삽입(Enqueue)‘되는 동작 과정
1. 데이터를 삽입할 때는 먼저 ‘rear’가 가리키고 있는 위치에 데이터를 ‘저장’합니다.(큐의 요소 중 제일 마지막 부분을 의미합니다)
2. ‘rear'의 위치는 다음 데이터가 ‘삽입될 위치로 이동'됩니다.
💡큐에 데이터 요소가 ‘추출(Dequeue)'되는 동작 과정
1. 데이터가 추출할 때는 먼저 ‘front’가 가리키고 있는 위치에 데이터를 ‘추출’합니다.(큐 내의 요소 중 가장 첫 번째 부분을 의미합니다)
2. ‘front'의 위치는 다음 데이터가 ‘추출될 위치로 이동'됩니다.
연산
설명
Java 제공 메서드
Enqueue
큐의 맨 뒤(rear)에서 데이터를 ‘추가'하는 연산을 의미합니다.
add(E e), offer(E e)
rear
큐의 '맨 뒤'에 위치한 데이터를 가리키는 포인터입니다.
remove(), poll()
front
큐의 '맨 앞'에 위치한 데이터를 가리키는 포인터입니다.
element(), peek()
Dequeue
큐의 맨 앞에 위치한 데이터를 가리키는 포인터입니다.
-
1. 선입선출(FIFO, First-In-First-Out)에 대한 이해
💡 선입선출(FIFO, First-In-First-Out)
- 자료구조에서 사용되는 용어로 '가장 먼저 추가된 데이터가 가장 먼저 삭제'되는 구조를 의미합니다.
2. 큐(Queue) 사용 예시
사용 예시
설명
프로세스 관리/대기열
은행에서 손님이 대기열에 줄을 서서 업무를 처리하는 것이 큐의 예시입니다. 먼저 온 순서대로 업무를 처리하기 때문에 이를 사용합니다
프로세스 관리
운영체제에서 프로세스를 관리할 때, 프로세스가 CPU를 할당받기 위해 대기하는 큐를 사용합니다.
너비 우선 탐색(BFS, Breadth-First Search)
그래프 탐색 알고리즘에서, 인접한 노드를 우선으로 방문해야 하는 경우에 큐를 사용합니다.
캐시(Cache)
캐시 메모리에서 데이터를 저장하고 꺼낼 때, 가장 오래된 데이터를 먼저 삭제하는 정책을 구현할 때 큐를 사용합니다.
3. 큐(Queue)를 이용한 예시
💡 Java에서 큐(Queue)를 이용한 예시입니다.
import java.util.LinkedList;
import java.util.Queue;
Queue<String> queue = new LinkedList<>();
// 큐의 요소를 넣어줍니다.
queue.offer("Apple");
queue.offer("Banana");
queue.offer("Strawberry");
queue.offer("Grape");
// 큐의 값을 출력합니다.
log.debug("queue :: " + queue);
// 큐의 첫번째 요소를 제거합니다.(Apple 제거)
queue.poll();
// 큐의 값을 출력합니다.
log.debug("queue :: " + queue); // ["Banana", "Strawberry", "Grape"]
💡[참고] Queue를 활용한 문제와 관련되어 궁금하시면 아래의 링크를 확인하시면 크게 도움이 됩니다
- 자료구조론에서 사용되는 용어로 '가장 마지막에 추가된 데이터가 가장 먼저 삭제'되는 구조를 의미합니다.
2. 스택(Stack) 사용예시
사용 예시
설명
함수 호출
- 함수 호출 시 함수 내부에서 사용되는 변수들은 스택에 저장됩니다. 함수의 호출이 끝나면 스택에서 제거됩니다.
수식 계산
- 수식에서 괄호를 계산하기 위해서는 스택을 이용해야 합니다.
웹 브라우저 방문 기록
- 웹 브라우저에서 방문한 웹 페이지는 스택에 저장됩니다. 이전 페이지로 돌아갈 때에도 스택을 이용합니다.
3. 스택(Stack)을 이용한 예시
💡 Java에서 스택(Stack)을 이용한 예시입니다.
import java.util.Stack;
Stack<String> stack = new Stack<>();
// 요소 추가
stack.push("Apple");
stack.push("Banana");
stack.push("Strawberry");
stack.push("Grape");
// 스텍의 요소 출력
log.debug("stack :: " + stack);
// 스택의 요소 제거
stack.pop(); // "Grape" 요소 제거
stack.pop(); // "Strawberry" 요소 제거
// 스텍의 요소 출력
log.debug("stack :: " + stack); // [Apple, Banana]
💡 [참고] Stack의 심화 문제에 대해 궁금하시면 아래의 링크를 확인하시면 도움이 됩니다.
- 덱(Deque)은 스택과 큐의 기능을 모두 가지고 있는 자료구조로, 양쪽 끝에서 삽입과 삭제가 가능합니다. 따라서 선입선출(FIFO)과 후입선출(LIFO) 개념이 모두 적용될 수 있습니다. - Java에서 덱은 java.util.Deque 인터페이스를 이용해 구현할 수 있습니다.
1. 덱(Deque) 사용 예시
사용 예시
설명
양방향 큐(Double-Ended Queue)
큐의 앞과 뒤에서 모두 삽입과 삭제가 가능한 덱은 양방향 큐라고도 불립니다.
회문(Palindrome) 판별
덱은 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 검사할 때 사용됩니다.
최대값/최소값 검색
덱은 슬라이딩 윈도우(Sliding Window) 알고리즘을 이용해 최대값/최소값을 검색할 때 사용됩니다.
2. 덱(Deque)을 이용한 예시
💡 Java에서 덱(Deque)을 이용한 예시입니다.
import java.util.Deque;
import java.util.LinkedList;
Deque<String> deque = new LinkedList<>();
// 덱의 요소를 추가합니다.
deque.addFirst("Apple");
deque.addFirst("Banana");
deque.addLast("Strawberry");
deque.addLast("Grape");
// 덱의 값을 출력합니다.
log.debug("deque :: " + deque); // [Banana, Apple, Strawberry, Grape]
// 덱의 첫번째 요소를 제거합니다.(Banana 제거)
deque.removeFirst();
log.debug("deque :: " + deque); // [Apple, Strawberry, Grape]
// 덱의 마지막 요소를 제거합니다(Grape 제거)
deque.removeLast();
// 덱의 값을 출력합니다.
log.debug("deque :: " + deque); // [Apple, Strawberry]
💡 [참고] 덱(Deque)의 메서드
메서드
설명
addFirst(E e)
덱의 맨 앞에 지정된 요소를 추가합니다.
addLast(E e)
덱의 맨 뒤에 지정된 요소를 추가합니다.
removeFirst()
덱의 맨 앞에서 요소를 제거하고 반환합니다. 덱이 비어 있으면 예외가 발생합니다.
removeLast()
덱의 맨 뒤에서 요소를 제거하고 반환합니다. 덱이 비어 있으면 예외가 발생합니다.
getFirst()
덱의 맨 앞에서 요소를 반환합니다. 덱이 비어 있으면 예외가 발생합니다.
getLast()
덱의 맨 뒤에서 요소를 반환합니다. 덱이 비어 있으면 예외가 발생합니다.
5) 큐(Queue), 스택(Stack), 덱(Deque) 요약
분류
큐(Queue)
스택(Stack)
덱(Deque)
정의
먼저 들어온 데이터가 먼저 나가는(First-In-First-Out) 자료구조
마지막에 들어온 데이터가 먼저 나가는(Last-In-First-Out) 자료구조
양쪽 끝에서 삽입과 삭제가 가능한 자료구조
삽입/삭제
삽입은 enqueue, 삭제는 dequeue
삽입은 push, 삭제는 pop
addFirst, addLast, removeFirst, removeLast
활용 예시
대기열, 버퍼(Buffer) 등
함수 호출(call stack), 수식 계산 등
양방향 큐(Double-Ended Queue), 회문(Palindrome) 판별, 최대값/최소값 검색
장점
데이터의 순서가 중요한 작업에 적합
구현이 쉽고, 메모리 관리가 용이
양쪽 끝에서의 삽입과 삭제가 가능
단점
큐의 크기가 고정되어 있으면 데이터가 가득 차면 더 이상 삽입이 불가능
데이터 접근이 어렵고, 중간에 있는 데이터에 접근하려면 맨 위의 데이터부터 차례로 꺼내야 함
메모리 사용량이 큼
💡[참고] 좀 더 다양한 자료구조에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
