C++로 쉽게 풀어쓴 자료구조/ 스택

스택(Stack)의 추상 자료형

스택이란

입출력이 후입선출(Last-In First-Out)인 자료구조.

스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다.

스택의 추상 자료형

  • 객체
    • 후입선출의 접근 방법을 유지하는 요소들의 모음
  • 연산
    • push(x): 주어진 요소 x를 스택의 맨 위에 추가한다.
    • pop(): 스택이 비어있지 않으면 맨 위의 요소를 삭제하고 반환한다.
    • peek(): 스택이 비어있지 않으면 맨 위의 요소를 삭제하지 않고 반환한다.
    • isEmpty(): 스택이 비어있으면 true 아니면 false를 반환한다.
    • isFull(): 스택이 가득차 있으면 true 아니면 false를 반환한다.
    • size(): 스택 내의 모든 요소들의 갯수를 반환한다.
    • display(): 스택 내의 모든 요소들을 출력한다.

스택의 활용 예

  • 문서나 그림 편집기에서 undo 기능을 구현할 때
  • 함수 호출에서 복귀 주소를 기억할 때
  • 소스코드나 문서에서 괄호 닫기가 정상적으로 되었는지를 검사할 때 등

스택의 구현

배열을 이용한 스택의 표현

배열로 스택을 구현할 때는 크기가 정해진 배열과 배열의 최상단 데이터를 가리키는 top 변수가 필요하다.

top 변수는 최초 -1로 초기화 되었다가 요소가 삽입되면 +1씩 증가하고, 요소가 삭제되면 -1씩 증가한다.

연결 리스트를 이용한 스택

배열을 이용하여 스택을 구현할 경우 구현은 간편하지마나 크기가 제한된다는 단점이 있다. 연결 리스트를 이용하면 이 문제를 해결할 수 있는데, 이에 대한 자세한 내용은 5장에서 한다.

스택의 응용

괄호 검사

괄호는 가장 가까운 거리에 있는 괄호들끼리 서로 쌍을 이룬다. 따라서 스택을 사용하여 왼쪽 괄호들을 만나면 계속 삽입하다가 오른쪽 괄호들이 나오면 스택에서 가장 최근의 왼쪽 괄호를 꺼내어 짝을 맞춰 보는 식으로 오류를 검사할 수 있다.

수식 계산

수식 계산은 3가지 형태로 할 수 있다.

  • 전위(prefix) 표기법: 연산자를 피연산자 앞에 표기한다. +ab, +5*ab
  • 중위(infix) 표기법: 연산자를 피연산자 사이에 표기한다. a+b, 5+a*b
  • 후위(postfix) 표기법: 연산자를 피연산자 뒤에 표기한다. ab+, 5ab*+

사람들은 중위 표기법에 익숙하지만 컴파일러는 주로 후위 표기법을 사용하는데 이유는 다음과 같다.

  • 괄호를 사용하지 않고도 계산해야 할 순서를 알 수 있다.
  • 연산자의 우선순위를 생각할 필요가 없다. 식 자체에 우선순위가 이미 포함되어 있다.
  • 수식을 읽으면서 바로 계산할 수 있다. 중위 표현식은 괄호와 연산자의 우선순위 때문에 수식을 끝까지 읽은 다음에야 계산이 가능하다.

이러한 이유로 컴파일러는 프로그램 개발자가 표기한 중위 표기식을 후위 표기식으로 바꾸고, 변환된 후위 표기식으로 계산하는 방법을 사용한다.

중위 표기식이나 후위 표기식이나 피연산자의 순서는 같다. 그러나 연산자의 순서는 다르기 때문에, 중위 표기식을 후위 표기식으로 바꾸는 과정에서 연산자를 별도로 처리하는 스택이 필요하다. 더불어 연산자 사이엔 우선순위가 존재하므로 –곱셈이 덧셈보다 우선순위가 높고, 괄호의 우선순위가 높다– 우선순위를 반영해서 표기식을 변환해야 한다. 표기식을 변환하는 알고리즘은 다음과 같다.

  • 중위 표기식에서 피연산자를 만나면 후위 표기식에 바로 추가한다.
  • 중위 표기식에서 연산자를 만나면 아래의 연산자 처리를 적용한다.
    • 현재 연산자보다 우선순위가 높거나 같은 연산자는 모두 출력하여 후위 표기식에 추가한 후 현재 연산자를 연산자 스택에 넣는다.
    • 왼쪽 괄호를 만나면 일단 연산자 스택에 넣은 후, 오른쪽 괄호를 만나면 왼쪽 괄호가 삭제될 때까지 왼쪽 괄호 위에 쌓여 있는 모든 연산자들을 출력하여 후위 표기식에 추가한다.

미로 탐색 문제

미로 탐색 문제는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, Breadth First Search)으로 구분할 수 있다. 이 중 깊이 우선 탐색은 일단 갈 수 있는 데까지 간 후에 막히면 다른 길을 찾는 방식인데 이 방식은 스택 자료 구조가 적합하다. 반면 너비 우선 탐색은 일단 주위를 다 둘러 본 후에 다음 위치로 이동하는 방식으로 큐 자료 구조가 적합하다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기