3. 스택과 큐

▶ 스택 구현하기

이전에는 연결리스트를 배웠다면, 이번에는 스택이다. 연결리스트는 하나의 노드를 다음 노드에 연결시켜 그 자료들을 관리하는 것이었다면, 스택은 말 그대로 데이터를 쌓아 올린다는 의미이다. 문제의 종류에 따라 배열보다 스택을 활용하는 것이 더 좋을 수 있기 때문에 분별하는 능력이 필요로 하다. 스택은, 가장 최근에 추가한 데이터 항목이 가장 먼저 제거되는 형식이다. 스택에서 가장 필수가 되는 연산을 살펴보자.

pop() : 스택에서 가장 위에 있는 항목 제거
push(item) : item 하나를 스택의 가장 윗 부분에 추가
peek() : 스택의 가장 위에 있는 항목을 반환
isEmpty() : 스택이 비어 있을 때에 true를 반환

 

다음은 스택 예제코드이다. 스택은 같은 방향에서 아이템을 추가하고 삭제한다는 조건하에 연결리스트로 구현할 수도 있다.

public class MyStack {
	private static class StackNode {
    	/*
        	stack은 자신이 가지고 있는 data와
            다음의 스택노드를 가리키고 있는 next를 가지고 있다.
            1, 2, 3 순으로 데이터가 입력된다면
            3이 가지고 있는 data는 3이며, next는 2이다. 
        */
    	private T data;
        private StackNode next;
        
        // data가 들어오면 stackNode를 초기화 시킴
        public StackNode(T data) {
        	 this.data = data;
        }
    }
    
    // top은 가장 최상층에 있는 데이터를 의미한다.
    // 즉, 가장 나중에 들어온 데이터라는 것을 말한다.
    private StackNode top;
    
    public T pop() {
    	if(top == null) throw new EmptyStackException();
        T item = top.data;
        top = top.next;
        return item;
    }
    
    public void push(T item) {
    	StackNode t = new StackNode(item);
        t.next = top;
        top = t;
    }
    
    public T peek() {
    	if(top == null) throw new EmptyStackException();
        return top.data;
    }
    
    public boolean isEmpty() {
    	return top == null;
    }
}

 

스택은 재귀 알고리즘을 쓸 때 유용하다.

스택은 재귀 알고리즘을 사용할 때에 임시 데이터를 스택에 넣어 주고, 재귀 함수를 빠져 나와 퇴각 검색을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 주어야 한다. 이 관점에서 stack은 이러한 행위를 직관적으로 가능하게 해 준다.

 

▶ 큐 구현하기

큐는 앞에 들어간 데이터가 먼저 빠져나가는 자료 구조이다. 큐에는 다음과 같은 연산을 가지고 있다.

add(item) : item을 리스트의 끝부분에 추가한다.
remove() : 리스트의 첫 번째 항목을 제거한다.
peek() : 큐에서 가장 위에 있는 항목을 반환한다.
isEmpty() : 큐가 비어 있을 때에 true를 반환한다.

큐 또한 연결리스트로 구현할 수 있으며, 연결리스트의 반대 방향에서 항목을 추가하거나 제거하도록 구현한다면 근본적으로 큐와 같다고 할 수 있다.

public class MyQueue {
	private static class QueueNode {
    
    	// Queue는 자신이 가지고 있는 data와
        // 자신 보다 먼저 들어온 node를 가리키는 next가 존재한다.
    	private T data;
        private QueueNode next;
        public QueueNode(T data) {
        	this.data = data;
        }
    }
    
    
    /*
    	데이터가 가장 먼저 들어온 first node와
        데이터가 가장 늦게 들어온 last node가 존재한다.
    */
    private QueueNode first;
    private QueueNode last;
    
    public void add(T item) {
    	QueueNode t = new QueueNode(item);
        if(last != null) {
        	last.next = t;
        }
        last = t;
        if(fist == null) {
        	fist = lase;
        }
    }
    
    public T remove() {
    	if(first == null) throw new NoSuchElementException();
        T data = first.data;
        first = first.next;
        if(first == null) {
        	last = null;
        }
        return data;
    }
    
    public T peek() {
    	if(first == null) throw new NoSuchElementException();
        return first.data;
    }
    
    public boolean isEmpty() {
    	return first == null;
    }
}

큐는 너비 우선 탐색을 하거나 캐시를 구현하는 경우에 종종 사용된다.
처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용한다. 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다. 이렇게 함으로 노드를 접근한 순서대로 처리할 수 있게 된다.