[Java/자료구조] 선형구조 - 큐(Queue), 스택(Stack), 덱(Deque) 이해하기 - 1

 

반응형

 

해당 글에서는 자료구조론 중 선형 구조인 큐(Queue)와 스택(Stack), 덱(Deque)에 대해서 이해하고 언제 사용하며 각각의 장단점이 무엇인지에 대해 알아보기 위한 작성한 글입니다.

 
 

 

💡 [참고] 자료구조의 전체 구조

- 해당 글에서는 선형 구조 >> 스택, 큐, 덱에 대해 알아봅니다.

 

 

 

1) 선형 구조(Linear Structure)

---

💡 선형 구조(Linear Structure)

- 데이터를 저장하기 위한 기본적인 형태로 데이터가 '일렬로 나열'되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미합니다.

- 선형구조에는 큐(Queue), 스택(Stack), 덱(deque)이 있습니다.
- 큐는 선입선출(FIFO, First-In-First-Out)의 특성을 가지며 스택은 후입선출(LIFO, Last-In-First-Out)의 특성을 가지고 덱(deque)은 양쪽 끝에서 삽입과 삭제가 가능한 형태의 구조를 가집니다. 

출처 : https://goodgid.github.io/DS-Linear-and-NonLinear/

 
 
 

[ 더 알아보기 ]

💡 비 선형구조(NonLinear) 란?

- 비 선형구조는 데이터를 저장하는 방법 중에서 '일렬로 나열되지 않은 자료구조'를 의미합니다.
- 즉, 데이터가 계층적으로 구성된 경우에 사용합니다. 대표적인 예로는 트리(Tree), 그래프(Graph) 등이 있습니다.

 

출처 : https://goodgid.github.io/DS-Linear-and-NonLinear/

 
 

 

 

2) 큐(Queue)

---

💡 큐(Queue)

- 선형 구조의 형태이며 데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로 선입선출(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를 활용한 문제와 관련되어 궁금하시면 아래의 링크를 확인하시면 크게 도움이 됩니다

[Java/자료구조] 스택(Stack)/큐(Queue) 이해하기 -2 : 문제로 이해하기

 
 

💡 [참고] 큐의 주요 메서드

메서드	설명
offer(E e)	큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우 false를 반환합니다.
add()	큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우  IllegalStateException 예외를 발생시킵니다.
poll()	큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
peek()	큐의 맨 앞에서 요소를 반환합니다. 큐가 비어 있으면 null을 반환합니다.
clear()	큐의 모든 요소를 제거합니다.

 

💡 [참고] Stack API Docuemnt에 대해 궁금하시면 아래의 링크를 확인하시면 도움이 됩니다. 

[Java/자료구조] 선형구조 : 우선순위 큐(Priority Queue) 이해하기

 
 
 
 

3) 스택(Stack)

---

💡 스택(Stack)이란?

- 데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로, 후입선출(LIFO, Last-In-First-Out)의 특성을 가지는 자료구조를 의미합니다.

- 스택은 주로 깊이 우선탐색(DFS:Depth First Search), 백트래킹 종류의 코딩테스트에 사용이 됩니다.
- Java에서 스택은 java.util.Stack 클래스를 이용해 구현할 수 있습니다.

주요 용어	설명
Top	삽입과 삭제가 일어나는 위치를 의미합니다.
Push	스택의 맨 위(top)에 데이터를 추가하는 연산입니다.
Pop	스택의 맨 위(top)에서 데이터를 삭제하고 반환하는 연산입니다.
Peek	스택의 맨 위에 있는 데이터를 조회하는 연산입니다.

 
 

💡 [참고] Stack API Docuemnt에 대해 궁금하시면 아래의 링크를 확인하시면 도움이 됩니다. 

[Java/API] Stack Method API Document : Java 11

 
 
 

1. 후입선출(LIFO, Last-In-First-Out)에 대한 이해

---

 💡 후입선출(LIFO, Last-In-First-Out)

- 자료구조론에서 사용되는 용어로 '가장 마지막에 추가된 데이터가 가장 먼저 삭제'되는 구조를 의미합니다.

 
 

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의 심화 문제에 대해 궁금하시면 아래의 링크를 확인하시면 도움이 됩니다.

[Java/자료구조] 스택(Stack)/큐(Queue) 이해하기 -2 : 문제로 이해하기

 
 

4) 덱(Deque)

---

💡 덱(Deque)이란?

- '양쪽 끝에서 삽입과 삭제가 가능'한 자료구조를 의미합니다.

- 덱(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) 판별, 최대값/최소값 검색
장점	데이터의 순서가 중요한 작업에 적합	구현이 쉽고, 메모리 관리가 용이	양쪽 끝에서의 삽입과 삭제가 가능
단점	큐의 크기가 고정되어 있으면 데이터가 가득 차면 더 이상 삽입이 불가능	데이터 접근이 어렵고, 중간에 있는 데이터에 접근하려면 맨 위의 데이터부터 차례로 꺼내야 함	메모리 사용량이 큼

 
 
 

💡[참고] 좀 더 다양한 자료구조에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.

분류	주제	링크
선형구조	순차 리스트(Array, ArrayList)	https://adjh54.tistory.com/317
선형구조	연결 리스트(단순, 이중, 순환 리스트)	https://adjh54.tistory.com/319
선형구조	큐, 스텍, 덱	https://adjh54.tistory.com/135
선형구조	큐, 스텍, 덱 (문제로 이해하기)	https://adjh54.tistory.com/185
선형구조	큐(일반 큐, 우선순위 큐)	https://adjh54.tistory.com/226
비선형구조	트리(일반트리/이진트리)	https://adjh54.tistory.com/320
비선형구조	균형트리(AVL, 레드-블랙, B-트리)	https://adjh54.tistory.com/324
비선형구조	그래프(방향, 무방향 그래프)	https://adjh54.tistory.com/325

 
 
 

 
 
오늘도 감사합니다. 😀