메모
03 스택과 큐
- 스택
- 말 그대로 데이터를 쌓아 올린다(stack)는 의미
- LIFO(Last-In-First-Out)으로 자료를 배열함.
- pop() : 스택에서 가장 위에 있는 항목을 제거
- push(item) : item 하나를 스택의 가장 윗 부분에 추가
- peek() : 스택의 가장 위에 있는 항목을 반환
- isEmpty() : 스택이 비어있을 경우 true 반환
- i 번째 항목에 상수 시간 접근이 불가능
- 단, 데이터 추가, 삭제는 상수 시간에 가능
- 배열처럼 원소를 하나씩 옆으로 밀어줄 필요가 없음.
- 같은 방향에서 아이템을 추가하고 삭제한다는 조건하에 연결리스트로 구현할 수 있음.
public class MyStack {
private static class StackNode {
private T data;
private StackNode next;
public StackNode(T data) {
this.data = data;
}
}
private StackNode top;
public T pop() {
if (top == null) throw new EmptyStackException();
T item = top.data;
top = top.next;
return item;
}
public void push(T itme) {
StackNode t = new StackNode(item);
t.next = top;
top = t;
}
public T peek() {
if (top == null) throw new EmptyStackException();
return top.data;
}
public boolean isEmpty() {
return top == null;
}
}
- 스택이 유용한 경우는 재귀 알고리즘을 사용할 때임.
- 재귀적으로 함수 호출 시 임시 데이터를 스택에 넣어 두었다가, 재귀 함수를 빠져 나와서 퇴각 검색(backtrack) 할 때 스택에 넣어 두었던 임시 데이터를 뺴 줘야 함.
- 스택은 이러한 일련의 행위를 직관적으로 가능하게 해줌.
큐 구현하기
- 큐
- FIFO(First-In-First-Out) 순서를 따름.
- 큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거됨.
- add(item) : item 을 리스트 끝부분에 추가함
- remove() : 리스트의 첫 번쨰 항목을 제거함.
- peek() : 큐에서 가장 위에 있는 항목을 반환
- isEmpty() : 큐가 비어있을 때 true 반환
- 큐 역시 연결리스트로 구현할 수 있음.
public class MyQueue {
private static class QueueNode {
private T data;
private QueueNode next;
public QueueNode(T data) {
this.data = data;
}
}
private QueueNode first;
private QueueNode last;
public void add(T item) {
QueueNode t = new QueueNode(item);
if (last != null) {
last.next = t;
}
last = t;
if (first == null) {
first = last;
}
}
public T remove() {
if (first == null) throw new NoSuchElementExcpetion();
T data = first.data;
first = first.next;
if (first == null) {
last = null;
}
return data;
}
public T peek() {
if (First == null) throw new NoSuchElementException();
return first.data;
}
public boolean isEmpty() {
return first == null;
}
}
- 큐에서 처음과 마지막 노드 갱신할 때 실수가 나오기 쉬움.
- 큐는 너비 우선 탐색(breadth-first search)을 하거나 캐시를 구현하는 경우에 종종 사용됨.
면접 문제
3.1 한 개로 세 개
- 배열 한 개로 스택 세 개를 어떻게 구현할지 설명하라.
- 힌트
- 스택은 단순히 가장 최근에 추가된 원소를 가장 먼저 제거하는 자료구조이다. 배열을 사용해서 스택 하나를 흉내 낼 수 있겠는가? 이를 구현하는 방법은 다양하며, 각각 장단점이 있다는 사실을 명심하라.
- 배열의 처음 1/3은 첫 번째 스택, 두 번째 1/3은 두 번째 스택, 세 번째 1/3은 세 번째 스택으로 할당한다면 세 개의 스택을 흉내 낼 수 있다. 하지만 스택 하나가 다른 스택보다 크기가 커지는 경우가 생길 수도 있다. 배열을 나누는 크기를 좀 더 유동적으로 정할 수 있을까?
- 유동적인 분할을 허용하고 싶다면, 스택을 이동할 수 있다. 사용 가능한 모든 공간을 사용할 수 있는가?
- 순환 배열을 생각해보자. 순환 배열이란, 배열의 마지막과 앞부분이 연결된 것을 말한다.
3.2 스택 Min
- 기본적이 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min 함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다.
- 힌트
- 최소 원소는 자주 변하지 않는다는 사실에 주목하라. 더 작은 원소가 추가되거나 최소 원소를 뺴내야 할 때만 바뀐다.
- 각각의 스택 노드에서 추가 데이터를 저장하고 있다면 어떨까? 어떤 종류의 데이터를 갖고 있어야 문제를 풀기 쉬워지나?
- 각각의 노드가 ‘부분스택’(자신을 포함해서 자신보다 아래에 있는 모든 원소)의 최솟값을 알고 있다고 가정하자.