[자료구조 및 프로그래밍] 1. Stack (implement with Array)

Stack ( 스택 ) 이란

스택이라는 자료구조는 매우 직관적으로 이해할 수 있는 자료구조이다.

스택이라는 말 자체가 이미 이 자료구조에 대해 모든 걸 설명하고 있다.

번역기 조차 번역을 하지 않는다..

보통 스택이라고 하면 어떤 것들이 쌓여있는 형태를 의미하는데,

스택이라는 자료구조도 무언가를 쌓는 형태를 자료구조화 한 것이다.

 

가령 책이 한 무더기 쌓여있다고 해보자.

중간에 있는 원하는 책을 찾아 꺼내려면 어떻게 해야할까?

가장 당연하게 떠오르는 방법은 맨 위에 있는 책부터 하나씩 하나씩 확인하면서 찾을 것이다.

중간 어디에 있는지도 모르는데 책을 무더기로 들춰가면서 찾는 것은 너무 힘들지 않을까

 

그 책 무더기에 새로운 책을 여러권 놓는다고 해보자.

그러면 가장 먼저 놓은 책이 제일 밑에 놓이고, 가장 나중에 놓은 책이 맨 위에 놓이는 것은 아주 당연하다.

스택은 그냥 그 자체로 모든 것을 설명하고 있는 아주 자명한 자료구조이다.

스택 자료구조에 데이터가 쌓이는 과정

스택에 데이터를 넣는 것을 Push 라고 한다.

스택에는 제일 마지막에 넣는 데이터가 맨 위로 올라오게 된다.

스택에서는 맨 위에 있는 데이터가 의미 있기 때문에, 이 위치를 가리켜 Top 이라고 특별히 명명해준다.

 

스택에 쌓인 데이터가 나오는 과정

반대로 스택에서 데이터를 빼는 것을 Pop 이라고 한다.

스택에서는 가장 위에 있는 데이터 (Top) 부터 Pop 된다.

 

이것이 스택의 전부이다.

 

스택 자료구조는 일상에서도 어렵지 않게 찾아볼 수 있다.

브라우저에서 페이지를 방문하다가 뒤로 가기를 누르면 직전에 방문했던 페이지가 나오고,

한번 더 뒤로 가기를 누르면 그 직전에 방문했던 페이지가 나온다.

 

브라우저에서 특정 페이지를 새롭게 방문하는 것은, 브라우저 히스토리 스택에 데이터를 Push 하는 것과 같고,

뒤로 가기를 누르는 것은, 브라우저 히스토리 스택에서 데이터를 Pop 하는 것과 같다.

 

스택의 Top 에는 언제나 가장 마지막에 Push 했던 데이터가 저장되고,

Pop 을 할 때는 스택의 Top 에 있는 데이터를 Pop 하므로, 마지막에 들어온 데이터가 먼저 나가는 특징을 보인다.

이를 LIFO (Last In First Out) 구조라고 한다.

---

스택의 구현 (with Array)

이제 스택을 실제 프로그램에서 구현한다고 해보자.

아주 많은 언어들이 이미 스택 자료구조를 자체적으로 구현해서 라이브러리로 제공하지만,

한번 배열을 이용해서 스택을 0부터 직접 구현하는 과정을 거쳐보자.

 

처음에는 직접 코드를 짜기보다 수도코드 형태로 짜보고자 한다.

먼저 배열을 이용해서 스택을 구현하는 것은 직관적으로 아래와 같이 생각할 수 있다.

크기가 5인 배열을 선언하였을 때,

배열에 값이 없는 인덱스 중 가장 작은 인덱스부터 값을 채워나가는 것을 Push로 하고,

배열에 값이 있는 인덱스 중 가장 큰 인덱스 부터 값을 빼나가는 것을 Pop 이라고 보면 스택의 동작과 같다.

 

일반적인 상황에서

배열에 값이 없는 인덱스 중 가장 작은 인덱스 = 배열에 값이 있는 인덱스 중 가장 큰 인덱스 + 1 이므로,

둘 중에 하나의 값만 저장해도 나머지 값을 구할 수 있다.

 

둘 중에 어떤 값을 이용하느냐에 따라 스택의 구현 방법이 조금 달라지는데,

먼저 배열에 값이 없는 인덱스 중 가장 작은 인덱스(A)를 이용해보자.

 

아까 스택에서는 제일 위에 있는 값이 의미있는 값으로서 Top 으로 명명한다고 하였다.

이제 A 를 Top 으로 생각하고 구현해보자.

이때 A는 "나중에 Push를 하는 경우 값이 추가될 인덱스" 를 의미한다.

 

먼저 크기가 N인 배열을 선언한다.

stack => array of size N

그리고 A 역할을 할 변수 top 을 선언해두자.

초기에는 스택이 비어있는데, 맨 처음 값이 추가될 인덱스는 0 이므로, top 변수는 0으로 초기화한다.

init: top;  // top 은 global 변수로서 어느 곳에서든 접근할 수 있다.
top <- 0

크기가 5인 배열을 이용한다면 위 그림과 같은 상황이 되겠다.

---

이제 배열에 값을 추가하는 push 를 구현해보자.

top 이 값을 추가할 인덱스를 가리키고 있으므로, 추가할 값을 top이 가리키는 배열 인덱스에 넣으면 된다.

push(x) {
  stack[top] <- x;
}

그런데 top 이 가리키는게 무엇이었는가?

'앞으로 값이 추가될 때 해당 값을 넣을 인덱스' 였다.

이제 top 에는 값이 존재하므로 top 이 가리키는 인덱스를 1 증가시켜 주어야 한다.

push(x) {
  stack[top] <- x;
  top <- top + 1;
}

이것으로 '일반적인 상황' 에서의 push 구현이 완료되었다.

하지만 특수한 상황이 하나 있다.

바로 배열이 가득 찬 상황에서 push 를 하는 경우다.

이런 경우를 Overflow 라고 한다.

 

overflow 가 발생하는 경우는 어떤 경우일까?

top 이 가리키는 인덱스가 배열이 허용하는 인덱스를 넘은 경우

즉 top >= n 인 경우가 되겠다.

push(x) {
  if (top >= n)
  	OVERFLOW! 			// overflow 가 발생하면 이후의 코드는 실행되지 않는다.
    
  stack[top] <- x;
  top <- top + 1;
}

이것으로 push 기능의 수도 코드가 완성되었다.

---

pop도 마찬가지로 작성해보자.

pop을 하게 되면, 스택의 가장 위의 값이 가리키고 있는 값을 리턴해주어야 한다.

 

현재 우리가 정의한 top 변수는 '값이 새롭게 추가될 인덱스' 이므로, 우리가 개념적으로 정의한 top 과 조금 다르다.

따라서 현재 스택에 있는 값 중 가장 큰 값을 가리키려면 top - 1 을 해주어야 한다.

pop() {
  y <- stack[top-1];
  return y;
}

하지만 pop 을 하고나면 스택의 데이터가 하나 사라지는 것과 같으므로,

우리가 정의한 top (값이 들어있지 않은 인덱스 중 가장 작은 인덱스) 이 1 작아져야 한다.

pop() {
  y <- stack[--top];
  return y;
}

리턴 이후에는 코드가 실행되지 않으므로, C 언어식으로 표현한다면 이렇게 세련되게(?) 표현할 수 있다.

 

하지만 이것도 '일반적인 상황' 만을 고려한 것이다.

만약 스택이 비어있는 상황에서 pop 을 한다면 어떻게 될까?

꺼낼 자료가 없는데 꺼내라는 명령을 실행시킬 수는 없는 노릇이다.

이런 상황을 Underflow 라고 한다.

 

underflow 는 어떻게 체크할까?

지금 구현한 스택은 top = 0 일 때 비어있는 상황이므로,

top <= 0 이면 꺼낼 수 있는 데이터가 없으니 Underflow가 발생한다고 볼 수 있다.

pop() {
  if (top <= 0)
    UNDERFLOW!       // UNDERFLOW 발생 시에는 아래의 코드가 실행되지 않는다.
    
  y <- stack[--top];
  return y;
}

---

이것으로 스택의 모든 기능 구현이 완료되었다.

정리하면 아래와 같이 된다.

stack: array of size N   // stack 은 global 변수로서 어느 곳에서든 접근할 수 있다. 
init: top;               // top   은 global 변수로서 어느 곳에서든 접근할 수 있다.
top <- 0


push(x) {
  if (top >= n)
  	OVERFLOW! 			// overflow 가 발생하면 이후의 코드는 실행되지 않는다.
    
  stack[top] <- x;
  top <- top + 1;
}


pop() {
  if (top <= 0)
    UNDERFLOW!       // UNDERFLOW 발생 시에는 아래의 코드가 실행되지 않는다.
    
  y <- stack[--top];
  return y;
}

---

이렇게 구현하기 싫은데요?

분명 개념상으로 top 은 스택의 가장 위의 데이터를 가리키고 있다.

따라서 구현할 때도 이에 맞춰 top 을 설정하고 싶을 수 있다.

이런 경우 구현의 디테일이 조금 달라진다.

 

이때 top 은 현재 스택에 값이 존재하는 인덱스 중 가장 큰 인덱스를 의미하게 된다.

그렇다면 top 의 초기화는 0 이 되면 안된다.

top = 0 이라는 이야기는 배열의 0번째 인덱스에 스택의 top 데이터가 있다는 의미이기 때문이다.

 

따라서 이 경우 top 은 -1 로 초기화하는 것이 바람직하다.

init: top;  // top 은 global 변수로서 어느 곳에서든 접근할 수 있다.
top <- -1

이제 push, pop 도 조금씩 구현이 달라지게 된다.

 

push 를 할 때는 더이상 top 이 원소를 추가할 위치를 가리키지 않으므로

top 을 +1 시킨 후, top 이 가리키는 위치에 원소를 추가해야 한다.

(물론 순서를 바꿔도 되지만 그러면 코드가 깔끔하지 않다)

 

또 Overflow를 체크하는 것도, n 이상이 아니라 n-1 이상일 때 오버플로우로 인식하도록 해야한다.

배열의 가장 큰 인덱스가 n-1 이기 때문이다.

push(x) {
  if (top >= n-1)
  	OVERFLOW! 			// overflow 가 발생하면 이후의 코드는 실행되지 않는다.
  
  stack[++top] <- x;
}

pop 을 할 때는 현재 top 이 가리키는 인덱스가 실제 스택의 top 이므로

top 인덱스 값을 바로 빼낸 이후에 top을 1 감소시키면 끝이다.

 

Underflow 체크는 top 이 -1 이면 빈 상태이므로

top <= -1 일 때 Underflow가 발생하는 것으로 볼 수 있다.

pop() {
  if (top <= -1)
    UNDERFLOW!       // UNDERFLOW 발생 시에는 아래의 코드가 실행되지 않는다.
    
  y <- stack[top--];
  return y;
}

정리하면 아래와 같다.

stack: array of size N   // stack 은 global 변수로서 어느 곳에서든 접근할 수 있다. 
init: top;               // top   은 global 변수로서 어느 곳에서든 접근할 수 있다.
top <- -1


push(x) {
  if (top >= n-1)
  	OVERFLOW! 			// overflow 가 발생하면 이후의 코드는 실행되지 않는다.
    
  stack[++top] <- x;
}


pop() {
  if (top <= -1)
    UNDERFLOW!       // UNDERFLOW 발생 시에는 아래의 코드가 실행되지 않는다.
    
  y <- stack[top--];
  return y;
}

---

이것으로 스택을 배열을 이용해서 구현하는 과정을 알아보았다.

구현할 때 초기 top 변수 값을 어떻게 잡는지에 따라 pop과 push 기능의 구현이 달라지는 디테일이 있다.

 

다음에는 배열을 이용해서 큐를 구현하는 과정을 정리하고자 한다.