공부방

LinkedList / 원형Queue 본문

알고리즘/Queue

LinkedList / 원형Queue

코딩 화이팅 2023. 2. 23. 12:56

원형 큐

  • 초기 공백 상태
    front=rear=0
  • Index의 순환
    • front와 rear의 위치가 배열의 마지막 인덱스인 n-1을 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야함
    • 이를 위해 나머지 연산자 mod를 사용
  • front 변수
    공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠.
  선형 큐 원형 큐
front / rear 가장 첫번째 원소 한 칸 앞 idx / 가장 마지막 원소
초기 값 front->-1 / rear->-1 front->0 / rear->0
가장 첫번째 삽입 원소  idx 0 1
enQueue rear++
arr[rear]->item		 rear->(rear+1)%arr.length
arr[rear]->item
deQueue front++
return arr[front]		 front->(front+1)%n
return arr[front]

원형 큐의 연산 과정

package test1;

//원형 큐
public class test1 {
	public static int n=5;
	public static int arr[]=new int[n];
	public static int front=0, rear=0;
	
	public static void main(String[] args) {
		enQueue(1);
		enQueue(2);
		enQueue(3);
		enQueue(4);
		enQueue(5);//원형큐는 크기가 5인 배열이지만 front자리가 비기 때문에
		//5번째 인덱스에는 합류가 불가능
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
		//선형큐에서는 불가능하지만 원형큐에서는 가능
		enQueue(6);
		enQueue(7);
		enQueue(8);
		System.out.println(deQueue());
		System.out.println(deQueue());
		System.out.println(deQueue());
	}
	
	//큐가 비어 있는지
	public static boolean isEmpty() {
		return front==rear;//선형 큐와 같다.
	}
	
	//큐가 다 찼는지
	public static boolean isFull() {
		return (rear+1)%n==front;
	}
	//선형큐에서는 rear에 ++하고 리턴하지만 원형큐에서는 나머지 연산을 통해
	//만약 크기가 4인 배열이라면 0->1 1->2 2->3 3->4 4->0로 순환할 수 있게
	//나머지 연산을 추가해줘 크기를 나눈 나머지값을 front값과 비교.
	
	//enQueue
	public static void enQueue(int item) {
		if (isFull()) {
			System.out.println("큐가 가득 차서 더이상 원소 못 넣음");
		}else {
			rear=(rear+1)%n;
			arr[rear]=item;
		}
	}
	//마찬가지로 n만큼 나눈 곳을 rear로 선언하고 그곳을 enQueue
	
	//deQueue
	public static int deQueue() {
		if (isEmpty()) {
			System.out.println("큐가 비었음");
			 return -1;
		}else {
			front=(front+1)%n;
			return arr[front];
		}
	}
}
	//뺄 때도 n으로 나눈곳을 리턴
//
큐가 가득 차서 더이상 원소 못 넣음
1
2
3
4
큐가 비었음
-1
6
7
8

우선순위 큐의 특성

  • 우선순위를 가진 항목들을 저장하는 큐
  • FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.

PriorityQueue 사용 방법

package test2;

import java.util.Collections;
import java.util.PriorityQueue;

//우선 순위 큐
public class test1 {
	public static void main(String[] args) {
		//기본값: 숫자가 작은게 우선순위가 높다.(오름차순)
		PriorityQueue<Integer> pq=new PriorityQueue<>();
		//1. 생성자에다가 Comparator를 만들어 넣던지,
		//2. person이 Comparable을 구현하도록 한다.
		
		pq.offer(100);
		pq.offer(2);
		pq.offer(31);
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
        
        //우선순위를 뒤집으려면 생성자에다가 Comparator
		pq=new PriorityQueue<>(Collections.reverseOrder());
		
		pq.offer(100);
		pq.offer(2);
		pq.offer(31);
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}
}
//
2
31
100
100
31
2

새로운 클래스에 객체 생성 후 Comparable을 implements하여 구현하는 방법

package test3;
//Comparable을 implements할 클래스 생성 후 객체 생성하고
//Override 부분에 비교를 해준다.
public class person implements Comparable<person>{
	public String name;
	public int age;
	
	public person(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
	
	@Override
	public String toString() {
		return "person [name=" + name + ", age=" + age + "]";
	}

	@Override
	public int compareTo(person o) {
		//나이 순
		return this.age-o.age;
        //이름 순
		return this.name.compareTo(o.name);
	}
	
	
}
====================================================================
package test3;

import java.util.PriorityQueue;

public class test1 {
	public static void main(String[] args) {
		PriorityQueue<person> pq=new PriorityQueue<>();
		
		pq.offer(new person("강현", 26));
		pq.offer(new person("강현일", 27));
		pq.offer(new person("강현이", 28));
		pq.offer(new person("강현삼", 29));
		pq.offer(new person("강현사", 30));
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());		
	}
}
//
(나이순)
person [name=강현, age=26]
person [name=강현일, age=27]
person [name=강현이, age=28]
person [name=강현삼, age=29]
person [name=강현사, age=30]


(이름순)
person [name=강현, age=26]
person [name=강현사, age=30]
person [name=강현삼, age=29]
person [name=강현이, age=28]
person [name=강현일, age=27]

새로운 클래스에 생성자에다가 Comparator를 implements하여 구현하는 방법

package test4;

public class person{
	public String name;
	public int age;
	
	public person(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
	
	@Override
	public String toString() {
		return "person [name=" + name + ", age=" + age + "]";
	}
}
============================================================
package test4;

import java.util.Comparator;

public class ageComparator implements Comparator<person>{

	@Override
	public int compare(person o1, person o2) {
		return o1.age-o2.age;
	}
}
================================================================
package test4;

import java.util.Comparator;

public class nameComparator implements Comparator<person>{

	@Override
	public int compare(person o1, person o2) {		
		return o1.name.compareTo(o2.name);
	}
}
===================================================================
package test4;

import java.util.Comparator;
import java.util.PriorityQueue;

public class test1 {
	public static void main(String[] args) {
		PriorityQueue<person> pq=new PriorityQueue<>(new nameComparator());
		PriorityQueue<person> pq=new PriorityQueue<>(new ageComparator());
				
		pq.offer(new person("강현", 26));
		pq.offer(new person("강현일", 27));
		pq.offer(new person("강현이", 28));
		pq.offer(new person("강현삼", 29));
		pq.offer(new person("강현사", 30));
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}
}
//
person [name=강현, age=26]
person [name=강현사, age=30]
person [name=강현삼, age=29]
person [name=강현이, age=28]
person [name=강현일, age=27]

person [name=강현, age=26]
person [name=강현일, age=27]
person [name=강현이, age=28]
person [name=강현삼, age=29]
person [name=강현사, age=30]

무명 클래스로 한 클래스 안에서 객체를 생성 후 비교하는 방법

package test4;

import java.util.Comparator;
import java.util.PriorityQueue;

public class test1 {
	public static void main(String[] args) {
		
		//무명 클래스: 이름이 없는 클래스, 객체를 단 한번만 생성
		PriorityQueue<person> pq=new PriorityQueue<>(new Comparator<person>() {

			@Override
			public int compare(person o1, person o2) {
				return o1.age-o2.age;
			}
		});

		
		pq.offer(new person("강현", 26));
		pq.offer(new person("강현일", 27));
		pq.offer(new person("강현이", 28));
		pq.offer(new person("강현삼", 29));
		pq.offer(new person("강현사", 30));
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}
}
//
person [name=강현, age=26]
person [name=강현일, age=27]
person [name=강현이, age=28]
person [name=강현삼, age=29]
person [name=강현사, age=30]

람다 표현식 / 이름이 같을 때 나이순으로 비교하는 방법도 같이!

package test4;

import java.util.Comparator;
import java.util.PriorityQueue;

public class test1 {
	public static void main(String[] args) {

		//람다 표현식
		//함수를 간결하게 표현한 것
		//메서드의 길이가 짧은 경우
		//전통적으로 자바는 객체지향 언어
		//본래는 함수가 객체를 떠나서 독자적으로 존재할 수 없었다.
		//람다식은 함수형 프로그래밍을 자바에 도입한 것
		//매개변수로 람다함수를 전달 가능
		
		//문법 : (파라미터)->{본문}
		//파라미터가 단일 매개변수일 때 () 생략 가능
		//본문이 단일 문장일 때 {} 생략 가능
		
		PriorityQueue<person> pq=new PriorityQueue<>((o1, o2)->{
			if(o1.name.equals(o2.name)) {
				return o1.age-o2.age;
			}
			else {
				return o1.name.compareTo(o2.name); 
			}
		});
		
		pq.offer(new person("강현", 26));
		pq.offer(new person("강현", 27));
		pq.offer(new person("강현이", 28));
		pq.offer(new person("강현삼", 29));
		pq.offer(new person("강현사", 30));
		
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}
}
//
person [name=강현, age=26]
person [name=강현, age=27]
person [name=강현사, age=30]
person [name=강현삼, age=29]
person [name=강현이, age=28]

 

'알고리즘 > Queue' 카테고리의 다른 글

큐  (0) 2023.02.22
'알고리즘/Queue' Related Articles more