구현) 큐, 스택

자료구조 구현

1. 자료구조 특징 정리

 

2. 자료구조 특징에 사용될 변수를 정의한다.

 

3. 자료구조 특징에 따라 구현한다. 

구현 시, 변수를 어떻게 활용할지 고려

 

4. 자료구조 '최대 입력', '비었을때 제거'와 같이 경계영역? 예외 처리 해준다. 

ex) 배열 크기, 포인터 역할의 변수 ( 경계 영역에서 어디를 가리켜야 하는지 )

 

 

 

 

 

스택 

1. Last In First Out

 

 

2. top 이용

마지막 원소의 인덱스

 

 

3. 구현 시 주의할 점

 

pop()

스택이 빈 경우

 

push()

스택이 다 찬 경우 

 

 

 

배열을 이용한 스택 구현

    static class myStack{
        int[] stack = new int[4];
        
        /*
         *  마지막 원소의 인덱스 
         *  원소가 없는 경우 -1 
         */
        int top = -1;
        
        public void push(int data) {
            top++;
            
            if(top == stack.length) {
                System.out.println("full");
                top--;
                return;
            }
            
            stack[top] = data;
        }
        
        public int pop() {
            // 큐가 빈 경우 
            if(top == -1) {
                System.out.println("empty");
                return -1;
            }
            
            return stack[top--];
        }
    }
 

 

 

 

 

큐 

1 First In First Out

 

 

2 first, last 이용 

first : 첫 번째 원소 인덱스

last : 마지막 원소 다음 인덱스

 

 

3 구현 시 주의할 점

 

add

마지막에 원소 추가

 

큐가 빈 경우 ( first 추가 처리 필요 ) 

큐가 다 찬 경우 

 

 

poll( 또는 pop)

: 첫 번째 원소 제거 

 

큐가 빈 경우 ( first, last로 비었는지를 확인 )

큐에 원소가 한 개 남은 경우 

 

 

 

 

1. 배열을 이용한 큐 구현

( 실제 구현 시, 초기값 입력 받아 배열 크기 설정필요 ) 

 

static class myQueue{
    int[] q = new int[4];
    
    /*
     *  첫 원소를 가리킨다.
     *  처음에 언소가 없으므로 -1  
     */
    int first = -1;
    
    // 마지막 원소 다음을 가리킨다. 
    int last = 0;
    
    // 마지막에 추가 
    public void add(int data) {
        if(last == q.length) {
            System.out.println("full");
            return;
        }
        
        q[last++] = data;
        
        if(first == -1) {
            first++;
        }
    }
    
    // 먼저 들어온 원소 삭제 
    public int pop() {
        /*
         *  크기가 0일때 pop 불가 
         *  ( 처음에 first = -1 때만 빈거라고 착각했다. ) 
         */
        if(last - first == 1) {
            System.out.println("empty");
            return -1;
        }
        
        return q[first++];
    }
}

 

 

 

2. 링크드 리스트(?) 이용한 큐

노드가 next 노드를 가리키고 있다. 

 

마찬가지로 first, last 노드를 사용한다. 

 

poll에서 마지막 한 개 남았을때 주의

last도 null 처리

 

class myQueue{
    class node{
        private int data;
        private node next;
        public node(int data) {
            this.data = data;
        }
    }
    
    node first;
    node last;
    
    // 추가 후 last로 가리키기 
    public void add(int data) {
        node addNode = new node(data);
        if(last != null) {
            last.next = addNode;
        }
        last = addNode;
        
        if(first == null) {
            first = addNode;
        }
    }
    
    // 첫 번째 데이터 반납, 없다면 -1 리턴 
    public int pop() {
        if(first == null) {
            return -1;
        }
        
        node removeNode = first;
        first = removeNode.next;
        
        if(first == null) {
            last = null;  
        }
        
        return removeNode.data;
    }
}