Queue()-캐시 [JAVA]

큐란?

큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가집니다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조이다.

Enqueue : 가장 뒤에 데이터 추가
Dequeue : 가장 앞의 데이터 제거

큐 메서드

Queue<Integer> queue = new LinkedList<>();
queue.add(value);       // queue에 데이터 추가, 실패시 Exception
queue.offer(value);     // queue에 데이터 추가, 실패시 False

queue.remove();    		// 삭제 데이터 반환, 공백이면 Exception
queue.remove(value);    // queue에 데이터 제거, 존재하지 않으면 false
queue.poll();      		// 삭제 데이터 반환, 공백이면 null

queue.element();   		// queue의 맨 앞 데이터 반환, 공백이면 Exception
queue.peek();      		// queue의 맨 앞 데이터 반환, 공백이면 null

queue.clear();     		// queue 초기화
queue.size();      		// queue 사이즈 반환
queue.contains(value);  // queue에 해당 값 존재시 True
queue.isEmpty();   		// queue 공백 여부

캐시 교체 알고리즘, LRU(Least Recently Used)를 사용한 문제

Queue<String> queue = new LinkedList<>();
		//캐시사이즈가 0인경우
        if (cacheSize == 0) return cities.length*5; 
        for (int i = 0; i< cities.length; i++){
            String city = cities[i].toUpperCase();
            //큐에 해당 도시가 존재하는 경우
            if (queue.remove(city)){
            	//큐가 가득 찬 경우
                if (queue.size()==cacheSize){ 
                    queue.remove(city);
                    queue.add(city);
                }else {
                    queue.add(city);
                }
                hour += 1;
            }
            //큐에 해당 도시가 존재하지 않는 경우
            else{ 
                if (queue.size() == cacheSize){
                    if (queue.size() == 0){
                        queue.add(city);
                    }else{
                        queue.remove();
                        queue.add(city);
                    }
                }else {
                    queue.add(city);
                }
                hour += 5;
            }
        }
        return hour;
    }