자료구조와 알고리즘with 파이썬 chapter1

1-1 스택이란?

스택은 후입선출(LIFO)의 형태로 제한되는 자료구조.

ex) A - B - C 순서대로 쌓아져 있다면 꺼낼 때는 C - B - A 순서로 나온다.

입력의 역순으로 자료를 꺼내야 할 때 사용.

스택의 연산

• push(e) : 새로운 요소 e를 스택의 맨 위에 추가
• pop( ) : 스택의 맨 위에 있는 요소를 꺼내서 반환
• isEmpty( ) : 스택이 비어 있으면 True를, 아니면 False를 반환
• isFull( ) : 스택이 가득 차 있으면 True를, 아니면 False를 반환
• peek( ) : 스택의 맨 위에 있는 항목을 삭제하지 않고 반환
• size( ) : 스택에 들어 있는 전체 요소의 수를 반환

오버플로 : 포화 상태인 스택에 새로운 요소를 삽입하면 오류 발생

언더 플로 : 공백의 상태의 스택에 pop( )나 peek( )를 호출하면 오류 발생

1-2 배열구조로 스택 구현하기

 

• array[ ] : 스택 요소들을 저장할 배열
• capacity : 스택의 최대용량. 저장할 수 있는 요소의 최대 개수(상수)
• top : 상단 요소의 위치(변수, 인덱스)

스택 초기화(공백): top = -1

포화상태 : top == capacity-1

## 스택의 공백 상태와 포화 상태 검사
def isEmpty():
	if top == -1 : return True
    else : return False
def isFull(): return top == capacity

## 스택의 삽입 연산
def push(e):
	if not isFull():
    	top += 1
        array[top] = e
    else :
    	print("stack overflow")
        exit()

## 스택의 삭제 연산
def pop() :
	if not isEmpty():
    	top -= 1
        return array[top+1]
    else :
    	print("stack underflow")
        exit()

## 스택의 peek()연산
def peek():
	if not isEmpty():
    	return array[top]
    else : 
    	print("stack underflow")
        exit()

## 문자열 역순 출력 프로그램
s = ArrayStack(100)
msg = input("문자열 입력: ")
for c in msg :
	s.push(c)
print("문자열 출력: ", end='')
while not s.isEmpty():
	print(s.pop(), end='')
print()

## 괄호 검사 프로그램
def checkBrackets(statement):
	stack = ArrayStack(100)
    for ch in statement:
    	if ch in ('{', '[', '('):
        	stack.push(ch)
        elif ch in ('}', ']', ')'):
        	if stack.isEmpty():
            	return False
            else:
            	left = stack.pop()
                if (ch == "}" and left != "{") or \ (ch == "]" and left != "[") or \ (ch == ")" and left != "(") :
                	return False
    return stack.isEmpty()

1-3 시스템 스택과 순환 호출

순환 : 함수가 자기 자신을 다시 호출 하여 문제를 해결하는 프로그래밍 기법ex) 팩토리얼 계산, 하노이탑 자료구조(이진 트리)

## 순환 구조의 팩토리얼 함수
def factorial(n):
	if n == 1:
    	return 1
    else :
    	return n * factorial(n-1)

순환 함수는 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성