선형 자료구조 - 스택

 영어 단어 Stack은 무더기, 더미를 의미합니다. 자료구조에서도 같습니다. 선형 자료구조의 하나로, 데이터의 더미를 의미합니다. 

 

근데 무언가의 더미라는 건 어떤 특성을 가질까요? 박스 더미를 생각해보면, 우리는 기존에 놓인 박스 위에 새로운 박스를 얹습니다. 밑에 얹을 수는 있지만 잘 그러지 않지요. 박스를 가져갈 땐 맨 위부터가 가져갑니다. 역시 밑에서부터 가져갈 수는 있지만 잘 그러지 않지요.

 

 자료구조에서도 비슷합니다. 데이터를 쌓는데, 먼저 들어온 것들을 밑에 두고 새로운 것이 항상 맨 위에 쌓이는 구조를 스택이라고 합니다. 스택에 접근할 때는? 가장 위의 데이터에 접근이 되겠죠.

 

 저는 ‘뭐야? 배열로, 리스트로 어디에도 접근을 잘하고 있었는데 이런 귀찮은 것은 왜쓰는겨??’ 라는 생각을 했었습니다. 하지만 개똥도 쓸데가 있는데 스택은 얼마나 쓸데가 많을까요. 기존의 선형 자료구조에 비해 제약이 생겼지만, 그 제약이 바로 스택과 다음 주에 설명할 큐를 이용하는 이유입니다.

 

 스택과 큐는 임시 데이터를 처리하는데 주로 사용되는 구조입니다. 임시로 쌓인 데이터들을 어떤 순서로 처리하는지에 따라 스택과 큐로 구분되는데, 오늘은 앞서 설명한 스택에 대해 설명해보려 합니다.

 

스택

 

 스택을 설명하는데 곧잘 쓰이는 말이 LIFO이다. Last in First Out의 줄임말인데, 마지막으로 들어온 것이 가장 먼저 나간다는 것을 의미한다. 우리말(이었던) 한자로 풀어보면 후입선출이다. 음식점 재고관리를 후입선출로 했다간 큰일이 나겠지만, 데이터는 그렇지 않다. 우리가 가장 흔히 쓰는 단축키 중에 ctrl + z, undo가 있다. 가장 마지막으로 행한 동작부터 차례대로 undo가 되는데, 이런 때 스택이 쓰인다.

 

 

 앞서 말한 것 처럼 스택도 선형 자료구조의 하나이다. 지난주에 다룬 배열이나 연결 리스트를 이용해 구현할 수 있다. 새로운 구조에 테이터를 담는다기 보단, 담겨진 데이터에 접근하고 활용하는 새로운 방식이라고 이해했다. 두 자료구조로 스택을 어떻게 구현하는지 알아보기 전에, 먼저 스택에 어떤 연산이 있는지 써보려 한다.

 

스택의 연산

• Push
  스택에 새로운 데이터를 넣는 연산이다. 위의 그림처럼 흔히 스택을 세로로 표현하는데, 이 가장 위에 데이터를 넣어준다.
• Pop
  스택 가장 위의 데이터를 반환하고 스택에서 제거한다. 앞서 임시 데이터를 처리하는데 주로 사용된다고 했는데, 사용된 데이터는 없어져야 할 때 사용하다 보니 이렇게 데이터를 없애주어야 한다.
• Peek
  스택 가장 위의 데이터를 반환만 한다. Pop과 다른 것은 데이터가 스택에 남아 있다는 점이다.

 

배열 스택

 

 배열엔 항상 한계가 있다. 그것은 할당받은 크기만큼만 사용할 수 있다는 뜻이다. 재할당이 가능하지만 일단 제껴보자. 그래서 배열 스택에는 들어갈 수 있는 데이터의 개수에 최대치가 존재한다. 그리고 현재 배열의 가장 끝 원소를 삭제하거나 그 뒤에 삽입할 때 시간복잡도가 O(1)이다. 스택은 가장 끝의 원소를 Pop해서 원소를 삭제하거나 Push해서 가장 끝에 원소를 삽입한다. 스택을 배열로 많이 구현하는 이유이다.

 

이렇게 배열을 반시계 방향으로 돌렸다고 생각하면 편하다.

 

 배열 스택을 편리하게 사용하기 위해서 top이라는 변수를 사용한다. top은 -1에서 시작하고, 현재 스택의 가장 위에 있는 데이터의 인덱스를 뜻한다. 그래서 스택이 비어있는 처음에는 -1이다. 데이터가 하나 들어오면 0이다. Push를 하면 데이터가 top + 1 인덱스에 들어간다. top은 배열의 크기 - 1 까지 값이 커질 수 있다. top이 배열의 크기 - 1에 달하는 순간, 스택은 꽉 차게 된다. 더 이상 Push를 할 수 없다.

 

 Pop을 하면 top이 1씩 줄어든다. top이 현재 가장 상단 데이터의 인덱스이기 때문에, 별다른 것 없이 Pop만 해줘도 스택에서 데이터를 없애는 효과를 낼 수 있다. 하지만 이는 스택에 접근할 때 인덱스를 top으로 접근할 때의 이야기다. top 사용은 배열 스택을 쓸 때 우리들의 약속이다. stack pointer라고도 부른다고 한다.

 

 top을 사용하지 않고 임의의 인덱스로 접근하면 어떻게 되는가? 이미 삭제된 (top 보다 높이 위치하는) 값을 조회하거나, 스택의 중간에 구멍을 만들거나 하는 수가 있다. 우리의 입에서 미소가 사라지는 순간이다.

 

리스트 스택

 

 배열이 찰떡이긴 하지만, 리스트 스택의 장점도 있다. 그것은 바로 스택의 크기에 한계가 존재하지 않는다는 것이다. 메모리가 허락하는 한 계속해서 Push를 할 수 있다.

 

 배열과 가장 크게 다르다고 생각한 점은, 항상 맨 앞에서 노드를 Push하고 Pop한다는 것이다. 배열은 맨 뒤가 스택의 가장 위였지만, 리스트는 맨 앞이 스택의 가장 위이다. 왜 이런 차이가 존재하는가? 단순한 연결 리스트로 구현할 때, 삽입 삭제가 가장 쉬운 곳은 맨 앞이기 때문이다. 배열처럼 가장 뒤에서 삽입/삭제가 이루어진다면, 매번 리스트의 가장 끝까지 포인터를 타고 타고 긴 여정 끝에 도달해야만 삽입과 삭제를 할 수 있을 것이다. 조회도 마찬가지다. 이런 낭비를 없애기 위해 가장 앞이 top이 된다.

 

  배열과 반대로 시계방향으로 돌렸다고 생각해보자.

 

 인덱스가 존재하지 않으니 stack pointer라거나 top이라고 부르는 인덱스가 필요하지 않다. 다만 가장 위 노드의 주소만 알고 있으면 된다. 이게 NULL을 가리키면 스택이 빈 것일 거고, 아니라면 스택에 무엇인가 있는 것이다.

 

스택의 응용

 

 멘토님께서 준비해주신 4개의 응용 문제를 풀어보면서 스택의 특성을 더 잘 이해할 수 있었다. 어떤 문제를 어떻게 풀었는지에 대한 기록이다. 반드시 스택을 사용해야 풀 수 있냐? 그것은 아니라고 생각한다. 하지만 스택을 쓸 때 효율적으로 쉽게 풀 수 있었다.

(글 하단에 코드가 담긴 깃허브 링크가 있습니다. 글로 이해가 안 가시는 부분이 있다면 코드도 함께 보시면 나을 거예요.)

 

1. 문자열 뒤집기

 문자열을 순회하며 첫 인덱스부터 마지막 인덱스까지 스택에 Push한다. 그러면 스택의 가장 밑에는 문자열의 첫 글자가, 가장 위에는 마지막 글자가 들어간다. 여기서 스택이 빌 때까지 Pop을 하면 문자열의 역순으로 글자가 튀어나오게 된다. 이걸 순서대로 이어 붙이면 뒤집어진 문자열 완성이다. 사실 이 문제는 스택으로 푸는게 효율적이거나 쉽지는 않았지만, 스택의 특성을 알려주기 위한 문제였다고 생각한다.

 

2. 괄호 검사

 이걸 어떻게 스택을 이용해서 푸냐! 열린 괄호를 만나면 스택에 Push한다. 닫히는 괄호를 만나면, 스택에서 Pop을 해 종류가 맞는가 확인한다. 문자열을 전부 순회했을 때, 스택이 비어있다면 이상한 괄호가 없는 것이다! 모든 괄호가 짝이 맞았다면 마지막에 스택이 비어있을 것이고, 아니라면 남는 녀석이 스택에 들어있거나, 문자열 순회중 닫는 괄호를 만나 Pop을 하려는데 스택이 비어있을 것이다. 이런 경우엔 닫히지 않은 괄호가 있는 것이다.

 닫는 괄호를 만날 때(1)는, 항상 마지막으로 열었던 괄호의 짝이어야 제대로 닫힌 것이다. 그러면 바로 다음에 또 닫는 괄호(2)를 만났다면? 마지막으로 열었던 괄호 하나 전에 열었던 괄호와 짝일 것이다. (1)에서 Pop을 한번 했으니 이제 스택에는 마지막 하나 전의 열린 괄호가 나올 것이다. 걔가 (2)의 짝이다. 괄호 짝이 맞는지 확인하는 것은 이런 식으로 흘러간다.

 괄호는 (소), {중}, [대] 세 가지의 괄호가 혼재하는 경우에, 각 괄호가 짝을 맞춰서 잘 닫혀 있는지, 그리고 닫히지 않은 괄호가 없는지 확인하는 문제이다. 예컨대 { ] 이런 식으로 짝이 안맞거나, ( { [ ] } 이런식으로 안 닫힌 괄호가 있다면 걸러주어야 한다.

 

3. Reverse Polish Notation

 이 문제는 사실 후위 표기법 계산 문제라고 알려주셨다. 근데 RPN이 더 멋지다고 생각해서 RPN이라고 표기한다. 이 표기법은 우리가 평소 쓰는 중위 표기법에 비해 괄호가 없다. 연산자에 따른 우선순위를 고려하지 않아도 된다. 그래서 구현이 쉬운 편에 속한다.

A + (B * C)라는 수식이 있다고 생각해보자. 이를 후위 표기법으로 표기하면 A B C * + 이다. 우째 이렇게 되는가?

 후위 표기법에선 숫자를 만나면 넘어가다가 연산자를 만나면 직전 2개의 숫자에 해당 연산자를 적용하고, 그 자리에 그 숫자를 놓는다. 위 수식에 적용해보자. *를 만나면 직전 B와 C에 적용한다. B * C이다. 편의를 위해 괄호로 감싸 그 자리에 놓아보자. A (B * C) + 가 남는다. 이제 + 를 만난다. 직전 두 숫자 A와 (B * C)를 더한다. A + (B * C)가 되는 것이다. 몹시 마법 같다.

 어 자꾸만 이렇게 직전 뭐를 꺼내고 자시고 한다면??? 스택이 등장하기 딱 좋은 때다. 후위 표기법 계산에는 스택을 이용한다. 숫자를 만나면 스택에 Push한다. 연산자를 만나면 Pop을 두 번 하고, 연산자를 적용하고, 결과를 Push 한다. 마지막에 스택이 비어있다면? 짜잔, 수식이 계산되는 것이다.

 

4. 미로찾기

 아찔하다. 이제는 미로를 돌파해야 한다. 미로에서 출구를 찾을 때는 어떻게 할까? 감으로 찾는 법도 있지만, 그거는 운이 매우 좋아야 할 것이다. 정석적으로 미로를 탈출하는 방법은 다음과 같을 것이다.

 

1. 막다른 길이 나올 때까지 간다.
2. 갈 곳이 없다면, 직전 갈림길까지 돌아간다.
3. 1과 2를 출구가 나올 때까지 반복한다.

 어?? 직전 갈림길?? 반복??? 스택의 냄새가 난다. 깊숙이 들어갔다가, 길이 막혀있으면 나온다. Depth First Search를 줄여 DFS 알고리즘이라고 부른다. 스택을 이용하면 DFS를 쉽게 구현할 수 있다.

인간은 길이 막혀있으면 알아서 방향을 전환하니까 상관없지만, 컴퓨터를 위해서 방향을 추가해주면 다음과 같은 시퀀스가 나온다.

 

1. 방향 전환 순서는 오른쪽→아래→왼쪽→위 등으로 임의로 정하면 된다.
2. 현재 방향으로 진행할 수 있다면, 진행한다.
3. 진행할 수 없다면(벽으로 막혀있거나, 이미 지나온 길인 경우), 방향을 전환한다.
4. 2, 3을 반복하다 사방이 모두 진행 불가라면, 한 칸 되돌아간다.

 이것만 반복하면 된다! 다만 한 칸 되돌아갈 곳을 기억해줘야 하기 때문에, 이동할 때마다 현재 위치를 스택에 Push하면 된다. 갈 곳이 없다면, 갈 방향이 생길 때까지 Pop을 하며 되돌아가면 된다.

 

메모리의 스택 영역과 함수의 재귀 호출

 

 DFS 알고리즘은 재귀로도 풀 수 있다. 구글에 DFS 미로찾기를 검색해보면 함수의 재귀 호출을 이용해 푼 문제가 대부분이다. 찾다 보면 dfs를 함수 이름으로 사용하는 코드도 심심찮게 볼 수 있다. 그러면 우째 스택으로도 풀 수 있고 재귀로도 풀 수 있는가??

 

 바로바로 C에서 함수가 호출될 때, 스택에 차곡차곡 쌓이기 때문이다! 이 방식이 우리가 구현한 스택을 사용하는 것과 같다. 어떤 스택?? 바로 메모리의 스택 영역이다. 함수를 호출하면 Push되고, 함수가 끝나면 Pop된다. 함수 안에서 함수가 호출되면 스택에 함수가 차곡차곡 쌓이고, 함수가 종료되는 순서대로 스택에서 사라진다. 스택을 직접 구현하는 대신, 메모리의 스택 영역을 사용해버리는 것이다.

 

 무한히 재귀적으로 호출되는 함수를 실행하면, 스택이 넘치게 된다. 이것을 Stack Overflow라고 부르고, 허용되지 않은 메모리 영역에 침범해 segmentation fault를 일으키게 된다.

 

 

구현 코드: DataStructureStudy/Stack at main · triplecheeseburger/DataStructureStudy