자료구조_선형구조 ④ 큐

 

 

[1] 큐  

---

(1) 큐의 개념

먼저 들어간 자료는 가장 먼저 나가고  , 마지막에 들어간 자료는 제일 마지막에 나온다 

FIFO 구조  선입선출

일괄처리, 스풀 운영에 활용한다 

모든 스케쥴링, 버퍼, 트리의 level order에 사용한다 

배열, 연결리스트로 구현할수 있으나 오버플로가 발생한다 ->무빙큐 , 원형큐, 연결리스트 대처 

맨 앞(front) 에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가 함

순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용 되는 자료구조

콜센터에 들어온 문의 전화, 메세지 큐 등에 활용됨

 

 

 

 

 

 

 

[2] 큐의 종류 

---

(1) 선형큐

※ front : 첫 요소 앞의 인덱스 자리 명칭 / real : 마지막 요소의 인덱스 자리 명칭 

 

 

rear (뒤) : 삽입 push   

→

4

3

2

1

→

front (앞) : 삭제 pop 

 

 

 

1이 나가기 전에는 인덱스(0) 자리에 데이터 1이 있었지만 

1을 삭제할경우 한칸씩 이동하여 1인덱스(0)자리에 데이터가 2로 바뀐다

이동하지 않으면 공간만 차지하고 있어 비효율적이기 때문에 무조건 배열의 길이 만큼 이동연산을 수행해야한다 

 

전단부 : 삽입 push   

→

4

3

2

→

1

후단부 : 삭제 pop 

 

 

큐는 링크 드리스트 구조이며 , 배열 대신에 현재값과 다음값을 가지는 구조체가 이어져 있는 구조이다 

자기 자신의 값인 1을 가지고 있는 동시에 다음 값은 2번라는 데이터와 연결되어있어요 라고 인식한다 

 

 

(2) 원형 큐 

 

배열을 원형으로 사용한다

시작과 끝을 인덱스로 지정하기 때문에 초기화(empty) 상태에서는 rear 과 front 는 같은 위치에 있다. 길이는 0이다 

초기화 상태에서는 front는 그대로 두고 real의 위치를 조정해야한다 (이유 : 처음과 끝이 같다는 모순이 생기니까)

데이터를 추가하면 마지막에 추가한 요소가 real 자리에 위치하게 된다  

 

 

 

데이터가 full 가득 찼어도 front 와 real의 자리는 같을 수 없다 

 

 

(3) 덱 = 데크 = 디큐 

스택과 큐의 장점을 결합함

삽입과 삭제가 리스트 양쪽 끝에서 임의로 수행한다 

 

 

 

[3] 큐 사용하기 

---

 

큐 선언하기

큐는 인터페이스라 객체 생성이 불가능하여 LinkedList 를 사용한다

Queue<Integer> Queue = new LinkedList<>();

 

큐 값 추가하기 . offer(data)

큐 맨 앞에 넣은 값 내보내기   .poll() , remove()

큐 맨앞에 있는 값 반환하기   .peek()

큐 크기 반환하기   .size()

(큐의 size == real이 가리키는 위치 -  front가 가리키는 위치)

큐 비어있는지 확인하기   .isEmpty()

 

 

 

 

큐 시간복잡도

---

시간 복잡도 Big O 표기법 이란 

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다 

 

Bio O 표기법	내용	시간복잡도 빠른순
O(1)	입력자료의 수에 관계없이 일정한 실행시간을 갖음	1
O(logn)	입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가	2
O(n)	입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 - 입력자료마다 일정 시간 할당	3
O(nlogn)	큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우	4
O(n^2)	이중 루프내에서 입력 자료를 처리할 때	5
O(n^3)	삼중 루프 내에서 입력자료 처리할 때	6
O(2^n)		7
O(n!)		8

 

맨 앞의 값이 지워져도 데이터 참조만 바꾸면 되기 때문에 O(1) 연산 수행으로 빠른 처리가 가능하다

단점은 인덱싱의 정보가 없어 인덱스 만큼 참조를 수행하여 값을 가져온다 

 

큐의 시간복잡도	삽입	Insertion O(1)
	삭제	Deletion O(1)
	검색	Search O(N)

 

 

 

 

 

큐 활용

---

우선순위 예약

프로세스 관리

너비우선 탐색 알고리즘 (BFS) : 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 

고객센터 콜대기 

실시간 interupt 처리

Event-driven Architecture

프린터-컴퓨터 사이의 인쇄 작업 큐 (버퍼링)

실시간 비디오 스트리밍 버퍼링

시뮬레이션 대기열 ( 은행 대기열)

통신 데이터 패킷 모델링에 이용

이메일 수신

푸시 알림기능

쇼핑몰에서 선착순으로 주문 처리하는 방식 

 

 

 

[7] 큐 구현하기 ( LinkedList 활용) 

 

import linkedlist.MyListNode;
import linkedlist.MyLinkedList;

interface IQueue{
	public void enQueue(String data);
	public String deQueue();
	public void printAll();
}

public class MyListQueue extends MyLinkedList implements IQueue{

	MyListNode front;
	MyListNode rear;
		
	
	public MyListQueue()
	{
		front = null;
		rear = null;
	}
	
	public void enQueue(String data)
	{
		MyListNode newNode;
		if(isEmpty())  //처음 항목
		{
			newNode = addElement(data);
			front = newNode;
			rear = newNode;
		}
		else
		{
			newNode = addElement(data);
			rear = newNode;
		}
		System.out.println(newNode.getData() + " added");
	}
	
	public String deQueue()
	{
		if(isEmpty()){
			System.out.println("Queue is Empty");
			return null;
		}
		String data = front.getData();
		front = front.next;
		if( front == null ){  // 마지막 항목
			rear = null;
		}
		return data;
	}
	
	public void printAll()
	{
		if(isEmpty()){
			System.out.println("Queue is Empty");
			return;
		}
		MyListNode temp = front;
		while(temp!= null){
			System.out.print(temp.getData() + ",");
			temp = temp.next;
		}
		System.out.println();
	}
}

 

public class MyListQueueTest {

	public static void main(String[] args) {

		MyListQueue listQueue = new MyListQueue();
		listQueue.enQueue("A");
		listQueue.enQueue("B");
		listQueue.enQueue("C");
		listQueue.enQueue("D");
		listQueue.enQueue("E");
		
		System.out.println(listQueue.deQueue());
		listQueue.printAll();
	}
}