Stack (스택)

설명

스택의 특성

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
• 스택에 저장된 자료는 선형 구조를 갖음
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있음
• 마지막에 삽입한 자료를 가장 먼저 호출 - 후입선출

스택의 구현 (필요한 자료구조와 연산)

• 자료구조 : 자료를 선형으로 저장할 저장소
  • 배열 사용 가능
  • 저장소 자체를 스택이라 부름
  • 스택에서 마지막 삽입된 원소의 위치를 top이라 부름
• 연산
  • 삽입 : 저장소에 자료를 저장, 보통 push라고 칭함
  • 삭제 : 저장소에서 자료를 호출, 꺼낸 자료는 삽입한 자료의 역순, 보통 pop이라고 칭함
  • 스택이 공백인지 아닌지를 확인하는 연산 : isEmpty
  • 스택의 top에 있는 원소를 반환하는 연산, peek
• 스택의 삽입/삭제 과정

• 스택의 push 알고리즘

def push(item):
	s.append(item)

 

• 스택의 pop 알고리즘

def pop():
	if len(s) == 0:
    	# underflow
        return
    else:
    	return s.pop(-1)