스택 알아보기
스택(stack)은 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출입니다. 데이터를 넣는 작업을 푸시라 하고 데이터를 꺼내는 작업을 팝이라고 합니다.
스택 만들기
다음은 자바로 구현된 스택입니다:
// int형 고정 길이 스택
public class IntStack {
private int[] stk; // 스택용 배열
private int capacity; // 스택의 크기
private int ptr; // 스택 포인터
//--- 실행시 예외: 스택이 비어있음 ---//
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() { }
}
//--- 실행시 예외: 스택이 가득 참 ---//
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException() { }
}
//--- 생성자(constructor) ---//
public IntStack(int maxlen) {
ptr = 0;
capacity = maxlen;
try {
stk = new int[capacity]; // 스택 본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
capacity = 0;
}
}
//--- 스택에 x를 푸시 ---//
public int push(int x) throws OverflowIntStackException {
if (ptr >= capacity) // 스택이 가득 참
throw new OverflowIntStackException();
return stk[ptr++] = x;
}
//--- 스택에서 데이터를 팝(정상에 있는 데이터를 꺼냄) ---//
public int pop() throws EmptyIntStackException {
if (ptr <= 0) // 스택이 빔
throw new EmptyIntStackException();
return stk[--ptr];
}
//--- 스택에서 데이터를 피크(peek, 정상에 있는 데이터를 들여다봄) ---//
public int peek() throws EmptyIntStackException {
if (ptr <= 0) // 스택이 빔
throw new EmptyIntStackException();
return stk[ptr - 1];
}
//--- 스택을 비움 ---//
public void clear() {
ptr = 0;
}
//--- 스택에서 x를 찾아 인덱스(없으면 –1)를 반환 ---//
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--) // 꼭대기 쪽부터 선형 검색
if (stk[i] == x)
return i; // 검색 성공
return -1; // 검색 실패
}
//--- 스택의 크기를 반환 ---//
public int getCapacity() {
return capacity;
}
//--- 스택에 쌓여있는 데이터 갯수를 반환 ---//
public int size() {
return ptr;
}
//--- 스택이 비어있는가? ---//
public boolean isEmpty() {
return ptr <= 0;
}
//--- 스택이 가득 찼는가? ---//
public boolean isFull() {
return ptr >= capacity;
}
//--- 스택 안의 모든 데이터를 바닥 → 정상 순서로 표시 ---//
public void dump() {
if (ptr <= 0)
System.out.println("스택이 비어있습니다.");
else {
for (int i = 0; i < ptr; i++)
System.out.print(stk[i] + " ");
System.out.println();
}
}
}큐 알아보기
큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아놓는 자료구조로, 데이터의 입력과 출력 순서는 선입선출입니다. 데이터를 넣는 작업을 인큐, 데이터를 꺼내는 작업을 디큐라고 합니다. 그리고 데이터가 나오는쪽을 프런트, 데이터를 넣는 쪽을 리어라고 합니다
큐 만들기
다음은 자바로 구현된 큐입니다:
// int형 고정 길이 큐(링 버퍼를 사용하지 않고 구현)
public class IntArrayQueue {
private int [] que; // 큐의 본체
private int capacity; // 큐의 용량
private int num; // 현재 데이터 개수
//--- 실행 시 예외 : 큐가 비어 있음 ---//
public class EmptyIntArrayQueueException extends RuntimeException {
public EmptyIntArrayQueueException() { }
}
//--- 실행 시 예외 : 큐가 가득 참 ---//
public class OverflowIntArrayQueueException extends RuntimeException {
public OverflowIntArrayQueueException() { }
}
//--- 생성자 ---//
public IntArrayQueue(int maxlen) {
num = 0;
capacity = maxlen;
try {
que = new int[capacity]; // 큐 본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
capacity = 0;
}
}
//--- 큐에 데이터를 인큐 ---//
public int enque(int x) throws OverflowIntArrayQueueException {
if (num >= capacity)
throw new OverflowIntArrayQueueException(); // 큐가 가득 참
que[num++] = x;
return x;
}
//--- 큐에서 데이터를 디큐 ---//
public int deque() throws EmptyIntArrayQueueException {
if (num <= 0)
throw new EmptyIntArrayQueueException(); // 큐가 비어 있음
int x = que[0];
for (int i = 0; i < num - 1; i++)
que[i] = que[i + 1];
num--;
return x;
}
//--- 큐에서 데이터를 피크(맨앞 데이터를 들여다봄 ) ---*/
public int peek() throws EmptyIntArrayQueueException {
if (num <= 0)
throw new EmptyIntArrayQueueException(); // 큐가 비어 있음
return que[num - 1];
}
//--- 큐에서 x를 검색하여 인덱스(발견하지 못하면 -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 capacity;
}
//--- 큐에 쌓여있는 데이터수를 반환합니다 ---//
public int size() {
return num;
}
//--- 큐가 비어 있는가? ---//
public boolean isEmpty() {
return num <= 0;
}
//--- 큐가 가득 찼는가? ---//
public boolean isFull() {
return num >= capacity;
}
//--- 큐 안의 모든 데이터를 맨앞 → 맨끝의 순서로 출력 ---//
public void dump() {
if (num <= 0)
System.out.println("큐가 비어 있습니다.");
else {
for (int i = 0; i < num; i++)
System.out.print(que[i] + " ");
System.out.println();
}
}
}링 버퍼 알아보기
배열 요소를 앞쪽으로 옮기지 않는 큐를 구현한 자료구조 입니다. 배열의 맨 뒤가 맨 앞과 연결되었다고 가정합니다. 큐와 마찬가지로 데이터의 입력과 출력 순서는 선입선출입니다. 데이터를 넣는 작업을 인큐, 데이터를 꺼내는 작업을 디큐라고 합니다. 그리고 데이터가 나오는쪽을 프런트, 데이터를 넣는 쪽을 리어라고 합니다.
링 버퍼는 데이터를 최신 n개만 유지하고, 오래된 데이터를 버리는 용도로 사용할 수 있습니다.
링 버퍼 만들기
다음은 자바로 링 버퍼입니다:
// int형 고정 길이 큐
public class IntQueue {
private int[] que; // 큐용 배열
private int capacity; // 큐의 크기
private int front; // 맨 처음 요소 커서
private int rear; // 맨 끝 요소 커서
private int num; // 현재 데이터 개수
//--- 실행시 예외: 큐가 비어있음 ---//
public class EmptyIntQueueException extends RuntimeException {
public EmptyIntQueueException() { }
}
//--- 실행시 예외: 큐가 가득 찼음 ---//
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() { }
}
//--- 생성자(constructor) ---//
public IntQueue(int maxlen) {
num = front = rear = 0;
capacity = maxlen;
try {
que = new int[capacity]; // 큐 본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
capacity = 0;
}
}
//--- 큐에 데이터를 인큐 ---//
public int enque(int x) throws OverflowIntQueueException {
if (num >= capacity)
throw new OverflowIntQueueException(); // 큐가 가득 찼음
que[rear++] = x;
num++;
if (rear == capacity)
rear = 0;
return x;
}
//--- 큐에서 데이터를 디큐 ---//
public int deque() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException(); // 큐가 비어있음
int x = que[front++];
num--;
if (front == capacity)
front = 0;
return x;
}
//--- 큐에서 데이터를 피크(프런트 데이터를 들여다봄) ---//
public int peek() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException(); // 큐가 비어있음
return que[front];
}
//--- 큐를 비움 ---//
public void clear() {
num = front = rear = 0;
}
//--- 큐에서 x를 검색하여 인덱스(찾지 못하면 –1)를 반환 ---//
public int indexOf(int x) {
for (int i = 0; i < num; i++) {
int idx = (i + front) % capacity;
if (que[idx] == x) // 검색 성공
return idx;
}
return -1; // 검색 실패
}
//--- 큐의 크기를 반환 ---//
public int getCapacity() {
return capacity;
}
//--- 큐에 쌓여 있는 데이터 개수를 반환 ---//
public int size() {
return num;
}
//--- 큐가 비어있는가? ---//
public boolean isEmpty() {
return num <= 0;
}
//--- 큐가 가득 찼는가? ---//
public boolean isFull() {
return num >= capacity;
}
//--- 큐 안의 모든 데이터를 프런트 → 리어 순으로 출력 ---//
public void dump() {
if (num <= 0)
System.out.println("큐가 비어있습니다.");
else {
for (int i = 0; i < num; i++)
System.out.print(que[(i + front) % capacity] + " ");
System.out.println();
}
}
}