배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현

큐는 데이터를 일시적으로 쌓아놓은 자료구조이다.

가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출인 점이 스택과 다름.

가장먼저 넣은 데티러르 가장 먼저 꺼내는 선입선출 구조로 되어있다.

큐의 예는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있다.

큐에 데이터를 넣는 작업을 인큐라 하고 데이터를 꺼내는 작업을 디큐라고 한다.

데이터를 꺼내는 쪽을 프런트(front)라 하고 데이터를 넣는 쪽을 리어(rear)라고 한다.

배열을 사용해 디큐를 하면서 모든 요소를 하나씩 앞쪽으로(shift)  옮기는 큐는 

데이터를 꺼낼때 마다 O(n) 복잡도 이므로 이런 처리를 하면 효율이 떨어짐

1. 배열을 사용해 디큐를 하면서 모든 요소를 하나씩 앞쪽으로(shift)  옮기는 큐 구현

package myTest1;
 
import java.util.Scanner;
 
public class IntAryQueue {
    
    private int max;        // 큐 용량        
    private int num;        // 현재 데이터 수
    private int[] que;        // 큐 본체
    
    // 실행 시 예외 : 큐이 비어있음
    public class EmptyIntAryQueueException extends RuntimeException{
        public EmptyIntAryQueueException(){
        }
    }
    
    // 실행 시 예외 : 큐이 가득 참
    public class OverflowIntAryQueueException extends RuntimeException{
        public OverflowIntAryQueueException(){
        }
    }
    
    // 생성자
    public IntAryQueue(int capacity){
        num = 0;
        max = capacity;
        try{
            que = new int[max];            // 큐 본체용 배열을 생성
        }catch(OutOfMemoryError e){    // 생성할 수 없음
            max = 0;
        }
    }
 
    // 큐에 데이터를 인큐하는 메서드
    public int inQueue(int x) throws OverflowIntAryQueueException{
        if(num >= max){    // 큐이 가득 참
            throw new OverflowIntAryQueueException();
        }
        return que[num++] = x;
    }
    
    // 큐의 맨 첫번째에 있는 데이터를 제거(디큐) 하고 그 값을 반환하는 메서드
    public int deQueue() throws EmptyIntAryQueueException{
        if(num <= 0){
            throw new EmptyIntAryQueueException();
        }
        int data = que[0];
        for(int i=0; i<num-1; i++){ // 0 < 2 // 0 1 2
            que[i] = que[i+1]; // que[0] = que[1] , que[1] = que[2],  que[2] = que[3]
        }
        --num;
        return data;
    }
    
    // 큐의 가장 먼저 빠질 데이터를 몰래 엿보는 메서드(peek 메서드 )
    public int peek() throws EmptyIntAryQueueException{
        if(num <= 0){
            throw new EmptyIntAryQueueException();
        }
        return que[0];
    }
    
    // 큐에서 x를 찾아 인덱스를 반환
    public int indexOf(int x){
        for(int i=num -1; i>=0; i--){
            if(que[i] == x){
                return i;
            }
        }
        return -1;
    }
    
    // 큐을 비움
    public void clear(){
        num = 0;
    }
    
    // 큐의 용량을 반환
    public int capacity(){
        return max;
    }
    
    // 큐에 쌓여있는 데이터 수를 반환
    public int size(){
        return num;
    }
    
    // 큐이 비어있는가?
    public boolean isEmpty(){
        return num <= 0;
    }
    
    // 큐이 가득찼는가?
    public boolean isFull(){
        return num >= max;
    }
    
    // 큐 안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
    public void dump(){
        if(num <= 0){
            System.out.println("큐이 비어있습니다.");
        }else{
            for(int i=0; i<num; i++){
                System.out.print(que[i] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntAryQueue queue = new IntAryQueue(64);    // 최대 64개를 푸시할 수 있는 큐
        
        while(true){
            System.out.println("현재 데이터 수 : " + queue.size() + " / " + queue.capacity()); 
            System.out.print("(1) 인큐 (2) 디큐 (3) 피크 (4) 덤프 (0) 종료 : ");
            int menu = scanner.nextInt();
            if(menu == 0) break;
            
            int x;
            switch(menu){
            
            case 1:
                System.out.print("데이터 : ");
                x = scanner.nextInt();
                try{
                    queue.inQueue(x);
                }catch(IntAryQueue.OverflowIntAryQueueException e){
                    System.out.println("큐가 가득찼습니다.");
                }
                break;
                
            case 2:
                try{
                    x = queue.deQueue();
                    System.out.println("디큐한 데이터는 " + x + "입니다.");
                }catch(IntAryQueue.EmptyIntAryQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 3:
                try{
                    x = queue.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                }catch(IntAryQueue.EmptyIntAryQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 4:
                queue.dump();
                break;
            }
        }
    }
}

결과

2. 링버퍼로 큐 만들기

package myTest1;
 
import java.util.Scanner;
 
public class IntQueue {
    
    private int max;        // 큐 용량        
    private int front;        // 첫번째 요소 커서
    private int rear;    // 마지막 요소 커서
    private int num;        // 현재 데이터 수
    private int[] que;    // 큐 본체
    
    // 실행 시 예외 : 큐이 비어있음
    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){
        }
    }
    
    // 실행 시 예외 : 큐이 가득 참
    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException(){
        }
    }
    
    // 생성자
    public IntQueue(int capacity){
        num = front = rear = 0;
        max = capacity;
        try{
            que = new int[max];            // 큐 본체용 배열을 생성
        }catch(OutOfMemoryError e){    // 생성할 수 없음
            max = 0;
        }
    }
 
    // 큐에 데이터를 인큐하는 메서드
    public int enque(int x) throws OverflowIntQueueException{
        if(num >= max){    // 큐이 가득 참
            throw new OverflowIntQueueException();
        }
        // que[0] 10 que[1] 9 que[2] 8
        // num = 3
        que[rear++] = x;
        num++;
        if(rear == max){
            rear = 0;
        }
        return x;
    }
    
    // 큐의 맨 첫번째에 있는 데이터를 제거(디큐) 하고 그 값을 반환하는 메서드
    public int deque() throws EmptyIntQueueException{
        if(num <= 0){
            throw new EmptyIntQueueException();    // 큐가 비어있음.
        }
        // que[0] 10 que[1] 9 que[2] 8
        // num = 3
        // int x = 10, num = 2 , front = 1
        int x = que[front++];
        num--;
        if(front == max){
            front = 0;
        }
        return x;
    }
    
    // 큐의 가장 먼저 빠질 데이터를 몰래 엿보는 메서드(peek 메서드 )
    public int peek() throws EmptyIntQueueException{
        if(num <= 0){
            throw new EmptyIntQueueException();
        }
        return que[front];
    }
    
    // 큐에서 x를 찾아 인덱스를 반환
    public int indexOf(int x){
        for(int i=0; i<num; i++){
            int idx = (i+front) % max;
            if(que[idx] == x){    // 검색 성공
                return idx;
            }
        }
        return -1;                    // 검색 실패
    }
    
    // 큐을 비움
    public void clear(){
        num = front = rear = 0;
    }
    
    // 큐의 용량을 반환
    public int capacity(){
        return max;
    }
    
    // 큐에 쌓여있는 데이터 수를 반환
    public int size(){
        return num;
    }
    
    // 큐이 비어있는가?
    public boolean isEmpty(){
        return num <= 0;
    }
    
    // 큐이 가득찼는가?
    public boolean isFull(){
        return num >= max;
    }
    
    // 큐 안의 모든 데이터를 프런트 -> 리어 순으로 출력
    public void dump(){
        // que[0] 10 que[1] 9 que[2] 8
        // num = 3
        // int x = 10, num = 2,    front = 1
        if(num <= 0){
            System.out.println("큐이 비어있습니다.");
        }else{
            // i=0 i<2 que[(0+1)%64 que[(1+1)
            // 2%64
            for(int i=0; i<num; i++){
                System.out.print(que[(i+front) % max] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntQueue queue = new IntQueue(64);    // 최대 64개를 푸시할 수 있는 큐
        
        while(true){
            System.out.println("현재 데이터 수 : " + queue.size() + " / " + queue.capacity()); 
            System.out.print("(1) 인큐 (2) 디큐 (3) 피크 (4) 덤프 (0) 종료 : ");
            int menu = scanner.nextInt();
            if(menu == 0) break;
            
            int x;
            switch(menu){
            
            case 1:
                System.out.print("데이터 : ");
                x = scanner.nextInt();
                try{
                    queue.enque(x);
                }catch(IntQueue.OverflowIntQueueException e){
                    System.out.println("큐가 가득찼습니다.");
                }
                break;
                
            case 2:
                try{
                    x = queue.deque();
                    System.out.println("디큐한 데이터는 " + x + "입니다.");
                }catch(IntQueue.OverflowIntQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 3:
                try{
                    x = queue.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                }catch(IntQueue.OverflowIntQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 4:
                queue.dump();
                break;
            }
        }
    }
}

결과

3. 링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.

예를 들면 요소의 개수가 n인 배열에 계속 데이터가 입력되면 

가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도이다.

배열의 길이는 10인데 정수입력이 12개가 들어온다면

정수 입력은 가장 최근에 입력한 10개의 데이터만 링 버퍼에 남아있다.

예전 데이터는 버리는 것이다.

 

package myTest1;
 
import java.util.Scanner;
 
public class LastElements {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int N = 10;
        int[] a = new int[N];            // 입력 받은 값을 저장
        int cnt = 0;                            // 입력 받은 개수
        int retry;                                // 다시 한 번?
        
        System.out.println("정수를 입력하세요.");
        
        do{
            System.out.printf("%d번째 정수: ", cnt+1);
            a[cnt++ % N] = scanner.nextInt();
            System.out.print("계속 할까요? (예. 1 / 아니오. 0) : ");
            retry = scanner.nextInt();
        }while(retry == 1);
        
        int i = cnt - N;
        if(i <0) i = 0;
        
        for(;i<cnt;i++){
            System.out.printf("%2d번째 정수=%d\n", i+1, a[i%N]);
        }
        
    }
}

결과

소스코드 첨부

myTest1.zip