DS #3. 스택과 큐 (Stack and Queue)

이번에 살펴볼 부분은 스택과 큐이다.

 

출처 : https://javarevisited.blogspot.com

 

스택

스택(Stack)은 후입선출(Last In First Out: LIFO)의 선형 자료구조이다. 데이터를 쌓아 올린다는 의미에서 더미(stack)라는 이름이 붙었다. 입력은 push, 출력은 pop, 그리고 가장 위에 있는 데이터를 확인하는 방법은 peek라고 한다. 바닥이 막힌 상자라고 이해하면 쉬운데, 그렇기 때문에 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수 밖에 없다.

스택을 구현하는 방법을 살펴보자. 스택에서 필요한 함수는 위에서 언급한 push, pop, peek 그리고 하나를 더 추가한다면 스택이 비었는지 아닌지를 확인하는 isEmpty 함수 정도가 될 것 같다. 배열과 다르게 스택은 한 번에 i(인덱스)번째 데이터에 접근할 수는 없다. 다만 삽입/삭제는 O(1)에 가능하다. 아래는 Java로 구현한 스택 코드이다.

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;
    }
}

스택은 크기를 고정해서 사용하기 때문에, 이를 다 사용하면 넘치게 된다. 이 경우 다른 메모리 영역을 침범할 수 있게 되고, 이런 현상을 StackOverFlow라고 한다. 또한 스택이라는 자료구조는 프로세스를 구성하는 4대 요소 중 하나이며, 함수의 호출에 관여한다. 운영체제 부분에서 나중에 다시 다룰 예정이기는 하지만 간단하게만 짚고 넘어가면, 프로세스에는 4가지 메모리 영역이 있는데 이는 스택, 힙, 데이터, 코드 영역이다. 여기서 스택 메모리 영역은 프로그램이 자동으로 사용되는 임시 메모리 영역으로 지역변수, 매개변수, 리턴 값 등과 같이 잠시 사용 되었다가 사라지는 데이터를 저장하는 영역이다. 함수 호출 시 생성되고 함수가 끝나면 반환된다. 프로세스가 메모리에 로드될 때 스택 사이즈가 고정이 되고 런타임시 스택 사이즈를 바꿀 수는 없다. 명령 실행 시 자동으로 증가/감소하기 때문에 보통 메모리의 마지막 번지를 지정한다.

출처 : https://sfixer.tistory.com

스택은 재귀(recursive) 알고리즘을 사용할 때 특히 유용하다. 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어주고, 재귀 함수를 빠져 나와 백트래킹을 할 때는 스택에 넣어 주었던 임시 데이터를 빼 줘야 한다. 어떤 함수든 호출하는 순간 스택에 그 함수를 위한 영역(stack frame)이 할당되는데, 어떤 함수 foo()가 호출된 상태에서 foo()가 다시 다른 함수 bar()를 호출한다고 생각해보자. 우선 스택 내부 foo()에 해당되는 프레임에 데이터가 쌓여 있을 것이다. bar()가 호출되면 우선 bar가 받는 인수들이 푸시되고, 그 다음 bar의 리턴값을 받을 공간이 푸시가 된다. 그 위로 bar에 해당되는 새로운 스택 프레임이 할당되고, 그 프레임 내부에 bar의 내부 변수들이 푸시된다.

그 다음 bar에 해당하는 연산이 종료되고 bar의 스택 프레임 내부의 값들이 하나씩 빠져나오면서 끝으로 출력 데이터가 리턴값을 받기 위한 공간으로 들어오게 된다. 다시 말해 함수가 호출될 때 마다 스택에 값들이 쌓이고, 계산이 끝나면 다시 하나씩 빼면서 출력값이 가장 밑에 있던 리턴 공간으로 돌아오는 것이다. 재귀는 연산속도에서 불리한 점이 발생한다. 한 번 재귀 호출이 일어날 때 마다 계속 스택을 쌓아나가므로 최종 결과를 되돌려 받으려면 쌓인 스택을 전부 다시 빼내야 하기 때문이다. 따라서 신중하게 사용하는 것이 좋다.

 

---

 

큐

큐(Queue)는 선형 자료구조의 일종으로 선위선출(First In First Out: FIFO)의 원리로 이루어진다. Stack과 반대로 가장 먼저 들어간 데이터가 가장 먼저 나오게 된다. 표 등을 구매하기 위해 선 줄을 큐라고 부른다. 데이터가 큐로 들어오는 동작은 enqueue, 큐에서 데이터가 나가는 동작은 dequeue이다. Queue를 구현하는데 있어야 하는 연산은 리스트에 끝에 아이템을 추가하는 add(item), 리스트의 첫번째 항목을 제거하는 remove(), 큐의 가장 위에 있는 항목을 반환하는 peek(), 그리고 큐가 비어있는지를 확인하는 isEmpty()가 있다. 다음은 연결 리스트로 구현한 자바 기반 큐 코드이다. 

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;
       	}
	}
}

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

큐는 여러가지 변형이 존재하는데 원형 큐, 우선순위 큐, 데크(Deque) 등이 있다.

원형 큐

큐를 위해 배열을 지정해 놓고 큐를 쓰다 보면 배열의 앞부분이 비게 된다는 한계(OutOfBoundException)를 극복하기 위해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 큐를 채우기 시작하는 형태의 큐이다. 원형 큐에서는 포인터 증가 방식이 (rear+1)%arraySize 형식으로 변환되기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다. 만약 큐가 포화상태이면 (rear+1)%arraySize == front 이면 Enqueue가 실행될 수가 없다.

 

우선순위 큐

우선순위 큐는 원소들에 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것이다. 만약 우선순위가 낮은 원소가 들어간다면(enqueue) 빼낼 때에는(dequeue) 해당 원소보다 이후에 들어온 원소가 더 먼저 나갈 수도 있는 상황이 발생한다. 대표적으로 힙(Heap)이 있다. 힙은 이후에 트리 부분에서 살펴보도록 한다.

 

데크

데크(deque, doubly-ended queue)는 양쪽에서 모두 삽입/인출이 가능한 큐이다. 스택과 큐의 장점만을 가지고 만들어졌다. 입력이 한쪽에서만 가능하고 출력은 양쪽에서 가능한 경우는 Scroll, 출력이 한 쪽에서만 가능하고 입력이 양쪽에서 모두 가능한 경우는 Shelf라고 한다.

 

참고 자료

1. https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure
2. https://sfixer.tistory.com/entry/%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%98%81%EC%97%ADcode-data-stack-heap
3. https://mailmail.tistory.com/m/41
4. https://www.geeksforgeeks.org/stack-data-structure/
5. <코딩인터뷰 완전분석>, 게일 라크만 맥도웰 저
6. <C언어로 쉽게 풀어쓴 자료구조>, 천인국 외 저