[자료구조] 스택 (Stack)

스택은 데이터를 쌓고 꺼낼 수 있는 선입선출(FILO) 자료구조 입니다. 먼저 들어간 데이터가 나중에 나오는 규칙으로 스택에 삽입하는 연산을 푸시(push), 꺼내는 연산을 팝(pop)이라고 합니다.

 

스택의 연산과 동작 이해

구분	정의	설명
연산	boolean isFull()	스택에 들어있는 데이터 개수가 maxsize인지 확인해 boolean값을 반환 (가득차 있다면 True, 아니면 False)
	boolean isEmpty()	스택에 들어있는 데이터가 하나도 없는지 확인해 boolean 값을 반환 (데이터가 하나라도 있으면 False, 아니면 True)
	void push (itemType item)	스택에 데이터를 푸시
	itemType pop()	스택에서 최근에 푸시한 데이터를 팝하고, 그 데이터를 반환
상태	int top	스택에서 최근에 푸시한 데이터의 위치를 기록
	ItemType data[maxsize]	스택의 데이터를 관리하는 배열

 

스택 push 연산 시, 데이터가 가득 찼는지 확인하고, 그렇지 않으면 top을 1만큼 증가시킨 후, top이 가리키는 위치에 data[0]에 데이터를 추가합니다.  pop 연산 시에는 데이터가 비어있는지 확인하고, 데이터가 있으면 top을 1 감소시키고, top을 통해 최근에 삽입한 데이터를 반환합니다.

스택의 동작원리와 ADT

 

 

스택 ADT 구현해보기

스택을 구현해보면 동작원리를 이해하는데 도움이 됩니다. 다만 스택을 활용해서 문제를 풀어야 겠다는 생각을 하기가 아직 쉽지 않은 것 같습니다. 스택 관련 문제를 많이 풀어봐야 감이 생길 것 같습니다.

stack = []     # 스택 리스트 초기화
max_size = 10  # 스택의 최대 크기

# 스택이 가득 찼는지 확인
def isFull(stack):
   return len(stack) == max_size

# 스택이 비어 있는지 확인하는 함수
def isEmpty(stack):
   return len(stack) == 0
   
# 스택에 데이터를 추가하는 함수
def push(stack, item):
   if isFull(stack):
      print("스택이 가득 찼습니다.")
   else:
      stack.append(item)
      print("데이터가 추가되었습니다.")


# 스택에서 데이터를 꺼내는 함수
def pop(stack, item):
   if isEmpty(stack):
      print("스택이 비어있습니다.")
      return None
   else:
      print("데이터를 반환했습니다.")
      return stack.pop()

 

 

스택 문제 풀어보기

N은 이진수로 변환할 숫자 입니다. N을 이진수로 변환하는 과정은 N이 1일 될 때까지 2로 계속 나누므로 연산 횟수는 "logN" 입니다. 하지만 문자열의 += 연산자는 수행할 때마다 객체를 새로 생성하므로 시간복잡도는 "O((logN)^2)"이 됩니다.

# 10진수를 입력받아 2진수로 변환해 반환하는 solution() 함수 구현
def solution(num):
   stack = []
   while num > 0:
      stack.append(str(num % 2))
      num //= 2

   binary = ""
   while stack:
      binary += stack.pop()
   
   return int(binary)

solution(13)  # 2진수: 1101