큐

위상 정렬 (Topological Sorting) 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 을 의미한다. 예시를 통해 확실하게 이해해보도록 하자. 그림과 같이 총 3개의 과목이 있다고 가정하자. 세 과목을 모두 듣기 위해서는 자료구조 → 알고리즘 → 고급알고리즘 (O) 순서로 과목을 들어야 한다. 만약 자료구조 → 고급 알고리즘 → 알고리즘 (X) 순서로 과목을 듣게 되면, 올바른 학습순서가 아니다. 진입차수와 진출차수 위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 진입..

이번시간에는 스택과 큐가 실제로 어떻게 활용되는지 예제르 통해서 알아보자. 스택의 활용 예 - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로 큐의 활용 예 - 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer) [스택의 활용 예] 수식계산의 경우, ((3+2)*8)/2 이러한 계산이 있으면, 이것은 스택을 활용해서 계산된다. 수식괄호 검사는, 수식에서 여는괄호와 닫는괄호의 갯수가 일치하는지 확인할 때 스택을 활용한다. 워드프로세서의 undo/redo (취소, 복구)에도 스택이 사용된다. 그리고 웹 브라우저의 다음으로가기 버튼과 이전으로가기 버튼에도 스택이 사용된다. 현재페이지가 D일 때, 뒤로가기 버튼을 누르면, 또하나의 스택을 만들어서 페이지D를 새로운 스택으로 ..

스택과 큐 (Stack & Queue) - 스택(Stack) : LIFO 구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다. 스택은, 밑이 막힌 상자처럼 되어있다. Last In First Out 구조이다. 먼저들어간게 제일 마지막에 나오고, 제일 마지막에 넣은게 제일 처음 나온다. 스택에서는 저장하는 것을 push, 추출하는 것을 pop라고 한다. 데이터 1, 2, 3, 4, 5가 있을 때, 이것의 순서를 반대로 뒤집고 싶다면, 스택에 넣었다가 빼면, 5, 4, 3, 2, 1로 나온다. - 큐(Queue) : FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다. 큐는 위아래가 뚫려있다. 데이터 흐름이 줄서기와 똑같다. First In First Out구조이다. 먼저 들어간게 제일 먼저나오고,..