4. 스택과 큐 - bloodfinger8/AlgorithmStudy GitHub Wiki
- 스택 문제 https://programmers.co.kr/learn/courses/30/lessons/60058
- 큐 문제 https://programmers.co.kr/learn/courses/30/lessons/17680
§ Stack
§ Queue
스택은 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 LIFO(Last In First Out) 형태의 자료구조입니다.
스택에서 데이터를 넣는 작업을 푸시(push) 라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop) 이라고 합니다.
public class IntStack {
private int max;
private int ptr;
private int[] stk;
// 생성자
public IntStack(int capacity) {
ptr = 0;
max = capacity;
try {
stk = new int[max];
} catch (OutOfMemoryError e) {
max = 0;
}
}
}-
스택용량 max
스택에 쌓을 수 있는 최대 데이터 수를 나타내는 필드입니다. 이 값은 배열 stk의 요솟수와 같습니다. -
스택포인터 ptr
스택에 쌓여있는 데이터 수를 나타내는 필드입니다. 이 값은 스택 포인터라고 합니다. -
스택 본체용 배열 stk
푸시된 데이터를 저장하는 스택 본체의 배열입니다. index 값이 0인 곳이 스택의 bottom입니다. 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0]입니다. -
생성자
생성 시 스택은 비어있으므로 스택 포인터 ptr값을 0으로 합니다. 그리고 매개변수 capacity로 전달받은 값을 스택 용량을 나타내는 max에 값을 복사하고 요솟수가 max인 배열 stk를 생성합니다. -
push
public int push (int x) throws OverflowIntStackException {
if (ptr >= max)
throw new OverflowIntStackException();
return stk[ptr++] = x;
}스택에 데이터를 푸시하는 메서드입니다. 스택이 가득차서 푸시할 수 없는 경우 예외처리를 합니다.
- pop
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}스택의 꼭대기에서 데이터를 팝하고 그 값을 반환하는 메서드입니다. 스택이 비어 있어 팝을 할 수 없는 경우 예외처리를 합니다.
- indexOf
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--) // 정상 쪽에서 선형 검색
if (stk[i] == x)
return i; // 검색 성공
return -1; // 검색 실패
}스택 본체 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지 검색하는 메서드입니다. 포함되어있다면 배열의 위치를, 없다면 -1을 반환합니다.
검색은 top에서 bottom의 방향으로 선형 검색을 합니다. 중복되는 값이 있을 경우 먼저 pop이 되는 값을 찾기 위해서 입니다.
- clear
public void clear() {
ptr = 0;
}스택에 쌓여있는 모든 데이터를 삭제하는 메서드입니다. 스택에 대한 푸시와 팝 등 모든 작업은 스택 포인터를 바탕으로 이루어집니다. 따라서 스택의 배열 요솟값을 변경할 필요가 없이 스택 포인터 ptr의 값을 0으로 하면 됩니다.
- capacity
public int capacity() {
return max;
}스택의 용량 capacity를 반환하는 메서드입니다.
- size
public int size() {
return ptr;
}현재 스택에 쌓여있는 데이터 수를 반환하는 메서드입니다.
- isEmpty
public boolean isEmpty() {
return ptr <= 0;
}스택이 비어있는지 검사하는 메서드입니다. 스택이 비어있으면 true, 그렇지 않으면 false를 반환합니다.
- isFull
public boolean isFull() {
return ptr >= max;
}스택이 가득 찼는지 검사하는 메서드입니다. 스택이 가득 찼으면 true, 그렇지 않으면 false를 반환합니다.
public class IntStack {
private int max; // 스택 용량
private int ptr; // 스택 포인터
private int[] stk; // 스택 본체
// 실행 시 예외 : 스택이 비어 있음
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() { }
}
// 실행 시 예외 : 스택이 가득 참
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException() { }
}
// 생성자
public IntStack(int capacity) {
ptr = 0;
max = capacity;
try {
stk = new int[max]; // 스택 본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
max = 0;
}
}
// 스택에 x를 푸시
public int push(int x) throws OverflowIntStackException {
if (ptr >= max) // 스택이 가득 참
throw new OverflowIntStackException();
return stk[ptr++] = x;
}
// 스택에서 데이터를 팝(정상에 있는 데이터를 꺼냄)
public int pop() throws EmptyIntStackException {
if (ptr <= 0) // 스택이 비어 있음
throw new EmptyIntStackException();
return stk[--ptr];
}
// 스택에서 x를 찾아 인덱스(없으면 –1)를 반환
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--) // 정상 쪽에서 선형 검색
if (stk[i] == x)
return i; // 검색 성공
return -1; // 검색 실패
}
// 스택을 비움
public void clear() {
ptr = 0;
}
// 스택의 용량을 반환
public int capacity() {
return max;
}
// 스택에 쌓여 있는 데이터 수를 반환
public int size() {
return ptr;
}
// 스택이 비어 있는가?
public boolean isEmpty() {
return ptr <= 0;
}
// 스택이 가득 찼는가?
public boolean isFull() {
return ptr >= max;
}
}Q. 기본적인 push기능과 pop 기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? 연산은 모두 O(1) 시간에 동작해야한다.
해답1) Stack 클래스에 멤버로 int minValue를 추가한다. 단, 스택이 커지면 각 원소마다 min을 기록하느라 공간을 낭비하게 된다.
해답2) min값을 기록하는 Stack을 추가한다. 최솟값이 들어올 때마다 값을 pop하고 새로 push한다. 해답1보다 공간적인 면에서 효율적이다.
큐에서 데이터를 넣는 작업을 인큐(enqueue) 라 하고, 큐에서 데이터를 꺼내는 작업을 디큐(dequeue) 라고 합니다.
데이터를 꺼내는 쪽을 프론트(front) 라 하고, 데이터를 넣는 쪽을 리어(rear) 라고 합니다.
-
Linear Queue
큐의 가장 기본적인 형태인 선형 큐(Linear Queue) 입니다. 선형 큐는 rear가 마지막 index를 가르키면서 데이터의 삽입이 이루어집니다. 문제는 rear이 배열의 마지막 index를 가르키게 되면 앞에 남아있는 공간(삽입 중간에 Dequeue 되어 비어있는 공간)을 활용 할 수 없게 됩니다. 이 방식을 해결하기 위해서는 Dequeue를 할때 front를 고정 시킨 채 뒤에 남아있는 데이터를 앞으로 한 칸씩 당기는 수밖에 없습니다. 이 처리의 복잡도는 O(n)이며 데이터를 꺼낼 때 마다 이런 처리를 하게 되면 알고리즘의 효율이 떨어집니다. -
Circular Queue
선형 큐의 단점을 보완하기 위해서 링 버퍼를 활용한 원형 큐(Circular Queue) 입니다. enqueue를 한 후 rear+1이 max와 같을 때 rear의 값을 0으로 초기화하거나, dequeue를 한 후 front+1의 값이 max와 같을 때 front의 값을 0으로 초기화합니다. 이렇게 구현하면 front와 rear값을 업데이트하며 enqueue와 dequeue를 수행하기 때문에 위의 문제를 해결할 수 있습니다. -
Deque
덱(deck)이라는 양방향 대기열(Deque/Double Ended Queue) 큐도 있습니다. front과 rear에서 모두 enqueue와 dequeue가 가능합니다.
링 버퍼를 사용하여 원형 큐를 구현하는 방법입니다.
public class IntQueue {
private int max;
private int front;
private int rear;
private int num;
private int[] que;
public IntQueue(int capacity) {
num = front = rear = 0;
max = capacity;
try {
que = new int[max];
} catch (OutOfMemoryError e) {
max = 0;
}
}
}-
큐의 최대 용량 max
큐의 최대 용량을 저장하는 필드로, 이 값은 배열 que에 저장할 수 있는 최대 요소의 개수와 같습니다. -
**큐의 머리 front **
enqueue하는 데이터 첫번째 요소의 인덱스를 저장하는 필드입니다. -
큐의 꼬리 rear
dequeue하는 데이터 첫번째 요소의 인덱스를 저장하는 필드입니다. -
현재 데이터 수 num
큐에 쌓아놓은 데이터 수를 나타내는 필드입니다. front와 rear의 값이 같은 경우 큐가 비어있는지, 가득찼는지 구별할 수 없는 상황을 피하기 위한 변수입니다. 큐가 비어있을 때 num은 0이고, 가득 찼을 때 num과 max의 값은 같습니다. -
큐 본체 que
enqueue하는 데이터를 저장하기 위한 큐 본체용 배열입니다. -
enqueue
public int enque(int x) throws OverflowIntQueueException {
if (num >= max)
throw new OverflowIntQueueException();
que[rear++] = x;
num++;
if (rear == max)
rear = 0;
return x;
}큐에 데이터를 enqueue하는 메서드입니다. num>=max라면 큐가 가득 차서 enqueue를 할 수 없으므로 예외처리를 합니다. rear+1이 max와 같다면 다시 배열의 앞으로 돌아오도록 0으로 초기화합니다.
- dequeue
public int deque() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException();
int x = que[front++];
num--;
if (front == max)
front = 0;
return x;
}큐에 데이터를 dequeue하는 메서드입니다. num<=0라면 큐가 비어서 dequeue를 할 수 없으므로 예외처리를 합니다. front+1이 max와 같다면 다시 배열의 앞으로 돌아오도록 0으로 초기화합니다.
- indexOf
public int indexOf(int x) {
for (int i = 0; i < num; i++) {
int idx = (i + front) % max;
if (que[idx] == x)
return idx;
}
return -1;
}queue는 데이터를 front에서 rear의 방향으로 출력하므로 검색의 방향도 front에서 rear으로 합니다. front에서 1씩 증가하여 검색하고 max값이 도달했을 때 다시 배열의 앞으로 돌아와야하기 때문에 (front+i)%max를 합니다. 값이 없을 때는 -1을 반환합니다.
- clear
public void clear() {
num = front = rear = 0;
}queue의 배열 요솟값을 변경할 필요가 없이 num, front, rear의 값을 0으로 하면 됩니다.
- capacity
public int capacity() {
return max;
}queue의 용량 capacity를 반환하는 메서드입니다.
- size
public int size() {
return num;
}현재 queue에 쌓여있는 데이터 수를 반환하는 메서드입니다.
- isEmpty
public boolean isEmpty() {
return num <= 0;
}queue가 비어있는지 검사하는 메서드입니다. queue가 비어있으면 true, 그렇지 않으면 false를 반환합니다.
- isFull
public boolean isFull() {
return num >= max;
}queue가 가득 찼는지 검사하는 메서드입니다. queue가 가득 찼으면 true, 그렇지 않으면 false를 반환합니다.
public class IntAryQueue {
private int max; // 큐의 용량
private int num; // 현재의 데이터 수
private int[] que; // 큐의 본체
// 생성자
public IntAryQueue(int capacity) {
num = 0;
max = capacity;
try {
que = new int[max]; // 큐 본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없습니다.
max = 0;
}
}
// 실행할 때 예외：큐가 비어 있음
public class EmptyIntAryQueueException extends RuntimeException {
public EmptyIntAryQueueException() {
}
}
// 실행할 때 예외：큐가 가득 참
public class OverflowIntAryQueueException extends RuntimeException {
public OverflowIntAryQueueException() {
}
}
// 큐에 데이터를 인큐
public int enque(int x) throws OverflowIntAryQueueException {
if (num >= max)
throw new OverflowIntAryQueueException(); // 큐가 가득 참
que[num++] = x;
return x;
}
// 큐에서 데이터를 디큐
public int deque() throws EmptyIntAryQueueException {
if (num <= 0)
throw new EmptyIntAryQueueException(); // 큐가 비어 있음
int x = que[0];
for (int i = 0; i < num - 1; i++)
que[i] = que[i + 1];
num--;
return x;
}
// 큐에서 x를 검색하여 index(찾지 못하면 -1)를 반환
public int indexOf(int x) {
for (int i = 0; i < num; i++)
if (que[i] == x) // 검색성공
return i;
return -1; // 검색실패
}
// 큐를 비움
public void clear() {
num = 0;
}
// 큐의 용량을 반환
public int capacity() {
return max;
}
// 큐에 쌓인 데이터 수를 반환
public int size() {
return num;
}
// 큐가 비어 있는가?
public boolean isEmpty() {
return num <= 0;
}
// 큐가 가득 찼는가?
public boolean isFull() {
return num >= max;
}
}public class IntQueue{
private int max; // 큐의 용량
private int front; // 맨 앞 커서
private int rear; // 맨 뒤 커서
private int num; // 현재의 데이터 수
private int[] que; // 큐의 본체
// 실행할 때 예외：큐가 비어 있음
public class EmptyIntQueueException extends RuntimeException {
public EmptyIntQueueException() {
}
}
// 실행할 때 예외：큐가 가득 참
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {
}
}
// 생성자
public IntQueue(int capacity) {
num = front = rear = 0;
max = capacity;
try {
que = new int[max]; // 큐 본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없습니다.
max = 0;
}
}
// 큐에 데이터를 인큐
public int enque(int x) throws OverflowIntQueueException {
if (num >= max)
throw new OverflowIntQueueException(); // 큐가 가득 참
que[rear++] = x;
num++;
if (rear == max)
rear = 0;
return x;
}
// 큐에서 데이터를 디큐
public int deque() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException(); // 큐가 비어 있음
int x = que[front++];
num--;
if (front == max)
front = 0;
return x;
}
// 큐에서 x를 검색하여 index(찾지 못하면 -1)를 반환
public int indexOf(int x) {
for (int i = 0; i < num; i++) {
int idx = (i + front) % max;
if (que[idx] == x) // 검색성공
return idx;
}
return -1; // 검색실패
}
// 큐를 비움
public void clear() {
num = front = rear = 0;
}
// 큐의 용량을 반환
public int capacity() {
return max;
}
// 큐에 쌓인 데이터 수를 반환
public int size() {
return num;
}
// 큐가 비어 있는가?
public boolean isEmpty() {
return num <= 0;
}
// 큐가 가득 찼는가?
public boolean isFull() {
return num >= max;
}
}public class IntDeque {
private int max; // 덱(deck)의 용량
private int num; // 현재의 데이터 수
private int front; // 맨 앞 커서
private int rear; // 맨 뒤 커서
private int[] que; // 덱(deck)의 본체
// 실행할 때 예외：큐가 비어 있음
public class EmptyIntDequeException extends RuntimeException {
public EmptyIntDequeException() {
}
}
// 실행할 때 예외：큐가 가득 참
public class OverflowIntDequeException extends RuntimeException {
public OverflowIntDequeException() {
}
}
// 생성자
public IntDeque(int capacity) {
num = front = rear = 0;
max = capacity;
try {
que = new int[max]; // 덱(deck)본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없습니다
max = 0;
}
}
// 덱(deck)에 데이터를 머리쪽부터 인큐
public int enqueFront(int x) throws OverflowIntDequeException {
if (num >= max)
throw new OverflowIntDequeException(); // 덱(deck)이 가득 참
num++;
if (--front < 0)
front = max - 1;
que[front] = x;
return x;
}
// 덱(deck)에 데이터를 꼬리쪽부터 인큐
public int enqueRear(int x) throws OverflowIntDequeException {
if (num >= max)
throw new OverflowIntDequeException(); // 덱(deck)은 가득 참
que[rear++] = x;
num++;
if (rear == max)
rear = 0;
return x;
}
// 덱(deck)의 머리부터 데이터를 디큐
public int dequeFront() throws EmptyIntDequeException {
if (num <= 0)
throw new EmptyIntDequeException(); // 덱(deck)이 비어 있음
int x = que[front++];
num--;
if (front == max)
front = 0;
return x;
}
// 덱(deck)의 꼬리부터 데이터를 디큐
public int dequeRear() throws EmptyIntDequeException {
if (num <= 0)
throw new EmptyIntDequeException(); // 덱(deck)이 비어 있음
num--;
if (--rear < 0)
rear = max - 1;
return que[rear];
}
// 덱(deck)에서 x를 검색하여 index(찾지 못하면 -1)를 반환
public int indexOf(int x) {
for (int i = 0; i < num; i++)
if (que[(i + front) % max] == x) // 검색성공
return i + front;
return -1; // 검색실패
}
// 덱(deck)에서 x를 검색하여 머리부터 몇 번 째인가(찾지 못하면 0)를 반환
public int search(int x) {
for (int i = 0; i < num; i++)
if (que[(i + front) % max] == x) // 검색성공
return i + 1;
return 0; // 검색실패
}
// 덱(deck)을 비움
public void clear() {
num = front = rear = 0;
}
// 덱(deck)의 용량을 반환
public int capacity() {
return max;
}
// 덱(deck)에 쌓인 데이터 수를 반환
public int size() {
return num;
}
// 덱(deck)이 비어 있는가?
public boolean isEmpty() {
return num <= 0;
}
// 덱(deck)이 가득 찼는가?
public boolean isFull() {
return num >= max;
}
}Q. 스택 두 개로 큐 하나를 구현하라.
해답1) 큐와 스택의 차이는 순서이다. 스택 s1, s2가 있다고 한다. s1에서 원소를 꺼내 s2에 넣어 저장된 원소의 순서를 뒤집는다. 단, push나 pop을 할 때마다 s1에서 s2로 옮기고, 연산을 수행한 후에 다시 s1을 넣어야 한다.
해답2) s1에는 새 원소가 맨 위에 오도록 하고 s2에는 마지막 원소가 맨 위에 오도록 한다. 큐에서 pop할 때는 s2에 있는 원소를 pop한다. s2가 비어있을 경우에는 s1의 모든 원소의 순서를 뒤집어서 s2에 넣는다. push를 할 때는 s1에 삽입하여 새 원소가 스택 최상단에 오도록 한다.