스택 (Stack) /큐 (Queue)
스택과 큐는 각각 한쪽 끝에서만 데이터를 추가하고 제거하는 자료구조
데이터를 저장하고 관리하는 방식에 차이가 있음
스택 (Stack)
스택의 특징
- LIFO (Last In, First Out) : 마지막에 추가된 요소가 먼저 제거
- 데이터를 넣는 작업을 푸시 (Push)
- 데이터를 빼는 작업을 팝 (Pop)
스택의 동작
- 스택의 최상단에 요소를 추가하거나 최상단에 요소를 제거할 수 있음
- 주로 함수 호출이나 재귀 알고리즘 등에 사용
스택의 예
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// 정수를 저장하는 스택 생성
Stack<Integer> stack = new Stack<>();
// 스택에 요소 추가 (푸시)
stack.push(10);
stack.push(20);
stack.push(30);
// 스택의 최상단 요소 조회
System.out.println("Top element of the stack: " + stack.peek());
// 스택에서 요소 제거 (팝)
int poppedElement = stack.pop();
System.out.println("Popped element: " + poppedElement);
// 스택의 현재 크기 출력
System.out.println("Size of the stack: " + stack.size());
// 스택이 비어있는지 확인
System.out.println("Is the stack empty? " + stack.isEmpty());
}
}
큐 (Queue) / 덱 or 덱크(Deque)
큐의 특징
- FIFO (First In, First Out) : 처음에 추가된 요소가 가장 먼저 제거
- 데이터를 넣는 작업을 인큐 (Enqueue)
- 데이터를 빼는 작업을 디큐 (Dequeue)
큐의 동작
- 큐의 뒤쪽에 요소를 추가하거나 앞쪽에서 요소를 제거할 수 있음
- 대기열이나 작업 처리, 네트워크 버퍼 등에 사용
큐의 예
Java에서는 java.util.Queue 인터페이스를 사용하며, 이를 구현한 클래스로는 LinkedList나 ArrayDeque 등이 있습니다.
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// 정수를 저장하는 큐 생성
Queue<Integer> queue = new LinkedList<>();
// 큐에 요소 추가 (인큐)
queue.add(10);
queue.add(20);
queue.add(30);
// 큐의 첫 번째 요소 조회
System.out.println("Front element of the queue: " + queue.peek());
// 큐에서 요소 제거 (디큐)
int dequeuedElement = queue.poll();
System.out.println("Dequeued element: " + dequeuedElement);
// 큐의 현재 크기 출력
System.out.println("Size of the queue: " + queue.size());
// 큐가 비어있는지 확인
System.out.println("Is the queue empty? " + queue.isEmpty());
}
}
덱(Deque)의 형태
큐의 확장된 형태로, 양쪽 끝에서 요소의 추가와 제거가 모두 가능한 자료 구조입니다.
1. 양방향 큐
- 양쪽에서 요소를 추가하거나 제거하는 형태
- 큐의 맨 앞과 맨 뒤에서 모두 추가(Enqueue) 및 제거(Dequeue) 작업이 가능
2. 양방향 스택
- 양쪽에서 데이터를 추가하거나 제거할 수 있는 스택
- 스택의 맨 위와 맨 아래에서 모두 추가(Push) 및 제거(Pop) 작업이 가능
덱의 예
Java에서는 java.util.Deque 인터페이스를 사용하여 Deque를 구현합니다.
구체적으로는 ArrayDeque나 LinkedList 클래스 등이 Deque 인터페이스를 구현한 클래스입니다.
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
// Deque 생성
Deque<Integer> deque = new ArrayDeque<>();
// 양쪽에서 데이터 추가 (Enqueue)
deque.addFirst(10); // 맨 앞에 추가
deque.addLast(20); // 맨 뒤에 추가
// 데이터 조회
System.out.println("Front element: " + deque.getFirst());
System.out.println("Rear element: " + deque.getLast());
// 양쪽에서 데이터 제거 (Dequeue)
int removedFront = deque.removeFirst(); // 맨 앞에서 제거
int removedRear = deque.removeLast(); // 맨 뒤에서 제거
// 큐의 현재 크기 출력
System.out.println("Size of the deque: " + deque.size());
// Deque가 비어있는지 확인
System.out.println("Is the deque empty? " + deque.isEmpty());
}
}
'코테 > 개념 정리' 카테고리의 다른 글
[ Heap ] 힙이란? 우선순위 큐란? (0) | 2023.12.23 |
---|---|
리스트 ArrayList <-> 배열 Array 변환 (1) | 2023.12.18 |
자료구조 - 해시(Hash)에 관하여... (0) | 2023.12.09 |
제곱근과 합성수 간의 관계 (1) | 2023.12.01 |
[Java]. 정수 오버플로우(overflow) (0) | 2023.11.30 |