[DS] Stack/Queue

Stack이란?

: 제한적으로 접근할 수 있는 나열구조로 목록의 한쪽 끝에서만 접근이 가능하다. 한쪽 끝으로 밀어넣는 것을 Push(), 그리고 한쪽 끝에 있는 원소를 빼는 것을 Pop()이라고 하며 LIFO (Last-In-First-Out) 구조를 가진다. 일반적으로 블록을 쌓는 것을 생각하면 간단하다. 기본 두 연산자 외에 Peek()이라는 함수를 통해 가장 끝에 있는 원소를 제거가 아닌 확인만 하는 함수도 있다. 

<출처: Medium>

스택은 활용도가 특히 높은 자료구조 중 하나인데 컴퓨터 구동에 기반이 되는 메모리 관리에도 스택이 사용되며 각종 알고리즘에서도 많이 활용된다. 모두가 아는 Stack Overflow의 Stack도 이 스택이다.

예시: DFS

DFS란 Depth First Search의 약자로, 그래프에서 특정 원소를 찾는 알고리즘이다. 이름에서도 알 수 있듯이 그래프의 최하단으로 먼저 내려가는 식으로 원소를 찾는다. 다음과 같은 그래프가 주어졌다고 하자. 

DFS 알고리즘은 Stack에 최상단의 있는 원소에 연결되어 있는 원소가 visited된적 없으면 Stack에 해당 원소를 push()하고 visited로 상태를 바꾼다. 만약 최상단의 원소와 연결되어 있는 모든 원소가 visited면 Stack에서 pop()한다. 

위 그래프에서 A를 먼저 Stack에 넣고 시작하면 다음과 같은 과정을 따른다.

1. Push A

2. Push B

 

3. Pop B

4. Push S

5. Push C -> Push D

6. Pop D

7. Push E

8. Push H

9. Push G -> Push F

10. 차례대로 Pop 

다른 글에서 다루겠지만 DFS의 시간복잡도는 O(|V|+|E|)이다.

Queue란?

: 마찬가지로 제한적으로 접근할 수 있는 나열구조로 먼저 넣은 데이터가 먼저 나오는 FIFO (First-In-First-Out) 구조를 가진다. Queue는 한국어로 줄로 일반적으로 줄 서있는 모습을 상상하면 된다. 

Queue에서 아이템을 밀어 넣는 것은 Enqueue()라 하며 아이템을 빼는 것을 Dequeue()라고 한다. 

<출처: Programiz>

예시: BFS

: BFS는 Breadth First Search의 약자로 그래프에서 특정 원소를 찾는 알고리즘이다. 이름에서 알 수 있듯이 옆으로 먼저 뻗어나가는 식으로 찾는다. 

BFS 알고리즘은 다음과 같다.

Q = new Queue();
Q.enqueue(starting_node);
starting_node.visited = true;

while (Q is not empty){
	node = Q.dequeue();
    for (neighbor in neighbor(node)){
    	if (neighbor.visited == false){
        	neighbor.visited = true;
            Q.enqueu(neighbor);
        }
    }
}

마찬가지로 다음과 같은 그래프가 주어졌다고 하자.

BFS를 통해 모든 원소를 Traverse하면 다음과 같다. 

 

다른 글에서 다루겠지만 BFS의 시간복잡도는 O(|V|+|E|)이다.

Time Complexity

	Stack	Queue
Push()/Enqueue()	O(1)	O(1)
Pop()/Dequeue()	O(1)	O(1)
Peek()	O(1)	O(1)
IsEmpty()	O(1)	O(1)
Search()	O(n)	O(n)
Size	O(1)	O(1)
Contain()/Removal()	O(n)	O(n)