큐

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
  큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
• 선입선출구조(FIFO)
  큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(first in)된 원소는 가장 먼저 삭제(first out)된다.

• 큐의 시작과 끝이 같다면 큐는 비어 있는 것
• 머리는 꼬리와 같이 원소를 가리키는 것이 아니라 첫번째 원소 앞에 -1을 처음에는 가리킨다.

• enQueue->rear++
• deQueue->front++

선형큐

• 1차원 배열을 이용한 큐
  • 큐의 크기=배열의 크기-size()
  • front : 마지막으로 삭제된 인덱스=배열에서 큐의 첫번째 원소의 idx-1
  • rear : 저장된 마지막 원소의 인덱스
• 상태 표현
  • 초기 상태 : front=rear=-1
  • 공백 상태 : front=rear
  • 포화 상태 : rear=n-1(n:배열의 크기, n-1: 배열의 마지막 인덱스)

초기 공백 큐 생성

• 크기 n인 1차원 배열 생성
• front와 rear를 -1로 초기화

배열을 이용한 큐 구현

package test1;

//선형 큐 구현
public class test1 {
	public static int n=5;
	public static int[] arr=new int[5];//n=5;
	public static int front=-1, rear=-1;
	
	public static void main(String[] args) {
		//Queue : FIFO 순서
		enQueue(1);
		enQueue(2);
		enQueue(3);
		enQueue(4);
		enQueue(5);
		print();
//		System.out.println(peek());
//		System.out.println(peek());
//		System.out.println(peek());
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
		print();
		System.out.println(deQueue());
		print();
		
		enQueue(6);
		System.out.println(size());
	}
	
	//enQueue(item) : 삽입
	public static void enQueue(int item) {
		if (isFull()) {//포화 상태라면
			System.out.println("큐가 꽉 참");
		}else {//rear!=n-1->포화상태X		
			arr[++rear]=item;
		}
	}
	
	//deQueue : 삭제
	public static int deQueue() {
		if (isEmpty()) {//큐가 비어있다면
			System.out.println("큐가 비어서 deQueue 불가능");
			return -1;
		}else {
			//삭제전
			front++;//큐에서 원소가 삭제됨
			return arr[front];//front:가장 마지막으로 삭제된 원소의
			//index(삭제 전에는 첫번째 원소)
			//front+1:새로운 첫번째 원소가 위치
		}
	}
	
	//peek : 가장 첫번째 원소 확인(삭제x, 반환)
	public static int peek() {
		if (isEmpty()) {
			System.out.println("큐가 비어서 peek 불가능");
			return -2;
		}else {
			return arr[front+1];//삭제하지 않고, 현재 첫번째 원소를 반환
			//front+1 : 현재 첫번째 원소의 idx
		}
	}
	
	//print : 현재 큐의 원소들 출력
	public static void print() {
		if (isEmpty()) {
			System.out.println("큐가 비어있어서 출력 불가능");
		}else {		
			for (int i = front+1; i <= rear; i++) {
				System.out.printf("[%d]:%d ", i, arr[i]);
			}
			System.out.println();
		}
	}
	
	//isEmpty : 큐가 비어있는지
	public static boolean isEmpty() {
		return rear==front;
	}
	
	//isFull : 큐가 차있는지(포화상태, 원소 추가 가능 여부)
	public static boolean isFull() {
		return rear==n-1;
	}
	
	//size : 현재 큐의 원소의 개수 
	public static int size() {
		return rear-front;
	}
}
//
[0]:1 [1]:2 [2]:3 [3]:4 [4]:5 
1
2
3
4
[4]:5 
5
큐가 비어있어서 출력 불가능
큐가 꽉 참
0

잘못된 포화 상태 인식을 해결하는 방법

//deQueue : 삭제
	public static int deQueue() {
		if (isEmpty()) {//큐가 비어있다면
			System.out.println("큐가 비어서 deQueue 불가능");
			return -1;
		}else {
		//front를 늘리는 것이 아니라 rear를 앞으로 당긴다.
			int temp=arr[front+1];//임시 변수에다가 현재 가장 앞에 있는 원소 저장
			//모든 원소를 한칸 앞으로 당기면서 덮어쓰기 한다.
			for (int i = 0; i < rear; i++) {
				arr[i]=arr[i+1];
			}
			rear--;//삭제 완료
			
			//삭제 원소를 반환
			return temp;
		}
	}
    public static void main(String[] args) {
		//Queue : FIFO 순서
		enQueue(1);
		enQueue(2);
		enQueue(3);
		enQueue(4);
		enQueue(5);
		print();
//		System.out.println(peek());
//		System.out.println(peek());
//		System.out.println(peek());
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
		print();
		System.out.println(deQueue());
		print();
		
		enQueue(6);
		print();
		System.out.println(size());
	}
    //
    [0]:1 [1]:2 [2]:3 [3]:4 [4]:5 
1
2
3
4
[0]:5 
5
큐가 비어있어서 출력 불가능
[0]:6 
1

스택과 큐의 비교

	Stack	Queue
추상 자료구조	o	o
선형	o 한쪽 끝에서만 삽입&삭제 동시에	o 한쪽 끝에서만 삽입 / 한쪽 끝에서만 삭제
연산	push : top++ pop : top--	enQueue : rear++-> O(1) deQueue : front++->O(1) / rear--->O(n)
java	stack 클래스	queue 인터페이스 linkedlist 클래스로 구현

 

package test2;

import java.util.LinkedList;
import java.util.Queue;

public class test1 {
	public static void main(String[] args) {
		//Queue는 인터페이스
		//LinkedList를 구현체로 사용
		Queue<Integer> q=new LinkedList<>();
		
		//enQueue -> offer(), add()
		//deQueue -> poll(), remove()
		//peek -> peek(), element()
		
		q.offer(1);
		q.add(2);
		q.offer(3);
		
		System.out.println(q.peek());
		System.out.println(q.poll());
		System.out.println(q.element());
		System.out.println(q.remove());
		System.out.println(q.poll());
		
		//add, remove, element 예외를 발생시킴
		//offer, poll, peek은 값만 리턴
		
		//add
		//새로운 원소 추가에 실패->IllegalStateException
		//offer
		//새로운 원소 추가에 실패->false
	
		//remove
		//큐에 원소가 없을 때->NoSuchElementException
		//poll
		//원소가 없다면 null 반환
	
		//element
		// 큐에 원소가 없으면 -> NoSuchElementException
		//peek
		//큐에 원소가 없으면 null 반환
		
	}
}
//
1
1
2
2
3