방송대 자료구조 교재 요약 제3 장 - 스택

제3 장 스택)

 

개관)

스택은 '입출력 순서'를 자료들 간의 관계로 표현하는 자료구조다.

스택은 입력이 가장 늦게 된 자료가 가장 먼저 출력되는 관계를 표현한다.

그래서 왔던 길을 되돌아가야 하는 미로찾기나 깊이 우선 탐색에 많이 사용되고,

예전에 처리했던 값을 역순으로 되돌아가며 찾아내서 처리해야 하는 후위식의 계산에 많이 사용된다.

사칙연산에도 주로 사용한다.

내가 여기까지 정리하면서 확신이 드는 게 방송대 교재는 실물로, 꼭 사는 게 좋은 거 같다.

편입학 초기에는 책을 꼭 사야 하나, 실물 책을 사느냐 eBook을 사느냐 같은 고민을 많이 하는데

실물 책을 사야 편하게 형광펜 등으로 체크도 하고, 필기도 하면서 여러 번 볼 수 있다.

방송대 컴퓨터과학과 교재 중 기본 CS와 관련 있는 책은 다회독 해도 절대 무익하지 않기 때문에

여유 되면 꼭 실물 교재를 사시라.

1. 스택의 개념

프로그래머의 의도를 반영한 자료구조는 어떻게 만들까?

이때 정의하는 게 바로 추상 자료형(ADT)이다.

...

스택의 자료구조는 정형화되어있고 이러한 틀 속에서 일반적으로 사용되는 함수는 push()와 pop()이다.

！(중요)스택의 크기는 무한하지 않다.(중요)！

스택에는 크기 제한이 있고, 이것은 프로그램의 작성에서 일어나는 메모리의 한계와도 관계가 있다.

따라서 스택의 크기(스택에 넣을 수 있는 원소의 개수)를 제한하는 경향이 실제 프로그램에서 존재한다.

...

2. 스택의 추상 자료형

스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되거나 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있다.

따라서 교재에 나와 있는 ADT는 절대적이기 보다는 기본적인 내용을 다룬다.

일단은 ADT들이 객체에 대한 정의와 적용 가능한 연산으로 이루어진다는 것을 이해하면 된다.

...

3. 스택의 응용

시스템 스택이란 것이 있다.

변수에 대한 메모리를 할당하고 수집할 때 시스템 스택이 사용된다.

시스템 스택은 프로그램에서 사용되는 변수들의 생명주기를 관리하기도 한다.

('프로그램 언어론'에 자세한 내용이 나오니 수강하든지 구매 후 듣자!)

...

변수의 생명주기 == 메모리 공간에서 변수가 메모리 영역을 배정받고 사용하다가 이를 비울 때까지의 시간을 의미한다.

(C라서 '비운다'라고 말한 것 같다. 자바였으면 가비지 콜렉터가 알아서 했겠지.)

이런 내용을 운영하는 건 운영체제다.

스택은 시스템 스택 외에 서브루틴 호출 관리를 위해 사용되기도 한다.

(이 내용도 프로그래밍 언어론 수업 시간에 나온다.)

(서브루틴 == 프로그램 내에서 특정 작업을 수행하는 코드의 독립된 부분.)

후위 수식 계산에서도 스택이 사용된다.

프로그램의 수행 도중 발생되는 인터럽트의 처리와 인터럽트 처리가 끝난 후에 되돌아갈 명령 수행 지점을 저장하기 위해 스택이 사용되기도 한다.

(이 부분은 운영체제 강의에서 자세히 알 수 있는데 현재 방송대에서 운영체제 과목 구입이 불가능하다. 계약 문제 때문인 것으로 아는데 수강 신청을 해서 듣는 것 외에는 방법이 없는 걸로 안다. 그런데 2025년에 운영체제 과목을 새로 찍는 걸로 아니까... 아마도 지금 서비스 중인 과목은 더 이상 들을 수 없을 것.)

컴파일러(한 문자 한 문자씩 입력받은 후에 명령어의 문법이 옳은지 검사한다.),

순환 호출 관리(함수가 자기 자신을 되부른 후 되돌아갈 실행 주소를 저장하기 위해 하는 관리) 등에도 스택이 유용하게 사용된다.

...

스택은 입력값의 입력 순서나 사건의 선후 순서를 기억하기 위해 사용되는 자료구조다라고 생각하면 좋다.

...

4. 스택의 연산

...

5. 사칙연산식의 전위·후위·중위 표현

프로그램에서는 수식을 읽는 방향(수식의 입력 방향)과 연산자가 나타나는 방향을 모두 고려한 수식의 표기 방법이 필요하다.

우리가 보통 왼쪽에서 오른쪽으로 글이나 수식을 읽는다고 해서 1+2*3이란 식을 1+2, (1+2)*3 이런 식으로 계산해 버리면 연산자의 우선순위를 무시한 틀린 결과가 도출되기 때문이다.

그래서 입력되는 숫자와 수식들의 순서와 연산자 우선순위의 충돌을 해결하기 위해 중위 표기법, 전위 표기법, 후위 표기법이 만들어졌다.

...

우리는 여기서 후위 표기법에 집중하면 된다.

이가 컴퓨터로 처리되기에 가장 효율적인 표기법이기 때문이다.

중위 표기법은 우리가 흔히 쓰는 1+2 같은 것이고 전위 표기법은 +12 같은 식이다.

...

전위, 중위, 후위 표기법을 사용하는 방법은 별로 어려운 것이 아니기 때문에 여기에 별도로 정리하지 않았다.

...

끝!