[Seoul National Univ: Data Science] Lecture 5. Stacks & Queues

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

https://youtu.be/8dD4ANue7NY?si=1eOVMOqqAywiAfKf

 

1. Stacks

 

동작 구조

 

• 선형 자료구조, 한쪽 끝(top) 에서만 넣고 빼는 구조이다.
• LIFO (Last-In, First-Out) : 나중에 들어간 데이터가 먼저 나온다.

기본 연산 

 

• push(x) : 맨 위(top)에 원소 x를 넣는다.
• pop() : 맨 위 원소를 꺼내서 제거한다. 
• top() : 맨 위 원소를 “보기만” 한다. (peek)
• size() : 스택에 들어 있는 원소 개수
• empty() : 비었는지 여부 

 

Array Based Stack

• push(x) : O(1)
• pop() : O(1)
• top() : O(1)
• size() : O(1)
• empty() : O(1)

Linked Stack

• push(x) : O(1)
• pop() : O(1)
• top() : O(1)
• size() : O(1)
• empty() : O(1)

 

2. Applications of Stacks

 

1. 그래프 경로 찾기 (DFS, Depth-First Search)

 

그래프에서 스택을 이용한 탐색 과정이다.

 

(1) 시작 정점 P를 스택에 push()

(2) 스택의 top()에 대해, 방문 안한 이웃 정점이 있으면 그 정점을 push()하고, 이웃이 없으면 pop()한다.

(3) 도착점을 만나면 True를 반환하고, 스택이 끝날 때까지 만나지 못하면 False를 반환한다.

 

2. 괄호가 잘 형성 (well-formed) 되었는지 검사

 

 여러 종류의 괄호가 있는 경우에 수식이 잘 형성 되었는지 스택을 사용해 검사하는 알고리즘이다.

 

(1) 여는 괄호 "(", "{", "["를 만나면 스택에 push()

(2) 닫힌 괄호 ")", "}", "]"를 만났을 때 스택이 비어 있다면 Fasle

(3) 아니라면 top()으로 반환된 괄호와 매칭 후 정확한 짝인지 확인

(4) 실행이 종료될 때 스택이 비어 있다면 True

 

3. Queues

 

동작 구조

 

• 선형 자료구조, 앞(front) 에서만 꺼내고 뒤(rear) 에서만 넣는 구조이다.
• FIFO (First-In, First-Out) : 먼저 들어간 데이터가 먼저 나온다.

 

기본 연산 

 

• enqueue(x) : 큐의 뒤(rear) 에 원소 x 삽입
• dequeue() : 큐의 앞(front) 에 있는 원소를 꺼내서 제거 
• front() : 맨 앞 원소를 보기만 한다 
• size() : 큐에 들어 있는 원소 개수
• empty() : 비었는지 여부

Array Based Queue

• enqueue(x) : O(1)
• dequeue() : O(1)  (단, 원형 Queue인 경우가 아닌 경우에는 O(N)이 된다.)
• front() : O(1)
• size() : O(1)
• empty() : O(1)

Linked Queue

• enqueue(x) : O(1)
• dequeue() : O(1) 
• front() : O(1)
• size() : O(1)
• empty() : O(1)

 

4. Applications of Queues

 

1. 동물 보호소 문제

 

 개와 고양이만 존재하고, 먼저 들어온 순으로 나가야 한다. 이때 고양이 혹은 강아지만 데려가는 경우에는 그 종류 중 가장 오래된 한 마리를 가져갈 수 있고, 어느 종류도 선택하지 않은 경우에는 가장 오래된 한 마리를 데려가야 한다.

 

(1) 고양이 Queue / 강아지 Queue를 생성

(2) 각 동물에 도착 순서를 나타내는 timeStamp를 붙인다.

(3) 각 종류에 맞는 Queue에 enqueue() 진행

(4) 고양이 / 강아지 중 골라서 데려가는 경우에는 해당 Queue에서 deque() 진행

(5) 종류 상관 없이 제일 오래된 동물을 데려가는 경우에는 두 Queue의 front()의 time Stamp를 비교 후 더 오래된 쪽을 dequeue()

 

 

2. 그래프 경로 찾기 (BFS, Breadth-Firsth Search)

 

그래프에서 큐를 이용한 탐색 과정이다.

 

(1) 시작 정점 P를 큐에 push()

(2) 현재 정점을 dequeue()로 꺼낸다.

(3) 만약 현재 정점에서 아직 방문 안한 이웃 정점이 있으면 그 정점을 큐에 enqeue()하고, 목적지를 만나면 True를 반환한다.

(4) 큐가 끝날 때까지 만나지 못하면 False를 반환한다.