03. 큐 구현하기

큐 특징

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

2. Fist In First Out (선입선출) 구조

3. 일상 생활에서 일렬로 줄 서 있는 모양

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

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

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

LV2.기능개발

import java.util.*;

public class Solution {
	
	
	public int[] solution(int[] progresses, int[] speeds) {
		Queue<Integer> q = new LinkedList<>();
		for(int i=0; i<progresses.length; i++) {
			q.add(i);
		}
		
		List<Integer> result = new ArrayList<>();
		int days = 0;
		int count = 0;
		while(!q.isEmpty()) {
			int index= q.poll();
			int expiration = (int) Math.ceil(
					(double)(100-progresses[index]) / speeds[index]);
			if(expiration > days) {
				
				if(days!=0) {
					result.add(count);
					count = 0;
				}
				days = expiration;
				
			}
			count++;
		}
		
		result.add(count);
		return result.stream().mapToInt(Integer::intValue).toArray();
		

		 
	}
}

LV2.다리를 지나는 터널

import java.util.*;

public class Solution {
	
	public int solution(int bridgeLength, int weight, int[] truckWeights) {
		int bridgeWeight = 0;
		Queue<Integer> bridge = new LinkedList<>();
		
		for(int i=0; i <bridgeLength; i++) {
			
			bridge.add(0);
		}
		
		int time = 0;
		int truckIndex = 0;
		while(truckIndex < truckWeights.length) {
			bridgeWeight -= bridge.poll();
			
			int truckWeight = truckWeights[truckIndex];
			if(bridgeWeight + truckWeight <= weight) {
				bridge.add(truckWeight);
				bridgeWeight += truckWeight;
				truckIndex++;
			}else {
				bridge.add(0);
			}
			
			time++;
			
			
		}
		
		while(bridgeWeight>0) {
			
			bridgeWeight -= bridge.poll();
			time++;
		}
		
		return time;
	}

}