728x90
1. 스택 (stack)
- 데이터를 일시적으로 저장하기 위한 자료구조
- 후입선출, LIFO(Last In First Out)
- 메서드를 호출하고 실행할 때 프로그램 내부에서 스택 사용
- arr[0] = bottom
- arr[n-1] = top
1.1. 스택 만들기
1.1.1. 필드 & 생성자
<java />
package chap04_1;
public class IntStack {
private int max; //스택 용량, 배열 길이
private int ptr; //스택 포인터, 현재 쌓여 있는 데이터의 수(인덱스가 아님)
private int[] stk; //스택 본체
//실제로는 본체를 참조하는 배열 변수로 배열 본체는 생성자에서 생성함
//실행 시 예외: stack이 비어있음
public class EmptyIntStackException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntStackException() {}
}
//실행 시 예외: stack이 가득참
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException() {}
}
//생성자
public IntStack(int capacity) {
max = capacity;
ptr = 0;
try {
stk = new int[max]; //스택 본체용 배열을 max 길이 맞춰서 생성
} catch (Exception e) { //생성할 수 없음
max = 0;
}
}
}
- 예외 처리 RuntimeException
- 맨 처음 stack 생성시에는 비어있기 때문에 ptr = 0
- 매개변수를 받아서 스택의 용량인 max에 넣고, 동시에 용량이 max인 배열 stk의 본체를 생성
- OutOfMemoryError 발생시 max = 0 ▶ 다른 메서드가 존재하지 않는 배열에 잘못 접근하는 것을 막음
1.1.2. 메서드
- ptr = 새로운 데이터를 삽입할 인덱스를 기억하는 용도로 사용하는 변수, 여기서는 포인터 변수를 의미하지 않음
- 위의 IntStack의 생성자와 메서드를 생성하면 ptr = 0 이상 max 이하
- 따라서 스택이 가득찼는지에 대한 검사는 등가 연산자(=) 사용 (관계 연산자(>=) 사용x)
<java />
if(ptr == max)
- 부등호로 판단하면 스택 본체 배열의 상한과 하한을 벗어나서 접근하는 것을 막을 수 있음
프로그래밍 실수와 같은 원인으로 ptr 값이 잘 못 입력되면 max를 초과하는 것을 미리 방지 가능
push 메서드
<java />
//스택에 x를 푸시
public int push(int x) throws OverflowIntStackException {
if(ptr >= max) //용량보다 들어간 데이터 수가 크거나 같으면
throw new OverflowIntStackException(); //예외 던짐
return stk[ptr++] = x; //들어온 데이터 넣기
//return문은 x를 저장한 후의 stk[ptr]의 값
}
pop 메서드
<java />
//스택에서 데이터를 팝(정상에 있는 데이터를 꺼냄)
public int pop() throws EmptyIntStackException {
if (ptr <= 0) //스택이 비어있음
throw new EmptyIntStackException(); //예외 던짐
return stk[--ptr]; //return으로 ptr의 값을 감소시키고, stk[ptr]에 저장되어 있는 값을 반환
}
peek 메서드
- stack의 top에 있는 데이터를 몰래 엿보는 메서드
<java />
//스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄)
public int peak() throws EmptyIntStackException {
if (ptr <= 0) //스택이 비어있음
throw new EmptyIntStackException();
return stk[ptr - 1]; //return으로 맨 위 = 가장 최근의 데이터 값을 반환
}
indexOf 메서드
- 데이터가 포함되어 있는지 여부 (있으면 인덱스 값, 없으면 -1 반환)
- top [ptr] ▶ bottom [0] 쪽으로 선형 검색
- 꼭대기 쪽에서 스캔하는 이유는 먼저 팝이 되는 데이터를 찾기 위함
(stack이니까 나중에 넣은 데이터가 먼저 pop 됨)
<java />
//스택에서 x를 찾아 인덱스(없으면 -1)를 반환
public int indexOf(int x) {
for(int i = ptr-1; i >= 0; i--) { //top부터 bottom까지 선형 검색, ptr-1 범위 확인!!!
if(stk[i] == x) //x값과 같은 값이 있으면
return i; //검색 성공
}
return -1; //검색 실패
}
나머지 메서드
<java />
//스택을 비움
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;
}
//스택 안의 모든 데이터를 바닥 → 꼭대기 순서로 출력
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();
}
}
- 모든 작업은 스택 포인터를 바탕으로 이루어짐
- 배열 요솟값을 변경할 필요가 없고, 모든 요소의 삭제는 스택 포인터 ptr = 0;으로 하면 끝남
- dump 메서드는 bottom ▶ top 순서로 표시
1.2. 실습
1.2.1. 전체 메서드 사용
<java />
package chap04_1;
import java.util.Scanner;
public class IntStackTester {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//IntStack 클래스 만듦
IntStack s = new IntStack(64); //최대 64를 푸시할 수 있는 스택
while(true) { //무한반복
System.out.println("현재 데이터 수: " + s.size() + " /"
+ s.capacity());
System.out.println("(1)푸시 (2)팝 (3)피크 " +
"(4)덤프 (5)찾기 (6)삭제 " +
"(7)정보 (0)종료");
int menu = scan.nextInt();
if(menu == 0) break; //0 누르면 종료
int x; //scan으로 값 넣을 데이터 변수
switch (menu) {
case 1: //푸시
System.out.print("데이터: ");
x = scan.nextInt();
try {
s.push(x);
} catch (Exception e) {
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2: //팝
System.out.print("데이터: ");
x = scan.nextInt();
try {
x = s.pop();
System.out.println("팝한 데이터는 " + x + "입니다.");
} catch (Exception e) {
System.out.println("스택이 비어있습니다.");
}
break;
case 3: //피크
try {
x = s.peak();
System.out.println("피크한 데이터는 " + x + "입니다.");
} catch (Exception e) {
System.out.println("스택이 비어있습니다.");
}
break;
case 4: //덤프, 데이터 다 확인하니까 필요x0
s.dump();
break;
case 5: //검색, 찾기
System.out.print("찾는 데이터: ");
x = scan.nextInt();
int idx = s.indexOf(x); //인덱스 값 반환
if(idx >= 0) { //idx 값이 있으면
System.out.println(x + "의 값은 " + (idx+1) + "번째에 있습니다.");
} else { //idx = -1
System.out.println("값을 찾을 수 없습니다.");
}
break;
case 6: //삭제
s.clear();
break;
case 7: //정보
System.out.println("현재 스택의 용량은 " + s.capacity() + "입니다.");
System.out.println("현재 스택의 데이터 수는 " + s.size() + "개 입니다.");
//if 사용
System.out.print("현재 스택은 ");
if(s.isEmpty() == false) {
System.out.println("비어있습니다.");
} else {
System.out.println("비어있지 않습니다.");
};
//3항 연산자 사용, 조건절 ? ture : false
System.out.println("현재 스택은 " + (s.isFull() ? "가득 차 있습니다." : "가득차 있지 않습니다."));
break;
}
}
}
}
1.2.2. 하나의 배열 - 두 개의 stack (enum 사용)
<java />
//스택에 쌓인 데이터 수 반환
public int size(AB sw) {
switch (sw) {
case StackA:
return ptrA;
case StackB:
return max - ptrB - 1;
}
return 0;
}
- ptrB는 스택이 비어있는 경우에는 max - 1
따라서 max - ptrB - 1을 계산하면, 스택의 전체 용량인 max에서 두 번째 스택(StackB)에 저장된 데이터의 개수를 나타내는 ptrB를 빼고, 1을 빼는 것으로써 두 번째 스택(StackB)에 저장된 데이터의 수를 계산 가능 - 예를 들어, max가 10이고 ptrB가 7이라면, max - ptrB - 1은 10 - 7 - 1 = 2로 두 번째 스택(StackB)에는 현재 2개의 데이터가 저장
이렇게 두 번째 스택(StackB)에 저장된 데이터의 수를 계산하는 이유? 스택의 상태를 파악하기 위
전체코드
더보기
Quiz3
<java />
package chap04_1;
public class Quiz3 {
private int max; //스택 용량
//다중 스택에서는 ptr이 스택포인터로서의 역할, 다음에 저장될 데이터의 인덱스값을 갖고있는 변수
private int ptrA; //스택 포인터A
private int ptrB; //스택 포인터B
private int[] stk; //스택 본체
//실행 시 예외: stack이 비어있음
public class EmptyIntStackException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntStackException() {}
}
//실행 시 예외: stack이 가득참
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException() {}
}
//생성자
public Quiz3(int capacity) {
max = capacity;
ptrA = 0;
ptrB = max - 1;
try {
stk = new int[max]; //스택 본체용 배열 생성
} catch (Exception e) {
max = 0;
}
}
//stack 선택 사용을 위한 열거형
enum AB{
StackA,
StackB
}
//push stackA or stackB
public int push(AB sw, int x) throws OverflowIntStackException {
if(ptrA >= ptrB + 1) //그림 잘 보고 이해
throw new OverflowIntStackException();
switch (sw) {
case StackA :
stk[ptrA++] = x;
break;
case StackB :
stk[ptrB--] = x;
break;
}
return x;
}
//pop stackA or stackB (꼭대기의 데이터를 꺼냄)
public int pop(AB sw) throws EmptyIntStackException {
int x = 0; //꺼낸 데이터를 넣을 변수
switch (sw) {
case StackA:
if(ptrA <= 0)
throw new EmptyIntStackException();
x = stk[--ptrA]; //ptr 기준 꼭대기 (비어있는 곳을 가리키기 때문에 감소해주고 값 얻기)
break;
case StackB:
if(ptrB >= max - 1)
throw new EmptyIntStackException();
x = stk[++ptrB];
break;
}
return x;
}
//peak (꼭대기의 데이터를 살펴봄)
public int peek(AB sw) throws EmptyIntStackException {
int x = 0;
switch (sw) {
case StackA:
if(ptrA <= 0)
throw new EmptyIntStackException();
x = stk[ptrA - 1];
break;
case StackB:
if(ptrB >= max -1)
throw new EmptyIntStackException();
x = stk[ptrB + 1];
break;
}
return x;
}
//스택에서 x 검색하여 인덱스 반환 (없으면 -1)
public int indexOf(AB sw, int x) {
switch (sw) {
case StackA:
for(int i = ptrA - 1; i >= 0; i--) {
if(stk[i] == x) //Gsrack에서는 E형 타입이니까 equals로 비교
return i; //검색 성공
}
break;
case StackB:
for(int i = ptrB + 1; i <= max; i++) {
if(stk[i] == x)
return i;
}
break;
}
return -1; //검색 실패
}
//스택을 비움 (A, B 선택해서 비우기 가능)
public void clear(AB sw) {
switch (sw) {
case StackA:
ptrA = 0;
break;
case StackB :
ptrB = max - 1;
break;
}
}
//스택의 용량을 반환 (A, B의 합계)
public int capacity() {
return max;
}
//스택에 쌓인 데이터 수 반환
public int size(AB sw) {
switch (sw) {
case StackA:
return ptrA;
case StackB:
return max - ptrB - 1;
}
return 0;
}
//스택이 비어 있는가?
public boolean isEmpty(AB sw) {
switch (sw) {
case StackA:
return ptrA <= 0; //비어있으면 true,
case StackB:
return ptrB >= max - 1;
}
return true; //스택 선택이 잘못된 경우 일반적으로 스택이 비어있다고 가정
}
// 스택이 가득 찼는가?
public boolean isFull() {
return ptrA >= ptrB + 1; //둘이 겹쳐질 때
}
// 스택 안의 데이터를 바닥 → 꼭대기의 차례로 나타냄
public void dump(AB sw) {
switch (sw) {
case StackA:
if (ptrA <= 0)
System.out.println("스택이 비었습니다.");
else {
for (int i = 0; i < ptrA; i++)
System.out.print(stk[i] + " ");
System.out.println();
}
break;
case StackB:
if (ptrB >= max - 1)
System.out.println("스택이 비었습니다.");
else {
for (int i = max - 1; i > ptrB; i--)
System.out.print(stk[i] + " ");
System.out.println();
}
break;
}
}
}
2. 큐(queue)
- 데이터를 일시적으로 쌓아 놓은 자료구조
- 선입선출, FIFO(First In First Out)
- front: 데이터를 꺼내는 쪽
- rear: 데이터를 넣는 쪽
| 예외 발생 | true / false | |
| 추가 (enqueue) | add(a) | offer(a) |
| 삭제 (dequeue) | remove() | poll() |
| 검사 (peek) | element() | peek() |
2.1. 큐 만들기
2.1.1. 배열 사용
- 효율 ▼
- 인큐의 경우 rear에 데이터 저장, 처리복잡도 O(1)
- 디큐의 경우 que[0]에서 꺼낸 후, 두번째 이후의 모든 요소를 모두 맨 앞으로 옮김, 처리복잡도 O(n)
<java />
package chap04_1;
//배열 방식으로 queue
public class IntAryQueue {
private int max; //총 용량
private int num; //데이터 수
private int[] que; //본체
//실행 시 예외: stack이 비어있음
public class EmptyIntAryQueueException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntAryQueueException() {}
}
//실행 시 예외: stack이 가득참
public class OverflowIntAryQueueException extends RuntimeException {
public OverflowIntAryQueueException() {}
}
//생성자
public IntAryQueue(int capacity) {
max = capacity;
num = 0; //데이터 수
try {
que = new int[max]; //que 본체용 배열 생성
} catch (Exception e) {
max = 0;
}
}
//인큐
public int enque(int x) throws OverflowIntAryQueueException {
if(num >= max)
throw new OverflowIntAryQueueException(); //큐 가득참
return que[num++] = x;
}
//디큐
//데이터를 꺼내고 앞으로 한칸씩 옮기기 - queue에서는 선입선출이므로 [0]번째 부터 나옴
public int deque() throws EmptyIntAryQueueException {
if(num <= 0)
throw new EmptyIntAryQueueException();
int x = que[0]; //제일 앞에 있는 값 꺼내기
//앞으로 한칸씩 옮기기
for(int i = 0 ; i < num; i++) {
que[i] = que[i + 1];
}
num--; //하나씩 데이터가 줄어드니까 num도 하나씩 줄어듦
return x;
}
// 큐에서 데이터를 피크(머리 데이터를 살펴봄)
public int peek() throws EmptyIntAryQueueException {
if (num <= 0)
throw new EmptyIntAryQueueException(); // 큐가 비어 있음
return que[num - 1]; //가장 최근의 데이터 값 반환
}
// 큐에서 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 void dump() {
if (num <= 0)
System.out.println("큐가 비었습니다.");
else {
for (int i = 0; i < num; i++)
System.out.print(que[i] + " ");
System.out.println();
}
}
}
2.1.2. 링 버퍼(ring buffer) 사용
- 처음과 끝이 연결되어 있다고 보는 자료구조
- 배열 요소를 앞쪽으로 옮기지 않음 = 처리복잡도 O(1)
- 논리적으로 순서를 식별하기 위해 front, rear 사용 (배열의 물리적 요소의 순서 x)
- rear: 맨 끝 요소의 하나 뒤의 인덱스 (다음 요소를 인큐할 위치를 미리 지정)
- 인큐한 다음의 상태는 현재 리어가 가지고 있는 위치에 저장 후, rear = rear+1 해줌
- 디큐한 다음의 상태는 front 값을 빼고, front = front+1 해줌
- front == rear 인 경우
queue 클래스 (que, max, front, rear, num, 생성자)
<java />
package chap04_1;
//스트링 버퍼 방식으로 queue
public class IntQueue {
private int max; //큐의 총 용량 [0]~[11] = 12
private int front; //첫번째 요소 커서
private int rear; //마지막 요소 커서
private int num; //현재 데이터 수
private int[ ] que; //큐 본체
//실행 시 예외: stack이 비어있음
public class EmptyIntQueueException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntQueueException() {}
}
//실행 시 예외: stack이 가득참
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {}
}
//생성자
public IntQueue(int capacity) {
num = front = rear = 0; //기본 초기화
max = capacity;
try {
que = new int[max];
} catch (Exception e) {
max = 0;
}
}
}
enque 인큐메서드
<java />
//데이터 인큐
public int enque(int x) throws OverflowIntQueueException{
if(num >= max)
throw new OverflowIntQueueException();
que[rear++] = x; //x를 현재 rear에 넣고 rear++
num++; //데이터 수 증가
//ex) 0~11 = max = 12, rear[11]에 넣고 rear++하면 rear[12]여야하는데 없으니까 rear[0]으로
if(rear == max) //++한 rear가 큐의 최대 용량인 max와 같아질 경우
rear = 0; //rear를 배열의 처음인 0으로 변경
return x;
}
- 인큐에서 rear가 다시 처음 위치인 rear[0] 돌아가게 되는 조건 확인
deque 디큐메서드
<java />
//데이터 디큐
public int deque() throws EmptyIntQueueException{
if(num <= 0) //데이터 수 없으면
throw new EmptyIntQueueException();
int x = que[front++]; //현재 front에서 빼고, front++
num--; //데이터 수 감소
if(front == max) //++한 front가 큐의 최대 용량인 max와 같아질 경우
front = 0; //front를 배열의 처음인 0으로 변경
return x;
}
peek
<java />
//front 데이터를 들여다 봄
public int peek() throws EmptyIntQueueException{
if(num <= 0)
throw new EmptyIntQueueException();
return que[front];
}
indexOf (인덱스 찾기)
<java />
//x를 검색하여 인덱스 반환 (못 찾으면 -1)
public int indexOf(int x) {
for(int i = 0; i < num; i++) { //데이터 개수 만큼만 반복(인덱스 아님)
//front → rear 순으로 선형 검색
//시작은 front부터
int idx = (i + front) % max; //인덱스 설정, 12 % 12 = 0이 되므로 처음으로 돌아감
if(que[idx] == x) { //검색 성공
return x;
}
}
return -1; //실패
}
dump
<java />
//큐 안의 모든 데이터를 출력, front → rear 순서
public void dump() {
if(num <= 0) {
System.out.println("큐가 비어있습니다.");
} else {
for(int i = 0; i < num; i++) {
System.out.print(que[(i + front) % max] + "");
System.out.println();
}
}
}
나머지
<java />
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;
}
2.1.3. Deque (덱)
- 양방향 대기열, Deque/Double Ended Queue
- 큐의 양쪽에서 삽입, 삭제 가능
<java />
package chap04_1;
public class IntDeque {
private int max; //큐의 총 용량
private int num; //현재 데이터 수
private int front; //첫번째 요소 커서
private int rear; //마지막 요소 커서
private int[] que; //큐 본체
//실행 시 예외: stack이 비어있음
public class EmptyIntDequeException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntDequeException() {}
}
//실행 시 예외: stack이 가득참
public class OverflowIntDequeException extends RuntimeException {
public OverflowIntDequeException() {}
}
//생성자
public IntDeque(int capacity) {
num = front = rear = 0;
max = capacity;
try {
que = new int[max];
} catch (OutOfMemoryError e) { //max = 0으로 없애기
max = 0;
}
}
//덱(deck)에 데이터를 머리쪽부터 인큐
public int endueFront(int x) throws OverflowIntDequeException{
if(num >= max)
throw new OverflowIntDequeException();
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)의 머리부터 데이터를 피크(머리데이터를 살펴봄)
public int peekFront() throws EmptyIntDequeException {
if (num <= 0)
throw new EmptyIntDequeException(); // 덱(deck)이 비어 있음
return que[front];
}
// 덱(deck)의 꼬리부터 데이터를 피크(꼬리데이터를 살펴봄)
public int peekRear() throws EmptyIntDequeException {
if (num <= 0)
throw new EmptyIntDequeException(); // 덱(deck)이 비어 있음
return que[rear == 0 ? max - 1 : rear - 1];
}
// 덱(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;
}
// 덱(deck)내의 데이터를 머리→꼬리의 차례로 나타냄
public void dump() {
if (num <= 0)
System.out.println("덱(deck)이 비었습니다.");
else {
for (int i = 0; i < num; i++)
System.out.print(que[(i + front) % max] + " ");
System.out.println();
}
}
}
2.2. 실습
2.2.1. 데이터 검색 (몇 번째에 있는지 찾기)
<java />
//임의의 데이터 검색 (검색 실패시 0, 프런트에 있는 경우 1)
public int search(int x) {
for(int i = 1; i <= num; i++) {
int idx = (i + front) % max;
if(que[idx] == x) {
return i;
}
}
return 0; //검색 실패
}
- IndexOf랑 구분 필요
- 똑같이 진행되는데 인덱스 + 1 혹은 i의 기준을 1부터 시작하면 됨
2.2.2. 제네릭형으로 된 큐 - 추가 수정 필
실행시 예외
<java />
//제너릭 클래스는 하위클래스가 될 수 없으므로 static을 붙여야 runtimeException에서 오류가 안남
//실행 시 예외: stack이 비어있음
public static class EmptyIntQueueException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntQueueException() {}
}
생성자
<java />
//생성자
public Gqueue(int capacity) { //capacity = 용량 설정
num = front = rear = 0;
max = capacity;
try {
que = (E[])new Object[max]; //객체형이고, E[]로 형변환
} catch (Exception e) {
max = 0;
}
}
전체 코드
더보기
<java />
package chap04_1;
public class Gqueue<E> {
private int max; //용량, 인덱스+1
private int front;
private int rear;
private int num; //데이터 수
private E[] que;
//제너릭 클래스는 하위클래스가 될 수 없으므로 static을 붙여야 runtimeException에서 오류가 안남
//실행 시 예외: stack이 비어있음
public static class EmptyIntQueueException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntQueueException() {}
}
//실행 시 예외: stack이 가득참
public static class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {}
}
//생성자
public Gqueue(int capacity) { //capacity = 용량 설정
num = front = rear = 0;
max = capacity;
try {
que = (E[])new Object[max]; //객체형이고, E[]로 형변환
} catch (Exception e) {
max = 0;
}
}
//enqueue - 예외
public E enque(E x) throws OverflowIntQueueException {
if(num >= max)
throw new OverflowIntQueueException();
que[rear++] = x; //x를 현재 rear에 넣고, rear++해서 다음 인덱스로
num++;
if(rear == max)
rear = 0;
return x;
}
//dequeue - 예외
public E dequeue() throws EmptyIntQueueException {
if(num <= 0) //큐가 비어있으면
throw new EmptyIntQueueException();
E x = que[front++]; //front의 인덱스값 꺼내고 front++
num--; //개수는 하나 줄이기
if(front == max) //front 위치가 max 용량과 같으면 front = 0으로 설정
front = 0;
return x;
}
//peek - 예외
public E peek() throws EmptyIntQueueException{
if(num <= 0)
throw new EmptyIntQueueException();
E x = que[front];
return x;
}
//indexOf - 인덱스 반환, 없으면 -1
public int indexOf(E x) {
for(int i = 0; i < num; i++) {
if(que[(i+front) % max] == x) {
return i + front; //인덱스값 반환
}
}
return -1; //실패
}
//search - 몇 번째인지 반환, 없으면 -1
public int search(E x) {
for(int i = 0; i < num; i++) {
if(que[(i + front) % max] == x) {
return i + 1;
}
}
return -1;
}
//queue를 비움
public void clear() {
num = front = rear = 0;
}
//queue 용량
public int capacity() {
return max;
}
//queue 데이터의 수
public int size() {
return num;
}
public boolean isEmpty() {
return num <= 0;
}
public boolean isFull() {
return num >= max;
}
//머리 → 꼬리의 차례로 큐 안의 데이터를 나타냄
public void dump() {
if(num <= 0) {
System.out.println("큐가 비었습니다.");
} else {
for(int i = 0; i < num; i++) {
System.out.print(que[(i + front) % max].toString() + "");
System.out.println();
}
}
}
}
2.3. ring buffer 활용
- 오래된 데이터를 버리는 용도
- 인큐는 무한히 할 수 있지만 배열에 저장되는 데이터는 가장 최근에 입력한 10개의 데이터만 남음
<java />
package chap04_1;
import java.util.Scanner;
public class LastNElements {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
final int N = 10; //크기 10으로 고정
int[] a = new int[N]; //입력 받은 값을 저장
int cnt = 0; //입력 받은 개수
int retry; //다시?
System.out.println("정수를 입력하세요");
do {
System.out.printf("%d번째 정수: ", cnt + 1);
a[cnt++ % N] = scan.nextInt(); //cnt를 넣고, ++
System.out.print("계속 할까요? (1: 예, 0: 아니오) : ");
retry = scan.nextInt();
} while (retry == 1);
int i = cnt - N; //1. 넣은 정수가 N보다 많으면 i의 시작값이 바뀜
if(i < 0) i = 0; //2. 넣은 정수의 개수가 N보다 작으면 i=0부터 돌면 됨
for( ; i < cnt; i++) { //i의 초기값은 위에서 선언
System.out.printf("%2d번째의 정수=%d\n", i+1, a[i%N]);
}
}
}
- 입력한 값을 저장하는 위치의 인덱스: cnt++ % N
- 입력한 값을 출력하는 방법
1. 입력한 값의 개수(cnt)가 N이하: a[0] ~ a[cnt-1]
2. 개수가 N이 넘어가는 경우(ex 12개): a[2], a[3] ~ a[9], a[0], a[1]
3. 예외 처리
3.1. RuntimeException
- 실행예외: 개발자가 직접 예외코드 처리
<java />
//실행 시 예외: stack이 비어있음
public class EmptyIntQueueException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
public EmptyIntQueueException() {}
}
//실행 시 예외: stack이 가득참
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {}
}
<java />
public int enque(int x) throws OverflowIntQueueException{
if(num >= max)
throw new OverflowIntQueueException();
}
public int deque() throws EmptyIntQueueException{
if(num <= 0) //데이터 수 없으면
throw new EmptyIntQueueException();
}728x90
'Study > Data Structure&Algorithm' 카테고리의 다른 글
| [자료구조&알고리즘] 셸, 퀵, 병합, 힙, 도수(계수) 정렬 (0) | 2023.06.02 |
|---|---|
| [자료구조&알고리즘] 재귀 알고리즘(팩토리얼, 유클리드 호제법), 하노이의 탑, N퀸 문제 / 백트래킹 (0) | 2023.05.08 |
| [알고리즘] 유클리드 호제법 (Euclidean algorithm), 약수, 배수 (0) | 2023.04.25 |
| [자료구조&알고리즘] 검색(검색 알고리즘, 선형검색, 이진검색) (0) | 2023.04.25 |
| [자료구조&알고리즘] 기본 자료구조(배열, 클래스) (0) | 2023.04.18 |
