[자료구조] 스택(Stack)

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

1. 개요
2. 본문
3. Reference

---

개요

큐와 유사하지만 분명한 대조성을 띄고 있는 자료 구조, 스택(Stack)에 대해서 정리해 보도록 하겠습니다.
스택의 구조를 이해하고 최종적으로 스택 자료구조를 구현해 보도록 하겠습니다.

---

본문

스택 구조

데이터를 제한적으로 접근할 수 있는 자료 구조입니다.

한 쪽 끝에서만 데이터를 삽입/삭제가 가능합니다.

스택은 LIFO(Last-In-First-Out) 방식을 사용합니다.

*LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 방식을 뜻합니다.

Ref - https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

스택 용어

• pop : 스택에 제일 마지막(아래)에 삽입된 데이터를 추출
• push : 스택에 제일 최근(위)에 데이터를 삽입

 

스택 구조와 프로세스 스택 

스택 구조는 프로세스 실행 구조의 가장 기본이 됩니다.

• 프로그램이 실행되는 상태를 프로세스라고 하며, 프로세스에서 함수를 호출하는 경우 프로세스 스택을 사용합니다.
  프로세스 스택은 LIFO 정책에 의해 제일 마지막에 실행된 함수를 제일 먼저 실행하게 됩니다.

 

프로세스 스택 예제

아래와 같이 코드를 실행할 경우, 재귀 함수인 recursive가 차례대로 호출될 것입니다.
이때, 함수들을 프로세스 스택에 쌓게 되고 종료 조건을 만나면 스택에 쌓인 상태로 LIFO 정책을 고려하여 수행될 것입니다.

아래의 예제에서는 다음과 같이 실행됩니다.
recursive(-1) -> recursive(0) -> recursive(1) -> recursive(2) -> recursive(3) -> recursive(4)
*제일 마지막에 호출된 recursive(-1)가 제일 먼저 수행됨.

def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)
        
recursive(4)

 

스택의 장/단점

장점

• 구조가 단순해서 구현이 쉽습니다.
  
  
• 데이터 저장/읽기 속도가 빠릅니다.

 

단점

• 스택의 크기를 선언해야 하기 때문에, 데이터 크기만큼 미리 선언해야 합니다.
  *이는 저장 공간의 낭비로 이어질 수 있습니다.
  *파이썬의 경우 재귀 함수가 1000번까지만 실행이 가능합니다.
  *Linked List를 이용하여 해당 단점을 보완할 수 있습니다.

 

스택 구현 코드

리스트 기능을 사용하여 스택을 구현

*파이썬은 append 함수가 push 기능의 역할을 수행하며, pop 기능은 이미 존재합니다.

data_stack = list()

data_stack.append(1)
data_stack.append(2)
data_stack.append(3)

# input 순서는 1>2>3 이지만, output 순서는 3>2>1
# 제일 마지막에 input 된 값이 제일 먼저 output 되는 스택 구조 (LIFO 정책)
print(data_stack.pop())
print(data_stack.pop())
print(data_stack.pop())

 

 

직접 스택 구현 (본인)

data_stack = list()

# list의 append 메서드를 통해 요소 추가
def push(n):
  data_stack.append(n)

# list에 저장되어 있는 제일 마지막 요소를 추출하기 위해 idx 값 저장
# print로 출력 후 요소 삭제
def pop():
  idx = len(data_stack)-1
  print(data_stack[idx])
  del data_stack[idx]

# 현재 남아있는 요소를 보여줌
def showStack():
  print(data_stack)

push(1)
push(2)
push(3)
push(4)
push(5)

pop()
pop()

showStack()

 

직접 스택 구현(강사)

data_stack = list()

def push(n):
  data_stack.append(n)

# 파이썬의 리스트 특징을 잘 사용한 것이 두드러짐
# 리스트 요소를 바로 삭제하면 반환할 수 없으니 임시 변수로 data를 선언함
def pop():
  data = data_stack[-1]
  del data_stack[-1]
  return data

# 간단한 경우에도 반복은 반복문 쓰기
for i in range(0,5):
  push(i)

pop()

---

Reference

• 코드 없는 알고리즘과 데이터 구조
• 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online.