Algorithm_07

Stack

---

Stack의 특성

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조이다.
• 스택에 저장된 자료는 선형 구조를 갖는다.
  • 선형구조 : 자료 간의 관계가 1대1의 관계를 갖는다.
  • 비선형구조 : 자료 간의 관계가 1대N의 관계를 갖는다
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다.

구현시 필요한 자료구조와 연산

• 자료구조 : 자료를 선형으로 저장할 저장소
  • 배열을 사용할 수 있다.
  • 저장소 자체를 스택이라 부르기로 한다.
  • 스택에서 마지막 삽입된 원소의 위치를 top이라 부른다.
• 연산
  • 삽입 : 저장소에 자료를 저장한다. 보통 push라고 부른다.
  • 삭제 : 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다.
  • 스택이 공백인지 아닌지 확인 : isEmpty
  • 스택의 top에 있는 item을 반환하는 연산 : peek

삽입 삭제 과정

[출처] https://velog.io/@ehddnr7355/%EC%8A%A4%ED%83%9DStack-%ED%81%90Queue

스택의 push 알고리즘

• append 메소드를 통해 리스트의 마지막에 데이터 삽입

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

def push(item, size):
	global top
    top += 1
    if top == size:
    	print('overflow')
	else:
    	stack[top] = item
size = 10
stack = [0] * size
top = -1
push(10,size)
top += 1		# push(20)
stack[top] = 20 

스택의 pop 알고리즘

def pop():
	if len(s) == 0:
    	return
    else:
    	return s.pop()

def pop():
	global top
	if top == -1:
    	print('underflow')
        return 0
    else:
    	top -= 1
    	return stack[top+1]
print(pop())

if top > -1:
	top -= 1
    print(stack[top+1])

Function call

• 프로그램 에서의 함수 호출과 복귀에 따른 수행 순서를 관리
  • 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행순서 관리
  • 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입
  • 함수의 실행이 끝나면 시스템 스택의 top 원소를 삭제하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀
  • 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

재귀호출

• 필요한 함수가 자신과 같은 경우 자신을 다시 호출하는 구조
• 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성

Memoization

• 재귀함수는 엄청난 중복호출이 존재한다.
• 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
• 메모이제이션은 이전에 계산한 값을 저장하여 중복 계산을 피하는 기법이다.
• 주로 재귀 함수를 통해 구현되며, 함수가 호출될 때마다 이전에 계산된 값을 저장하고, 동일한 입력에 대한 결과가 이미 저장되어 있는지 확인한다. 이미 계산된 값이 있으면 저장된 값을 반환하고, 없으면 계산을 수행하고 결과를 저장한다.