[자료구조] Stack - 스택

정의

사전적 의미

• (보통 깔끔하게 정도된) 무더기(더미), 쌓다, 채우다 등

우리가 공부할 STACK의 의미

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
• 저장된 자료는 선형구조를 갖는다.
• 후입선출(LIFO, Last In First Out)
• top: 마지막에 삽입된 원소의 위치(저장된 자료 중 가장 마지막에 들어간 자료)

[출처] http://www.incodom.kr/스택

기능

• Push : 자료를 저장소에 저장
• Pop : 저장되어 있는 자료 중 가장 최근 자료를 꺼냄
• IsEmpty : 저장소가 비어있는지 확인
• peek : top에 위치한 원소(item) 반환

구현

• push
  • List의 append()함수 활용
  • def push(item): stack.append(item) stack = [] push(10) print(stack) # [10]
  • 함수의 활용 없이 구현
  • def push(item, size): global top if top == size: print('overflow!') # 저장소의 크기보다 자료를 더 많이 저장할 수 없다. else: top += 1 stack[top] = item size = 10 stack = [0] * size top = -1 push(10, size) print(stack) # [10, 0, 0, 0, 0, 0, 0, 0, 0, 0]
• pop
  • List의 pop()함수 활용
  • def stack_pop(): if stack: # stack 내부에 내용이 있으면 True return stack.pop() else: return 'underflow!' stack = [10] print(stack_pop()) # 10 print(stack_pop()) # underflow!
  • 함수 활용 없이 구현
  • def pop(): global top if top == -1: return 'underflow!' else: top -= 1 return stack[top+1] top = -1 size = 10 stack = [0] * size print(pop()) # underflow! top += 1 print(pop()) # 0

주의사항

• List의 append()와 pop()을 사용시에 편할 수 있지만 자료의 수가 많아질수록 속도 저하
• 1차원 배열을 사용하여 구현할 경우 구현이 용이, 스택의 크기를 변경하기 어려움
  • 보완: 저장소를 동적으로 할당하여 스택을 구현
    • 동적 연결리스트를 이용하여 구현하는 방법
    • 장점: 메모리의 효율적인 사용, 단점: 구현하기 복잡함

 

<틀리거나 잘못된 부분을 댓글로 알려주세요!>