🏖️ 스택
스택, stack
Last-in, First-out 방식
- top으로 정한 곳을 통해서만 접근 가능
- top은 가장 위의 자료 (가장 최근 들어온 자료)를 가르킴
push: top을 통해 삽입하는 연산pop: top을 통해 삭제하는 연산
(예) 웹 브라우저 방문기록, 역순 문자열 만들기, 실행 취소 등
🏖️ 큐
큐, queue
First-in, First-out 방식
- 한 쪽 끝에서는 삽입 작업, 다른 쪽 끝에서는 삭제 작업
- front: 삭제연산만 수행되는 곳
- rear: 삽입연산만 이루어지는 곳
enQueue: 삽입연산deQueue: 삭제연산
(예) 프로세스 관리, 은행 업무, 너비 우선 탐색, 캐시 구현
🏖️ 스택 2개로 큐 구현하기
스택 1: add()할 때만 사용
스택 2: peek(), poll() 할때만 사용
과정
- 삽입: 1번 스택에 원소를 넣음
- 삭제(Poll): 1번 스택에 있는 원소들을 모두 2번 스택으로 옮기고 (원소들의 순서가 큐의 순서와 동일해짐), 2번 스택에서 Pop시킴
- 2번 스택이 비어있지 않으면 1번 과정을 생략함
- 크기(Size): 두 스택에 있는 원소들의 합 반환
import java.util.Stack;
public class Queue<T> {
Stack<T> stack1 = new Stack<>();
Stack<T> stack2 = new Stack<>();
private void moveIfAbsent() {
if (stack2.size() == 0)
while (stack1.size() != 0)
stack2.add(stack1.pop());
}
public void add(T t) {
stack1.add(t);
}
public T peek() {
moveIfAbsent();
return stack2.peek();
}
public T poll() {
moveIfAbsent();
return stack2.pop();
}
public int size() {
return stack1.size() + stack2.size();
}
}🏖️ 큐 2개로 스택 구현하기
삽입:
- 큐 2에 데이터 삽입
- 큐 2에 데이터가 존재하면 큐1에 기존 데이터 삽입
삭제:
- 큐 2에 데이터가 존재하면 큐 2의 데이터 삭제
- 큐 2에 데이터가 없으면: 큐 1에 데이터가 하나 남을 때까지 큐2로 옮기고 큐 1에 남은 데이터 삭제
🏖️ 시간복잡도를 유지하면서 배열로 스택과 큐를 구현하기
스택/큐 시간복잡도
- insertion: O(1)
- deletion: O(1)
- search: O(N)
배열로 스택을 구현하면
- 삽입/추출시 O(1): 기존 자료의 위치 변경 없이 단순 넣고 빼기
- 탐색 시 O(1): 위치를 알고 있다는 가정 하
배열로 큐를 구현하면
- 삽입/추출시 O(N): 기존의 자료의 위치를 변경해야 함
- 애초에 큐를 배열의 중간부터 시작하면 시간복잡도 유지 가능
- 탐색 시 O(1): 위치를 알고 있다는 가정 하
🏖️ Prefix, Infix, Postfix
Prefix: 연산자가 제일 앞에 오고 피연산자가 연달아 위치 (ex) +ab
Infix: 연산자를 중심으로 양쪽에 피연산자 위치 (ex) a+b
Postfix: 피연산자가 연달아 위치하고 연산자가 제일 뒤에 위치 (ex) ab+
- 컴파일러/계산기에서 사용
스택으로 Postfix 구현: 수식을 왼쪽부터 오른쪽으로 처리
- 연산값이 나타나면 스택에 넣음
- 연산자가 나타나면 필요한만큼의 연산값들을 스택에서 pop해서 계산 한 후 계산 결과를 스택에 넣음
🏖️ Deque
Deque, double ended queue: 양 끝에서 추가/삭제 등이 가능한 자료 구조
- 시간 복잡도:
- 양 끝 값 추가/삭제: O(1)
- 탐색: O(N)
직접 구현할 수도 있고, 원형큐나 배열 또는 링크드리스트를 이용해 구현할 수 있음
참고:
우당탕탕