스택,큐,덱

스택

스택은 후입선출(LIFO,Last in First Out)의 특성을 가진 자료구조

스택의 기본 연산

시간복잡도: O(1)

• push: 스택의 맨 위에 요소를 추가
• pop: 스택의 맨 위 요소를 제거하고 그 값을 반환
• peek: 스택의 맨 위 요소를 조회

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1); // 스택에 1 추가
stack.push(2); // 스택에 2 추가
System.out.println(stack.peek()); // 스택의 맨 위 요소 조회: 2
stack.pop(); // 스택의 맨 위 요소 제거
System.out.println(stack.peek()); // 스택의 맨 위 요소 조회: 1

큐

큐는 선입선출(FIFO, First in First Out)의 특성을 가진 자료구조

큐의 기본 연산

시간복잡도: O(1)

• offer/enqueue: 큐의 끝에 요소를 추가
• poll/dequeue: 큐의 첫 번째 요소를 제거하고 그 값을 반환
• peek: 큐의 첫 번째 요소를 조회

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 큐에 1 추가
queue.offer(2); // 큐에 2 추가
System.out.println(queue.peek()); // 큐의 첫 번째 요소 조회: 1
queue.poll(); // 큐의 첫 번째 요소 제거
System.out.println(queue.peek()); // 큐의 첫 번째 요소 조회: 2

큐는 왜 LinkedList로 정의하는가?

Queue - 인터페이스
LinkedList - 클래스, 리스트와 덱을 구현하고있다
Deque - 큐를 상속받는 인터페이스

• LinkedList가 Deque을 구현하고, Deque는 Queue를 상속하니까
• LinkedList는 Queue를 구현하는 셈이다
• 그래서 큐는 LinkedList로 정의할 수 있다
• LinkedList를 사용할 때 Queue로 선언하면 좀 더 유연하게 쓸수있다

덱

덱은 양방향에서 데이터를 추가하거나 제거할 수 있다

덱의 기본연산

시간복잡도: O(1)

• addFirst/offerFirst: 덱의 앞쪽에 요소를 추가
• addLast/offerLast: 덱의 뒤쪽에 요소를 추가
• removeFirst/pollFirst: 덱의 앞쪽 요소를 제거하고 그 값을 반환
• removeLast/pollLast: 덱의 뒤쪽 요소를 제거하고 그 값을 반환

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1); // 덱 앞쪽에 1 추가
deque.offerLast(2); // 덱 뒤쪽에 2 추가
System.out.println(deque.peekFirst()); // 덱 앞쪽 요소 조회: 1
System.out.println(deque.peekLast()); // 덱 뒤쪽 요소 조회: 2
deque.pollFirst(); // 덱 앞쪽 요소 제거
deque.pollLast(); // 덱 뒤쪽 요소 제거