[자료구조&알고리즘] stack(스택), queue(큐)

스택 (stack)

• 데이터를 일시적으로 저장하기 위한 자료구조
• 후입선출, LIFO(Last In First Out)
• 메서드를 호출하고 실행할 때 프로그램 내부에서 스택 사용

• arr[0] = bottom
• arr[n-1] = top

스택 만들기

필드 & 생성자

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 ▶ 다른 메서드가 존재하지 않는 배열에 잘못 접근하는 것을 막음

메서드

• ptr = 새로운 데이터를 삽입할 인덱스를 기억하는 용도로 사용하는 변수, 여기서는 포인터 변수를 의미하지 않음
• 위의 IntStack의 생성자와 메서드를 생성하면 ptr = 0 이상 max 이하
• 따라서 스택이 가득찼는지에 대한 검사는 등가 연산자(=)  사용 (관계 연산자(>=) 사용x)

if(ptr == max)

• 부등호로 판단하면 스택 본체 배열의 상한과 하한을 벗어나서 접근하는 것을 막을 수 있음
  프로그래밍 실수와 같은 원인으로 ptr 값이 잘 못 입력되면 max를 초과하는 것을 미리 방지 가능

push 메서드

//스택에 x를 푸시
	public int push(int x) throws OverflowIntStackException {
		if(ptr >= max) //용량보다 들어간 데이터 수가 크거나 같으면
			throw new OverflowIntStackException(); //예외 던짐
		return stk[ptr++] = x; //들어온 데이터 넣기
		//return문은 x를 저장한 후의 stk[ptr]의 값
	}

pop 메서드

//스택에서 데이터를 팝(정상에 있는 데이터를 꺼냄)
	public int pop() throws EmptyIntStackException {
		if (ptr <= 0) //스택이 비어있음
			throw new EmptyIntStackException(); //예외 던짐
		return stk[--ptr]; //return으로 ptr의 값을 감소시키고, stk[ptr]에 저장되어 있는 값을 반환
	}

peek 메서드

• stack의 top에 있는 데이터를 몰래 엿보는 메서드

//스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄)
	public int peak() throws EmptyIntStackException {
		if (ptr <= 0) //스택이 비어있음
			throw new EmptyIntStackException();
		return stk[ptr - 1]; //return으로 맨 위 = 가장 최근의 데이터 값을 반환
	}

indexOf 메서드

• 데이터가 포함되어 있는지 여부 (있으면 인덱스 값, 없으면 -1 반환)
• top [ptr] ▶ bottom [0] 쪽으로 선형 검색
• 꼭대기 쪽에서 스캔하는 이유는 먼저 팝이 되는 데이터를 찾기 위함
  (stack이니까 나중에 넣은 데이터가 먼저 pop 됨)

//스택에서 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; //검색 실패
	}

나머지 메서드

	//스택을 비움
	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 순서로 표시

실습

전체 메서드 사용

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;
			}
		}
	}
}

하나의 배열 - 두 개의 stack (enum 사용)

	//스택에 쌓인 데이터 수 반환
	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

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;
		}
	}
}

---

큐(queue)

• 데이터를 일시적으로 쌓아 놓은 자료구조
• 선입선출, FIFO(First In First Out)
• front: 데이터를 꺼내는 쪽
• rear: 데이터를 넣는 쪽

	예외 발생	true / false
추가 (enqueue)	add(a)	offer(a)
삭제 (dequeue)	remove()	poll()
검사 (peek)	element()	peek()

큐 만들기

배열 사용

• 효율 ▼

• 인큐의 경우 rear에 데이터 저장, 처리복잡도 O(1)
• 디큐의 경우 que[0]에서 꺼낸 후, 두번째 이후의 모든 요소를 모두 맨 앞으로 옮김, 처리복잡도 O(n)

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();
			}
		}
}

링 버퍼(ring buffer) 사용

• 처음과 끝이 연결되어 있다고 보는 자료구조
• 배열 요소를 앞쪽으로 옮기지 않음 = 처리복잡도 O(1)
• 논리적으로 순서를 식별하기 위해 front, rear 사용 (배열의  물리적 요소의 순서 x)
• rear: 맨 끝 요소의 하나 뒤의 인덱스 (다음 요소를 인큐할 위치를 미리 지정)

• 인큐한 다음의 상태는 현재 리어가 가지고 있는 위치에 저장 후, rear = rear+1 해줌
• 디큐한 다음의 상태는 front 값을 빼고, front = front+1 해줌
• front == rear 인 경우

queue 클래스 (que, max, front, rear, num, 생성자)

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 인큐메서드

//데이터 인큐
	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 디큐메서드

//데이터 디큐
	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

	//front 데이터를 들여다 봄
	public int peek() throws EmptyIntQueueException{
		if(num <= 0)
			throw new EmptyIntQueueException();
		return que[front];
	}

indexOf (인덱스 찾기)

	//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

	//큐 안의 모든 데이터를 출력, 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();
			}
		}	
	}

나머지

	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;
	}

Deque (덱)

• 양방향 대기열, Deque/Double Ended Queue
• 큐의 양쪽에서 삽입, 삭제 가능

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();
		}
	}
}

실습

데이터 검색 (몇 번째에 있는지 찾기)

	//임의의 데이터 검색 (검색 실패시 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부터 시작하면 됨

제네릭형으로 된 큐  - 추가 수정 필

실행시 예외

	//제너릭 클래스는 하위클래스가 될 수 없으므로 static을 붙여야 runtimeException에서 오류가 안남
	//실행 시 예외: stack이 비어있음
	public static class EmptyIntQueueException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
		public EmptyIntQueueException() {}
	}

생성자

	//생성자
	public Gqueue(int capacity) { //capacity = 용량 설정
		num = front = rear = 0;
		max = capacity;
		
		try {
			que = (E[])new Object[max]; //객체형이고, E[]로 형변환
		} catch (Exception e) {
			max = 0; 
		}
	}

전체 코드

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();
			}
		}
	}


}

ring buffer 활용

• 오래된 데이터를 버리는 용도
• 인큐는 무한히 할 수 있지만 배열에 저장되는 데이터는 가장 최근에 입력한 10개의 데이터만 남음

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]

---

예외 처리

RuntimeException

• 실행예외: 개발자가 직접 예외코드 처리

//실행 시 예외: stack이 비어있음
	public class EmptyIntQueueException extends RuntimeException { //실행예외: RuntimeException ▶ 개발자가 직접 예외코드 처리
		public EmptyIntQueueException() {}
	}

	//실행 시 예외: stack이 가득참
	public class OverflowIntQueueException extends RuntimeException {
		public OverflowIntQueueException() {}
	}

public int enque(int x) throws OverflowIntQueueException{
		if(num >= max)
			throw new OverflowIntQueueException();
}

public int deque() throws EmptyIntQueueException{
		if(num <= 0) //데이터 수 없으면
			throw new EmptyIntQueueException();
}