스택

특징

• 후입 선출 구조이다. (LIFO)
• 데이터가 입력된 순서의 역순으로 처리되어야 할때 사용한다.
• ex) 함수호출 스택, 괄호 쌍 찾기, 문자열 역순 출력 등

메소드

import java.util.Stack;

Stack stack = new Stack();

stack.push(5); // 스택에 데이터 입력
stack.pop(); // 스택에서 데이터 꺼내기
stack.peek(); // 스택에서 top 데이터 확인
stack.constains(5); // 스택 내 데이터 포함 여부 확인
stack.isEmpty(); // 스택이 비어있다면 true, 아니면 false
stack.clear(); // 스택 비우기
stack.size(); // 스택의 크기 반환

시간 복잡도

삽입	삭제	탐색	조회
O(1)	O(1)	O(N)	O(N)

큐

특징

• 선입 선출 구조이다. (FIFO)
• 입력 순서대로 데이터 처리가 필요할 때 사용
• ex) 프린터 출력 대기열, BFS, 급식줄..

메소드

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

Queue q = new LinedList();
q.add(3); // 큐에 추가
q.poll() / q.remove(); // 큐에서 제거
q.peek(); // 큐의 다음 데이터 보기
q.contains(3); // 큐에 데이터 포함 여부
q.clear(); // 큐 비우기
q.isEmpty(); // 큐가 비었는지 여부

시간 복잡도

삽입	삭제	탐색	조회
O(1)	O(1)	O(N)	O(N)