알고리즘1-4. 큐(Queue)

큐(Queue)

- 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다.

- 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)이다.

인큐(enqueue): 큐에 데이터를 넣는 작업	디큐(dequeue): 큐에서 데이터를 꺼내는 작업
프론트(front): 꺼내는 쪽	리어(rear): 데이터를 넣는 쪽

링버퍼로 큐 만들기

front = 5, rear = 5

디큐할 경우: 36(queue[0])을 디큐한 후 front값을 que[1]로 업데이트 해준다. (그 다음에 디큐할 경우를 대비해서)

인큐할 경우: queue[5]자리에 64를 저장하고 나서 rear값을 que[0]으로 업데이트 해준다.

- 링퍼버: 배열의 처음과 끝이 연결되었다고 보는 자료구조

- 여기서 어떤 요소가 첫 번째 요소인지 어떤 요소가 마지막 요소인지 식별하기 위한 변수 -> 프런트(front)와 리어(rear)

- 이렇게 큐를 구현하면 프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하기 때문에 요소 이동 문제를 해결할 수 있다.

프런트: 맨 처음 요소의 인덱스

리어: 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정)

Queue의 enqueue, dequeue, peek, info 메서드 구현한 뒤에 메서드 호출

1) main메서드가 포함된 IntQueueMain 파일과 queue에 필요한 메서드들을 선언한 (main메서드가 없는) IntQueue 파일 생성

2) IntQueueMain에서 먼저 queue의 객체를 생성하고 크기를 10으로 고정!

3) IntQueue에서 생성자를 생성하고, 지역변수를 만들어서 초기화

public class IntQueueMain {
	
	public static void main(String[] args) {
		
		IntQueue queue = new IntQueue(10); // 10개까지 저장할 수 있는 queue를 만들것이다!
	}
}

public class IntQueue {

	int capacity;  // 큐의 크기
	int[] queue; // 큐의 메모리를 선언
	
	// 초기화 정수:0, 실수:0.0 논리:false, 객체형:null / 멤버변수는 알아서 초기화가 된다.
	int front; // 제일 앞 위치
	int rear;  // 마지막 위치 (가변)
	int dataCnt; // queue의 데이터 갯수, (가변)
	
	public IntQueue() {}
	
	public IntQueue(int capacity) {
		this.capacity = capacity;
		queue = new int[capacity];
	}
}

4) 메뉴를 입력받을 메서드를 IntQueueMain에 따로 생성

import java.util.Scanner;

public class IntQueueMain {

	static Scanner s = new Scanner(System.in);
	
	// 메뉴를 입력받는 메서드(메뉴를 매서드로 기능을 뺐다.)
	static String getMenu() {
		System.out.print("[메뉴]1.enqueue 2.dequeue 3.peek 4.info 5.terminate ? ");
		return s.nextLine();
	}
	
	public static void main(String[] args) {

5) IntQueue에서 큐에 데이터를 추가하는 enqueue() 메서드 생성한다.

6) IntQueueMain에서 while문을 이용해 위에서 만든 getMenu()를 호출하고 switch문을 이용해 case "1" -> enqueue() 호출한다. 스캐너로 큐에 추가할 데이터를 받고 예외처리

// 큐에 데이터를 담는 메서드(enqueue)
public int enqueue(int data) throws QueueOverFlowException {  // 값이 링형식으로 계속 움직인다. 
	// 데이터가 가득 찼는지 확인
	// capacity: 용량, dataCnt: 현재 데이터 수
	if(capacity <= dataCnt) { // 최대용량보다 데이터값이 많으면 오버플로우 발생
		throw new QueueOverFlowException();
	}
        
	// 데이터를 큐에 담는다.(rear 위치에) 
	queue[rear++] = data;
	dataCnt++; // 데이터의 수 증가 ++ 앞뒤 상관 없음
		
	// rear의 위치를 링형으로 처리하기 (데이터를 빼고 나면 rear를 0으로)
	if(rear == capacity) { 
		rear = 0;
	}
        
	System.out.println("rear -> " + rear + ", 남은 데이터 -> " + dataCnt );
	return data;
}
    
// 오버플로우 발생시 처리할 예외
class QueueOverFlowException extends RuntimeException {
	QueueOverFlowException() { };
}

public class IntQueueMain {
	
	public static void main(String[] args) {
		while(true) {
			String menu = getMenu();
			if(menu.equals("5")) { // 5.terminate 선택시
				break;
			} else { // 그 외 메뉴선택시
				switch(menu) {
				case "1": // 큐에 데이터를 추가한다. 
				System.out.print("큐에 추가할 데이터: ");
				int data = Integer.parseInt(s.nextLine());
					
				try {
				int result = queue.enqueue(data);
				System.out.println("큐에 추가된 데이터는 " + result + "입니다.");
				}catch(Exception e) {
					System.out.println("큐가 가득찼습니다.");
				}
				break;
		}
}

7) IntQueue에서 큐에 데이터를 삭제하는 dequeue() 메서드 생성한다. (제일 앞에 데이터를 가져온다, front값 빼기)

8) IntQueueMain에서 dequeue( ) 호출 (큐에서 front 값 빼기)

// 큐에서 데이터를 얻어오기 메서드
public int dequeue() throws QueueEmptyException { // 예외 선언(dequeue()호출한 곳에서 예외처리해야함)
	
    if(dataCnt<=0) {  // 큐에 데이터가 없으면 예외 발생! 
		throw new QueueEmptyException();
	}
    
	// 큐에 데이터가 있을 때 실행됨
	dataCnt--; // 남은 객체의 수를 1 감소
	int deData = queue[front++];  // 제일 앞의 값 빼기 
	if(front==capacity) {
		front = 0;
	}
	System.out.println("front -> " + front + ", 남은 데이터 -> " + dataCnt );
	return deData;
}

// 큐가 비어있을 때 Empty예외 클래스 
class QueueEmptyException extends RuntimeException {
	 QueueEmptyException() { };
}

public class IntQueueMain {
	
	public static void main(String[] args) {
		case "2":  // 큐에서 데이터를 가져오기(제일 앞에)
		try {
			 int result = queue.dequeue();
			 System.out.println("큐에서 가져온 데이터는 " + result + "입니다.");
		}catch(Exception e) {
			System.out.println("큐가 비어 있습니다.");
		}
		break;
		}
	}
}

9) IntQueue에서 큐의 제일 앞(front) 데이터를 볼 수 있는 peek() 메서드 생성한다.

10) IntQueueMain에서 peek( ) 호출 (큐의 데이터값은 변경되지 않는다.)

// 큐의 제일 앞(front) 데이터를 구한다.
public int peek() throws QueueEmptyException {
	if(dataCnt<=0) {
		throw new QueueEmptyException();
	}
	return queue[front];
}

public class IntQueueMain {
	
	public static void main(String[] args) {
		case "3": // 큐의 제일 앞(front)에 있는 객체 얻어오기
		try {
			int result = queue.peek();
			System.out.println("큐에서 제일 앞의 데이터 -> " + result );
		}catch(Exception e) {
			System.out.println("큐가 비어 있습니다.");
		}
		break;
	}
}

11) IntQueue에서 큐의 크기, 데이터 수, front 인덱스, rear 인덱스, 처음값, 마지막값을 구하는 메서드를 생성한다.

12) IntQueueMain에서 각 메서드를 호출한 후 출력!(예외처리는 peek()메서드 때문에 해야한다(처음값))

// 큐의 크기
public int getCapacity() {
	return capacity;
}
	
// 큐의 데이터 수
public int getSize() {
	return dataCnt;
}
	
// front Index를 구해서 리턴
public int getFrontIndex() {
	return front;
}
	
// rear Index를 구해서 리턴
public int getRearIndex() {
	return rear;
}
	
// 마지막 값(제일 최근에 들어온 값)
public int getRearLastData() {
	return queue[rear-1];
}

public class IntQueueMain {
	
	public static void main(String[] args) {
		case "4":  // 4. 큐의 크기, 데이터 수, front 인덱스, rear 인덱스, 처음값, 마지막값을 구하라.
			try { // peek때문에
			System.out.println("큐의 크기: " + queue.getCapacity());
			System.out.println("데이터 수: " + queue.getSize());
			System.out.println("front: " + queue.getFrontIndex());
			System.out.println("rear: " + queue.getRearIndex());
			System.out.println("처음 값: " + queue.peek());
			System.out.println("마지막 값: " + queue.getRearLastData());
			}catch(Exception e) {
				e.printStackTrace();
			}
			break;
	}
}

<IntQueueMain 전체 코드>

package stack_queue;

import java.util.Scanner;

public class IntQueueMain {

	static Scanner s = new Scanner(System.in);
	
	// 메뉴를 입력받는 메서드(메뉴를 매서드로 기능을 뺐다.)
	static String getMenu() {
		System.out.print("[메뉴]1.enqueue 2.dequeue 3.peek 4.info 5.terminate ? ");
		return s.nextLine();
	}
	
	public static void main(String[] args) {
		
		IntQueue queue = new IntQueue(10); // 10개까지 저장할 수 있는 queue 객체 생성
		
		while(true) {
			String menu = getMenu();
			if(menu.equals("5")) { // 5.terminate 선택시
				break;
			} else { // 그 외 메뉴선택시
				switch(menu) {
				case "1": // 큐에 데이터를 추가한다. 
					System.out.print("큐에 추가할 데이터: ");
					int data = Integer.parseInt(s.nextLine());
					
					try {
					int result = queue.enqueue(data);
					System.out.println("큐에 추가된 데이터는 " + result + " 입니다.");
					}catch(Exception e) {
						System.out.println("큐가 가득찼습니다.");
					}
					break;
				
				case "2":  // 큐에서 데이터를 가져오기(제일 앞에)
					try {
						 int result = queue.dequeue();
						 System.out.println("큐에서 가져온 데이터는 " + result + "입니다.");
					}catch(Exception e) {
						System.out.println("큐가 비어 있습니다.");
					}
					break;
					
				case "3": // 큐의 제일 앞(front)에 있는 객체 얻어오기
					try {
						int result = queue.peek();
						System.out.println("큐에서 제일 앞의 데이터 -> " + result );
					}catch(Exception e) {
						System.out.println("큐가 비어 있습니다.");
					}
					break;
					
				case "4":  // 4. 큐의 크기, 데이터 수, front 인덱스, rear 인덱스, 처음값, 마지막값을 구하라.
					try { // peek때문에
					System.out.println("큐의 크기: " + queue.getCapacity());
					System.out.println("데이터 수: " + queue.getSize());
					System.out.println("front: " + queue.getFrontIndex());
					System.out.println("rear: " + queue.getRearIndex());
					System.out.println("처음 값: " + queue.peek());
					System.out.println("마지막 값: " + queue.getRearLastData());
					}catch(Exception e) {
						e.printStackTrace();
					}
					break;
					
				default: // 메뉴를 잘못 선택했을 때(그 외에)
					System.out.println("메뉴를 잘못선택하였습니다.");
				}
			}
		}
		System.out.println("프로그램이 종료되었습니다.");
	}
}

<IntQueue 전체 코드>

package stack_queue;

public class IntQueue {

	int capacity; 
	int[] queue; 
	
	int front;
	int rear; 
	int dataCnt; 
	
	public IntQueue() {}
	
	public IntQueue(int capacity) {
		this.capacity = capacity;
		queue = new int[capacity];
		
	}
	
	// 큐에 데이터를 담는 메서드(enqueue)
	public int enqueue(int data) throws QueueOverFlowException { 

		if(capacity <= dataCnt) { // 오버플로우 발생
			throw new QueueOverFlowException();
		}
		// 데이터를 큐에 담는다.(rear:위치에) 
		queue[rear++] = data;
		dataCnt++; 
		

		if(rear == capacity) { 
			rear = 0;
		}
		System.out.println("rear -> " + rear + ", 남은 데이터 -> " + dataCnt );
		return data;
	}
	
	// 큐에서 데이터를 얻어오기 메서드
	public int dequeue() throws QueueEmptyException {
		if(dataCnt<=0) {
			throw new QueueEmptyException();
		}

		dataCnt--; 
		int deData = queue[front++];
		if(front==capacity) {
			front = 0;
		}
		System.out.println("front -> " + front + ", 남은 데이터 -> " + dataCnt );
		return deData;
	}
	
	// 큐의 제일 앞(front) 데이터를 구한다.
	public int peek() throws QueueEmptyException {
		if(dataCnt<=0) {
			throw new QueueEmptyException();
		}
		return queue[front];
	}
	
	// 큐의 크기
	public int getCapacity() {
		return capacity;
	}
	
	// 큐의 데이터 수
	public int getSize() {
		return dataCnt;
	}
	
	// front Index를 구해서 리턴
	public int getFrontIndex() {
		return front;
	}
	
	// rear Index를 구해서 리턴
	public int getRearIndex() {
		return rear;
	}
	
	// 마지막 값
	public int getRearLastData() {
		return queue[rear-1];
	}
	
	// 오버플로우 발생시 처리할 예외
	class QueueOverFlowException extends RuntimeException {
		QueueOverFlowException() { };
	}
	
	// 큐가 비어있을 때 Empty예외 클래스 
	class QueueEmptyException extends RuntimeException {
		 QueueEmptyException() { };
	}
}

저작자표시

'멀티캠퍼스 풀스택 과정 > 알고리즘' 카테고리의 다른 글

알고리즘2-1. 선형리스트(LinkedList 연결리스트) (0)	2022.01.27
알고리즘1-6. 정렬(Sorting): 버블정렬, 선택정렬, 삽입정렬, 퀵정렬 (0)	2022.01.26
알고리즘1-5. 재귀알고리즘 (0)	2022.01.26
알고리즘1-2. 검색 알고리즘(선형검색, 이진검색) (0)	2022.01.25
알고리즘1-1. 알고리즘이란? (0)	2022.01.25