자료구조) 1. Stack, Queue

목차.

1. Stack, Queue

2. Graph, Tree, Binary Search Tree(BST, 이진탐색트리)

3. Tree traversal (트리순회)

4. Breadth-First Search(BFS, 너비우선탐색), Depth-First Search(DFS, 깊이우선탐색)

 

1. Stack, Queue

 1) Stack

Stack(이하 스택)은 '쌓다', '쌓이다' 라는 뜻을 가지고 있다. 그렇기 때문에 자료구조의 한 종류로써 스택은 데이터를 계속 해서 쌓아 놓은 것을 말한다. 예를들어 동전을 원통안에 하나씩 쌓을 경우 맨 아래의 동전을 꺼내기 위해서는 위에 쌓인 동전들을 모두 꺼내어야한다. 이처럼 데이터가 스택에 쌓여있기 때문에 가장 먼저 삽입된 데이터1을 사용하기 위해서는 뒤에 들어온 데이터들을 모두 꺼내야한다. 이를 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO, Last In First Out)라고 한다.

출입구
	데이터1	데이터2	데이터3	데이터4	데이터5	데이터6

스택을 활용한 대표적인 예는 웹페이지의 뒤로가기와 앞으로가기 버튼이 있다. 두개의 스택을 만들어 현재페이지에서 다른페이지로 이동할 때마다 이전페이지 스택에 이동직전의 페이지들을 저장해두고 뒤로가기 버튼을 클릭시 현재페이지를 다음페이지 스택에 저장해둔다.

			(A 페이지 접속)
			'A'
	이전페이지스택		현재페이지		다음페이지스택

 

			(B 페이지 접속)
	'A'		'B'
	이전페이지스택		현재페이지		다음페이지스택

 

			(C 페이지 접속)
	'B'
	'A'		'C'
	이전페이지스택		현재페이지		다음페이지스택

 

			(뒤로가기버튼)
	'A'		'B'		'C'
	이전페이지스택		현재페이지		다음페이지스택

 

 2) Queue

Queue(이하 큐)는 '차례를 기다리는 사람이나 승용차의 열' 이라는 뜻을 가지고 있다. 이때 차례를 기다린다는 것은 첫번째인 사람이나 승용차에게 가장 먼저 차례가 돌아간다는 뜻이다. 스택과는 상반되는 자료구조인 것이다. 세차장 앞에서 차들이 줄을 서있다면 가장먼저 도착해서 줄을 서있는 차가 먼저 세차를 시작하고 가장 먼저 나간다. 이처럼 먼저들어온 데이터가 먼저 사용되는 것을 선입선출(FIFO, First In First Out)이라고 한다. 

 

출구                                                                                                                                                                                                                                                 입구
데이터1	데이터2	데이터3	데이터4	데이터5	데이터6	데이터7

 

큐의 대표적인 사용예시는 프린트이다. 문서를 프린트할 때 프린트되는 순서는 작성된 문서의 페이지 순서대로 된다. 1페이지가 먼저 출력이 되고 그 다음에 2페이지, 3페이지 순으로 마지막 페이지까지 출력이 된다. 

출력                                                                                                                                                                                                                                                 입력
1페이지	2페이지	3페이지			3페이지크기의 문서순서대로입력

 

출력                                                                                                                                                                                                                                                  입력
2페이지	3페이지				1페이지 출력완료

 

출력                                                                                                                                                                                                                                                  입력
3페이지					2페이지 출력완료

 

출력                                                                                                                                                                                                                                                  입력
					3페이지 출력완료/모든 출력완료

 

 나름대로 독자적인 자료를 만들기 위해 테이블을 사용했다. 시간이 날 때 자료를 제작할 수 있는 툴이 있는지 알아봐야겠다.