스택과 큐

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력순서는 후입선출(LIFO)이다.

스택의 기본

public class IntStack {
    private int max;
    private int ptr;
    private int[] stk;
    
    public class EmptyIntStackException extends RuntimeException{
        public EmptyIntStackException(){}
    }
    
    public class OverflowIntStackException extends RuntimeException{
        public OverflowIntStackException(){}
    }
    
    public IntStack(int capacity){
        ptr = 0;
        max = capacity;
        try{
            stk = new int[max];
        }catch(OutOfMemoryError e){
            max = 0;
        }
    }
    
    public int push(int x) throws OverflowIntStackException{
        if(ptr >= max)
            throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }
    
    public int pop() throws EmptyIntStackException {
        if(ptr <= 0)
            throw new EmptyIntStackException();
        return stk[--ptr];
    }
    
    public int peek() throws EmptyIntStackException{
        if(ptr<=0)
            throw new EmptyIntStackException();
        return stk[ptr-1];
    }
    
    public int indexOf(int x){
        for(int i=ptr-1; i>=0; i--)
            if(stk[i] == x)
                return i;
            return -1;
    }
    
    public void clear(){
        ptr = 0;
    }
    
    public int capacity(){
        return max;
    }
    
    public int size(){
        return ptr;
    }
    
    public boolean isEmpty(){
        return ptr<=0;
    }
    
    public boolean isFull(){
        return ptr>=max;
    }
    
    public void dump(){
        if(ptr <=0)
            System.out.println("스택이 비어 있습니다.");
        else{
            for(int i=0; i<ptr; i++)
                System.out.printf(stk[i] +" ");
            System.out.println();
        }
    }
}

 

기본적인 기능들을 가지고 있는 스택알고리즘 입니다.

 

 

 

 

 

 

 

큐도 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조입니다. 하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)인 점이 스택과는 다릅니다.

 

하지만 이러한 구조에는 큰 단점이 있습니다. 데이터를 넣는 enqueue()는 O(1)이지만 데이터를 빼내는 dequeue()는 O(n)입니다. 데이터를 하나 빼면 배열을 앞으로 한칸씩 당겨야 하기 때문입니다. 이를 보완하는 것이 링버퍼입니다. 

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[rear++] = x;
        num++;
        if(rear == max)
            rear = 0;
        return x;
    }

    public int deque() throws EmptyIntQueueException{
        if(num <=0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if(front == max)
            front =0;
        return x;
    }

    public int peek() throws EmptyIntQueueException{
        if(num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }

    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(){
        if(num <=0)
            System.out.println("큐가 비어있습니다.");
        else{
            for(int i=0; i<num; i++)
                System.out.printf(que[(i + front) % max]+" ");
            System.out.println();
        }
    }
}