[알고리즘] 스택(Stack) / 큐(Queue) / 데크(Deque)

스택

삽입과 삭제가 후입선출(FILO)

스택의 종류

• push: 스택의 맨 위에 새로운 요소를 추가
• pop: 스택의 맨 위에 있는 요소를 제거하고 반환
• peek: 스택의 맨 위에 있는 요소를 제거하지 않고 반환
• isEmpty: 스택이 비어 있는지 확인

=> 깊이우선탐색, 백트래킹 종류 / 재귀함수 알고리즘 원리와 일맥상통

 

스택 선언

Stack<Integer> stack = new Stack<>();

// Push
stack.add(1);
stack.add(2);
stack.add(3);
// [1,2,3]


//pop
stack.pop();
// 3
// [1,2]

//peek
stack.peek();
// 2
// [1,2]


//isEmpty
stack.isEmpty();
// false

 

스택의 활용 예시

• 실행취소( Undo ) 기능
• 웹 브라우저 뒤로가기
• 함수 호출 스택

 

스택의 성질

1. 원소의 추가 O(1)
2. 원소의 삭제 O(1)
3. 제일 상단의 원소 확인 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

큐

삽입과 삭제가 선입선출(FIFO) - 삽입삭제 양방향
 

  

큐의 종류

• enqueue: 큐의 끝에 요소를 추가
• dequeue: 큐의 앞에서 요소를 제거하고 반환

=> 너비우선 탐색에서 사용

 

큐 선언

Queue<Integer> queue = new LinkedList<>();

// enqueue 연산
queue.add(1);
queue.add(2);
queue.add(3);
//[1,2,3]

// dequeue 연산
queue.poll(); // 또는 queue.remove();
//[2,3]

// peek 연산
queue.peek(); // 또는 queue.element();
//[2,3]

// isEmpty 연산
queue.isEmpty();
// false

 

큐의 활용 예시

• 프린터 대기열: 먼저 요청된 인쇄 작업부터 차례대로 처리
• 프로세스 스케줄링
• 데이터 스트림 처리

 

큐의 성질

1. 원소 추가 O(1)
2. 원소 삭제 O(1)
3. 제일 앞/뒤의 원소 확인 O(1)
4. 제일 앞 /뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

우선순위 큐 : MAX, MIN

 

💡 Queue 값 추가
add() : 큐가 꽉 찬 경우 IllegalStateException 에러 발생
offer() : 큐가 꽉 찬 경우 false 반환
 
💡 Queue 값 제거
remove() : 큐가 비어 있는 경우 NoSuchElementException 에러 발생
poll() : 큐가 비어 있을 경우 null 반환 clear() : 큐 비우기
 
💡 Queue 맨 앞 값 확인
element() : 큐가 비어 있는 경우 NoSuchElementException 에러 발생
peek() : 비어있는 경우 null 반환

 

데크

양쪽 끝에서 데이터를 처리할 수 있는 큐를 뜻함

어떤 쪽으로 입력하고 어떤쪽으로 출력하느냐에 따라서 스택으로 사용할 수 있고, 큐로도 사용할 수 있음

자바에서는 공식적으로 Stack 대신 ArrayDeque를 사용하도록 권장

• Stack 클래스는 자바 1.0부터 존재하던 오래된 클래스
• 불필요한 동기화 처리 및 스레드 안전에 의한 성능 감소

 

데크의 종류

• addFirst(e): 요소를 데크의 앞에 삽입합니다.
• addLast(e): 요소를 데크의 뒤에 삽입합니다.
• removeFirst(): 데크의 앞에서 요소를 제거하고 반환합니다.
• removeLast(): 데크의 뒤에서 요소를 제거하고 반환합니다.
• peekFirst(): 데크의 앞 요소를 제거하지 않고 반환합니다.
• peekLast(): 데크의 뒤 요소를 제거하지 않고 반환합니다.

 

데크 선언

Deque<Integer> deque = new ArrayDeque<>();

// 앞에 요소 추가
deque.add(1);
deque.add(2);
deque.add(3);
// [3,2,1]

// 뒤의 요소 추가
deque.addLast(4);
deque.addLast(5);
// [3,2,1,4,5]

// 앞의 요소 제거
deque.removeFirst();
// [2,1,4,5]

// 뒤의 요소 제거
deque.removeLast();
// [2,1,4]

// 앞 요소 확인
deque.peekFirst();
// 2
// [2,1,4]

// 뒤 요소 확인
deque.peekLast();
// 4
// [2,1,4]

//비어있는지 확인
deque.isEmpty();
//false

 

 

한눈에보기

특징	스택(Stack)	큐(Queue)	데크(Deque)
정의	LIFO(Last In First Out) 선입 후출	FIFO(First In First Out) 선입선출	양쪽 끝에서 삽입과 삭제가 가능
주요 연산	- 삽입(push) - 삭제(pop)	- 삽입(enqueue) - 삭제(dequeue)	- 앞쪽 삽입(push front) - 앞쪽 삭제(pop front) - 뒤쪽 삽입(push back) - 뒤쪽 삭제(pop back)
특징	- 최근에 삽입된 항목이 가장 먼저 삭제됨	- 가장 먼저 삽입된 항목이 가장 먼저 삭제됨	- 양쪽 끝에서 삽입과 삭제를 모두 수행할 수 있음
장점	- 구현이 간단함 - 메모리 효율적 사용	- 간단하고 직관적인 자료구조	- 다양한 삽입 및 삭제 작업 지원 - 스택과 큐의 장점 모두 포함
단점	- 요소 접근이 제한적임 - 중간에 있는 요소 접근 불편	- 중간에 있는 요소 접근 불편	- 복잡한 구현 필요 - 메모리 사용 증가
사용 사례	- 함수 호출 스택 - 후위 표기법 계산	- 작업 큐 - BFS (너비 우선 탐색)	- 양방향 탐색이 필요한 알고리즘 - 캐시 구현
복잡도	- 삽입: O(1) - 삭제: O(1)	- 삽입: O(1) - 삭제: O(1)	- 삽입: O(1) - 삭제: O(1)