스택과 큐는 단순한 자료구조이지만 이를 응용한 다양한 알고리즘들이 있습니다. 실제 컴퓨팅의 세계에서도 스택과 큐는 매우 중요한 역할을 합니다. 예를 들어 CPU의 명령 코드들은 거의 대부분 스택에 값과 주소들을 저장했다가 빼는 것을 반복합니다. 스택(Stack)은 밑이 막혀있는 프링글스 통처럼 입구와 출구가 하나인 자료구조입니다. 프링글스를 먹는 만큼 계속 채워 넣는다면 제일 아래에 있는 과자는 먹을 일이 없겠지요. 큐(Queue)는 반면에 입구와 출구가 따로 있는 긴 줄입니다. 은행 창구에 서있는 줄을 생각하면 되겠습니다. 누군가 순서를 어기고 새치기를 하면 난리가 나는 그런 줄입니다.
이 장에서는 스택과 큐에 대해서 기본 개념을 알아보고 그것을 배열과 연결리스트로 구현해 봅니다. 그리고 각각의 장단점에 대해서도 파헤쳐 볼 겁니다. 이어서 스택을 이용하여 수식의 표기법을 변환하고 수식을 계산하는 방법에 대해서도 알아볼 겁니다. 이를 통해 계산기 프로그램을 만들 수 있습니다.
강의 파일
동영상 파일
6.0 스택과 큐 - 시작 : 스택과 큐는 실제 생활에서도 많이 볼 수 있는 자료구조입니다. 데이터를 효율적으로 저장하고 순서를 매기고 빼내는 스택과 큐를 공부해 봅시다.
6.1 스택의 개념 : 스택이 무엇인지 개념을 살펴보고 기본적인 동작에 대해 알아봅니다.
6.2 스택의 구현 : 스택을 구현하는 방법은 여러가지 있습니다. 앞에서 배운 배열과 연결리스트를 이용하여 스택을 구현해 봅니다.
6.3 큐의 개념 : 스택과는 반대 개념이라고 할 수 있는 큐의 개념을 알아보고, 기본 동작을 익힙니다.
6.4 큐의 구현 : 큐도 여러가지 방법으로 구현할 수 있습니다. 배열로 구현할 경우 원형큐로 구현하는 것이 편리합니다. 연결리스트로 구현하는 것도 직관적인 방법입니다.
6.5 스택의 활용 - 계산기 CALC : 스택을 실제로 활용하는 예로 계산기를 만들어 봅니다. 이를 위해 수식의 표기법에 대해 알아보고, 스택으로 어떻게 변환을 할 수 있는지 알아봅니다.
6.6 후위 표기 변환 : 계산기 만들기 과정으로 스택을 이용하여 중위 표기 수식을 후위 표기 수식으로 변환하는 법을 알아봅니다.
6.7 수식 계산 : 후위표기로 표현된 수식을 입력받아 실제로 수식을 계산하는 프로그램을 만들어 봅니다. 이 역시 스택을 이용합니다.
6.9 스택과 큐 - 결론 : 스택과 큐에 대해 살펴 보았습니다. 그리고 스택을 이용하여 계산기 프로그램을 만들어 보았습니다. 이외에도 스택과 큐는 여러가지 분야에서 많이 쓰이고 있습니다.
관련글 |
- C++로 배우는 알고리즘
- 5장 : 연결리스트
- 7장 : 트리
