[자료구조와 함께 배우는 알고리즘 입문] 4. 스택과 큐

스택, 큐는 이전에 간단하게 정리해둔 필기가 있어서 기본적인 건 그걸로 대체하고 추가로 내가 모르는 부분만 작성하기루

절대 귀찮은거 아님!!!!!!!

 

 

1. 스택

 

 

2. 큐

 

2-1. 배열로 큐 만들기

 

 

2-2. 링 버퍼로 큐 만들기

 

배열 요소를 앞쪽으로 옮기지 않는 큐를 구현하기 위해 사용하는 자료구조가 링버퍼이다.

약간 초등학생때 짜던 방학 계획표처럼 동그라미 안에서 첫 값과 마지막 값이 연결되어있는 구조라고 생각하면 된다.

맨 첫값과 끝 값을 논리적으로 구분하기 위해 사용하는 것이 프론트, 리어이다.

링 버퍼를 통한 큐의 인큐, 디큐는 시간복잡도 O(1)이 된다.

 

링버퍼를 사용해 큐를 구현하면 아래와 같이 구현할 수 있다.

public class IntQueue {
    private int[] queue;    //큐 배열
    private int capacity;   //큐 용량
    private int front;      //프론트 값
    private int rear;       //리어 값
    private int data;       //현재 데이터 개수

    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){}               //큐가 비어있을 경우의 예외
    }

    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException(){}               //큐가 넘쳤을 경우의 예외
    }

    public IntQueue(int maxlen){            //큐 생성자
        data = front = rear = 0;
        capacity = maxlen;
        try{
            queue = new int[capacity];
        }catch (OutOfMemoryError e){
            capacity = 0;
        }
    }

    public int enque(int x) throws OverflowIntQueueException{
        if(data>=capacity){
            throw new OverflowIntQueueException(); //큐가 가득 찬 경우의 예외처리
        }
        queue[rear++] = x;                         //rear값을 증가시키면서 인덱스 위치에 x를 enque시킴
        data++;
        if(rear==capacity){                        //capacity와 rear이 같아지면 rear를 배열의 첫 인덱스값으로 변경
            rear = 0;
        }
        return x;
    }
    
    public int deque() throws EmptyIntQueueException{
        if(data<=0){
            throw new EmptyIntQueueException();    //현재 데이터가 0이하일 경우 예외처리
        }
        int n = queue[front++];                    //front값을 임의 데이터에 저장시키고 +1증가시킴
        data--;                                    //현재 총 데이터 수는 -1 감소
        if(front==capacity){                       //front가 큐 용량이랑 같아지면 맨 첫 인덱스값인 0으로 만들어줌
            front =0;
        }
        return n;
    }

}