[코딩 인터뷰 완전 분석] 자료 구조 / 스택과 큐

스택 구현 

스택 자료구조는 말 그대로 데이터를 쌓아 올린다는 의미이다. 문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

 

스택은 LIFO(Last-In-First-Out)에 따라 자료를 배열한다. 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

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

스택은 배열과 달리, 상수 시간에 i번째 항목에 접근할 수 없다. 하지만 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다. 배열처럼 옆으로 밀어 줄 필요가 없다! 연결리스트로도 구현 가능함.

public class MyStack {
    private static class StackNode{
    	private T data;
        private StackNode next;
        public StackNode(T data){
        	this.data=data;
        }
    }
    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;
    }
}

스택이 유용한 경우는 재귀 알고리즘을 사용할 때다. 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어 주고, 재귀 함수를 빠져 나와 퇴각 검색을(backtrack) 할 때에는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다. 

연결리스트로 구현한 스택의 push와 pop

 

큐 구현 

큐는 FIFO(First-In-First-Out) 순서를 따르고, 큐에 추가되는 순서대로 제거된다. 

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

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

public class MyQueue{
	private static class QueueNode {
    	private T data;
        private QueueNode next;
        public QueueNode(T data){
        	this.data=data;
        }
    }
    
    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 (first==null){
        	first=last;
        }
    }
    
    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;
    }
}

큐에서 처음과 마지막 노드를 갱신할 때 실수가 자주 나오므로 확인 꼭 하기!

큐는 너비 우선 탐색(BFS)을 하거나 캐시를 구현하는 경우 종종 사용된다. 

Ex) 너비 우선 탐색의 경우 : 처리해야 할 노드의 리스트를 저장하는 용도로 사용한다. 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다. 이런식으로, 접근한 순서대로 처리할 수 있게 된다.