핵심 자료구조 - 스택(Stack)

스택(Stack)은 자료구조의 한 종류로, 가장 간단하고 널리 사용되는 구조 중 하나다.

스택은 마지막에 들어온 데이터가 가장 먼저 나가는 구조로, LIFO(Last In, First Out) 원칙을 따른다. 이는 한쪽 끝으로만 데이터를 넣고 뺄 수 있는 구조로, 접시를 쌓거나 종이를 쌓는 방식과 비슷하다. 예를 들어, 마트에서 바구니를 쌓아두는 방식을 생각하면 이해하기 쉽다. 맨 위에 있는 바구니가 가장 먼저 꺼내지는 것처럼, 스택에서도 마지막에 들어온 데이터가 가장 먼저 처리된다.

 

이러한 스택의 원리를 컴퓨터에 적용하면 다양한 문제를 효율적으로 해결할 수 있다. 이번 포스터에서는 스택의 개념과 활용에 대해 자세히 알아보도록 하겠다.

1. 개요

스택은 한쪽 끝(Top)에서만 데이터를 삽입하고 제거할 수 있는 구조다. 이러한 제약으로 인해 불편하거나 비효율적이라고 생각할 수도 있지만, 프로그래밍에서는 매우 유용하게 활용된다.

 

특히 메모리 관리에서 스택은 중요한 역할을 한다. 프로그램이 실행될 때 메모리는 크게 전역 영역(Global Area), 힙 영역(Heap Area), 그리고 스택 영역(Stack Area)으로 나뉘는데, 스택 영역은 함수 호출과 관련된 데이터를 저장하는 데 사용된다. 현재 실행 중인 코드의 프로세스나 스레드는 스택 영역을 통해 효율적으로 데이터를 관리하고 함수 호출을 추적할 수 있다.

 

또, 함수를 호출하면 함수가 실행된 다음 다시 원래 위치로 돌아와야하는데 이 돌아올 위치를 저장하는 데도 스택이 필요하다. 이러한 점에서 스택은 편리한 부분이 있기에 지속해서 쓰고 있다.

 

이처럼 스택은 단순하면서도 강력한 구조로, 함수 호출 관리, 수식 계산, 괄호 검사, 데이터 역순 처리 등 다양한 분야에서 활용된다.

 

2. 스택의 동작방식

스택 자료구조는 push, pop, sitze, empty 등의 기능을 제공한다. 이에 대해 쉽게 설명하면 다음과 같다. 

 

마트에서 물건을 고를 때 사용하는 바구니를 떠올려 보자. 바구니에 물건을 하나씩 쌓으면, 마지막에 넣은 물건이 가장 위에 위치하게 된다. 바구니에서 물건을 꺼낼 때는 맨 위에 있는 물건부터 꺼내게 된다. 이 과정을 스택의 기능과 연결해 보겠다.

---

1) Push (넣기)

• 바구니에 물건을 담는 행위.
• 예: 사과를 먼저 넣고, 그 위에 우유를 넣으면 바구니에는 [사과 → 우유] 순서로 쌓인다.
• 스택에서 push 연산을 사용하면 데이터가 스택의 맨 위에 추가된다.

Push(사과) → Push(우유)  
바구니 상태: [사과, 우유]

 

2) Pop (빼기)

• 바구니에서 물건을 꺼내는 행위다. 가장 위에 있는 물건이 먼저 나온다.
• 예: 바구니에서 우유를 먼저 꺼내면, 그 다음에는 사과가 나온다.
• 스택의 pop 연산은 가장 위에 있는 데이터를 제거하고 반환한다.

Pop() → 우유 꺼냄  
바구니 상태: [사과]

 

3) Top (맨 위 확인)

• 바구니의 맨 위에 어떤 물건이 있는지 확인하는 행위다.
• 예: 바구니에 사과와 우유가 있을 때, 맨 위에 있는 물건은 우유다.
• 스택의 top 연산은 데이터를 제거하지 않고 맨 위의 데이터를 확인한다.

Top() → 우유 확인  

 

4) Size (크기 확인)

• 바구니에 담긴 물건의 개수를 확인하는 행위다.
• 예: 바구니에 사과와 우유가 있으면, 총 2개의 물건이 들어 있다.
• 스택의 size 연산은 스택에 쌓여 있는 데이터의 개수를 반환한다.

Size() → 2  

 

5) Empty (비었는지 확인)

• 바구니에 물건이 하나도 없는지를 확인하는 행위다.
• 예: 바구니가 비어 있다면 물건을 꺼낼 수 없다.
• 스택의 empty 연산은 스택이 비어 있으면 True, 그렇지 않으면 False를 반환한다.

Empty() → True (바구니가 비어 있음)  

바구니에 물건을 쌓고 꺼내는 과정을 시각적으로 표현하면 다음과 같다.

---

처음 상태 (비어 있음)

바구니: [ ]

 

Push(사과) → Push(우유)

바구니: [사과] 바구니: [사과, 우유] (우유가 맨 위에 쌓임)

 

 

Pop() → 맨 위 물건 꺼냄

바구니: [사과] (우유 꺼냄)

 

Top() → 맨 위 확인

바구니의 맨 위: 사과

 

Empty() → 바구니가 비었는지 확인

바구니: [사과] → False (비어 있지 않음) 바구니: [ ] → True (비어 있음)

 

3. 구현

이를 파이썬으로 구현하면 다음과 같다. 

def __init__(self):
	self.data[]
    
def push(self, x):
	self.data.append(x)

def pop(self):
    if not self.data:
        return -1
    return self.data.pop()
    
def size(self):
    return len(self.data)

def empty(self):
    if not self.data:
        return 1
    return 0

def top(self):
    if not self.data:
        return -1
    return self.data[-1]

 

이외에도 다음과 같은 방법도 존재한다. 이것은 파이썬 자체 라이브러리를 사용한 활용이다.

 

# 1. 리스트를 선언한다.
stk = []

# 2. 리스트에 값을 추가한다.
for item in ["고기", "빵", "과일", "채소"]:
	stk.append(item)
    
# 3. pop으로 가장 나중에 추가한 원소를 제거한다.    
print(stk.pop())

# 4. 스택의 가장 위에 위치한 값을 확인한다.
print(stk[-1])

# 5. 스택이 비었는지 확인한다.
print("empty" if not stk else "not empty")

 

출처

알고리즘 인사이드 with 파이썬 | 손혁제 - 교보문고