반응형
자료구조에서 중요한 개념인 Stack과 Queue를 코드로 직접 구현해보았다.
'Doit! 자료구조와 함께 배우는 알고리즘 입문 자바편'을 참고하여 작성하였습니다.
❑ 자바에서 Stack 배열로 구현하기
더보기
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(){};
}
// 생성자
public IntStack(int maxlen) {
ptr = 0;
capacity = maxlen;
try {
stk = new int[capacity];
} catch (OutOfMemoryError e) {
capacity = 0;
}
}
// 스택에 x push
public int push(int x) throws OverflowIntStackException {
if(ptr >= capacity) {
throw new OverflowIntStackException();
}
return stk[ptr++] = x;
}
// 스택에서 데이터를 pop
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;
// return ptr == 0; 으로도 가능
}
// 스택이 가득 찼는가?
public boolean isFull() {
return ptr >= capacity;
}
// 스택 안의 모든 데이터를 bottom-> top 순서로 출력
public void dump() {
if(ptr <= 0) {
System.out.println("Stack is Empty!");
}
else {
for(int i = 0; i < ptr; i++)
System.out.print(stk[i]+ " ");
System.out.println();
}
}
}
❑ Stack 클래스 테스트 하기
더보기
import java.util.Scanner;
public class IntStackTester {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
IntStack s = new IntStack(64);
while(true) {
System.out.println();
System.out.printf("present data count: %d / %d\n", s.size(), s.getCapacity());
System.out.print("(1)push (2)pop (3)peek (4)dump (5)clear (6)getCapacity (7)indexOf (8)isFull (0)exit : ");
int menu = stdIn.nextInt();
if(menu == 0) break; //exit
int x;
switch(menu) {
case 1 : // push
System.out.print("데이터: ");
x = stdIn.nextInt();
try {
s.push(x);
}catch (IntStack.OverflowIntStackException e) {
System.out.println("Stack is full!!");
}
break;
case 2: // pop
try {
x = s.pop();
System.out.println("pop data is " + x + ".");
} catch (IntStack.EmptyIntStackException e) {
System.out.println("Stack is Empty!!");
}
break;
case 3: // peek
try {
x = s.peek();
System.out.println("peek data is " + x + ".");
} catch (IntStack.EmptyIntStackException e) {
System.out.println("Stack is Empty!!");
}
break;
case 4: // dump
s.dump();
break;
case 5: // clear
s.clear();
break;
case 6: // getCapacity
System.out.println("Capacity : " + s.getCapacity());
break;
case 7: //indexOf
System.out.print("input you want to find : ");
x = stdIn.nextInt();
System.out.println(x + " is in " + s.indexOf(x));
break;
case 8:
System.out.println("Stack is Full? " + s.isFull());
break;
}
}
}
}
❑ 자바에서 Queue 배열로 구현하기
더보기
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() {}
}
// 생성자
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;
}
// 큐에서 데이터를 피크(front 데이터를 들여다봄)
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 int search(int x) {
for(int i = 0; i < num; i++) {
if(que[(i + front) % capacity] == x)
return i + 1;
}
return 0;
}
// 큐 안의 모든 데이터를 front -> rear 순으로 출력
public void dump() {
if(num <= 0)
System.out.println("큐가 비어있습니다.");
else {
for(int i = 0; i < num; i++) {
System.out.println(que[(i + front) % capacity] + " ");
}
System.out.println();
}
}
}
❑ Queue 클래스 테스트하기
더보기
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() {}
}
// 생성자
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;
}
// 큐에서 데이터를 피크(front 데이터를 들여다봄)
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 int search(int x) {
for(int i = 0; i < num; i++) {
if(que[(i + front) % capacity] == x)
return i + 1;
}
return 0;
}
// 큐 안의 모든 데이터를 front -> rear 순으로 출력
public void dump() {
if(num <= 0)
System.out.println("큐가 비어있습니다.");
else {
for(int i = 0; i < num; i++) {
System.out.println(que[(i + front) % capacity] + " ");
}
System.out.println();
}
}
}
반응형