[자료구조와 알고리즘 with 파이썬] 01 스택

01-1 스택이란?
01-2 배열 구조로 스택 구현하기
01-3 스택의 응용: 괄호 검사
01-4 파이썬에서 스택 사용하기
01-5 시스템 스택과 순환 호출

---

01-1 스택이란?

스택

• 마지막에 들어간 자료가 가장 먼저 나오는 자료구조
• 후입선출(LIFO: Last-In First-Out)의 형태로 제한되는 자료구조

상단(stack top)

• 다른 통로들은 막고 한쪽만을 열어둔 구조

요소(element)

• 스택에 저장되는 것
• 항목이라고도 함

[그림]

스택의 활용

예) 웹 브라우저의 [이전 페이지로 이동]

• 입력의 역순으로 자료를 꺼내야 할 떄 사용됨
• undo, 웹 브라우저의 [이전 페이지로 이동]

추상 자료형

추상화

• 새로운 자료형을 정의하기 위해, 그 자료형의 자세하고 복잡한 내용 대신에 필수적이고 중요한 특징만 골라서 단순화시키는 작업

추상 자료형

• 추상화를 통해 정의한 자료형
• 예) 스택의 추상 자료형
  • 스택이 어떤 자료를 다루고, 어떤 연산이 필요한지를 정의해 보는 것

자료형 확인 함수 type()

• 현재 변수에 저장된 값의 자료형을 출력하는 함수

스택의 연산

스택의 연산 (* 스택의 상태를 변환시키는 함수)

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

오버플로(overflow)

• 포화 상태인 스택에 새로운 요소를 삽입하는 경우
• 입력이 더 이상 불가능하므로 오류가 발생함

언더플로(underflow)

• 공백 상태의 스택에서 pop()이나 peek()을 호출하면 삭제나 참조가 불가능

[그림]

Quiz

1. 10, 20
2. 4
3. 3
4. 발생하지 않음

---

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

자료구조의 구현 방법들

배열 구조

• 자료들을 배열에 모아 저장하는 방법
• 모든 요소는 인접한 메모리 공간에 저장됨
• 메모리 공간이 가득차면 더는 저장할 수 없음

연결된 구조

• 흩어져 있는 요소들을 연결하여 하나로 관리하는 방법
• 배열 구조보다 유연하게 사용할 수 있음
• 관리하기 복잡함

리스트(list)와 튜플(tuple)을 이용할 수 있음
배열의 원소들을 변결할 수 있어야 하므로 리스트 사용

배열 구조의 스택을 위한 데이터

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

배열

• 요소들을 저장할 공간

용량(capacity)

• 한번 만들어지고 나면 고정되는 상수

top

• 인덱스를 저장하는 변수, 가장 최근에 삽입된 요소의 위치

capacity = 10           # 스택 용량: 예) 용량을 10으로 지정
array = [None]*capacity # 요소 배열 : [None, ..., None] (길이가 capacity)
top = -1                # 상단의 인덱스: 공백 상태(-1)로 초기화함

* 연산자를 이용해 같은 값을 나열하는 리스트 만들 수 있음

스택의 연산

공백 상태와 포화 상태를 검사하는 isEmpty()와 isFull() 연산

[그림]

def isEmpty():
   if top == -1: return True           # 공백이면 True 반환
   else: return False                  # 아니면 False 반환
   
def isFull(): return top == capacity-1 # 비교 연산 결과를 바로 반환

새로운 요소 e를 삽입하는 push(e) 연산

def push(e):
   # global top
   if not isFull():             # 포화 상태가 아닌 경우
      top += 1                  # top 증가
      array[top] = e            # top 위치에 e 복사
   else:                        # 포화 상태: overflow
   	  print("stack overflow")
      exit()

상단 요소를 삭제하는 pop() 연산

def pop():
   # global top
   if not isEmpty():          # 공백 상태가 아닌 경우
      top -= 1                # top 감소 (global top 선언 필요) 
      return array[top+1]     # 이전(top+1) 위치의 요소 반환
   else:                      # 공백 상태: underflow
      print("stack underflow")
      exit()

상단 요소를 들여다보는 peek() 연산

def peek():
   if not isEmpty():     # 공백 상태가 아닌 경우
      return array[top]
   else: pass            # underflow 예외는 처리하지 않았음

현재 스택 요소의 수를 반환하는 size() 연산

def size(): return top+1 # 현재 요소의 수는 top+1

전역 변수와 함수 구현 방법의 문제

1. top을 전역 변수로 인식하지 못해 생기는 문제
   • top을 전역 변수로 선언하는 global top 문장을 각 함수에 추가하여 간단히 해결할 수 있음
2. 여러 개의 스택이 동시에 필요한 문제에 사용할 수 없음

스택을 클래스로 구현

• 자료구조는 객체 지향 프로그래밍 기법으로 구현하는 것이 좋음

클래스의 선언과 멤버변수 초기화

class ArrayStack:
   def __init__(self, capacity):
      self.capacity = capacity           # 스택 용량
      self.array = [None]*self.capacity  # 요소 배열
      self.top = -1                      # 상단의 인덱스

생성자

• 클래스의 객체가 만들어질 때마다 자동으로 호출되는 함수
• 멤버함수의 첫 번째 매개변수로 스택 객체 자신을 나타내는 'self'를 넣음

def isEmpty(self): return self.top == -1
def isFull(self): return self.top == self.capacity-1 

def push(self, item):
   if not self.isFull():             
      self.top += 1                  
      self.array[top] = item           
   else: pass                 
   	  
def pop(self):
   if not self.isEmpty():          
      self.top -= 1               
      return self.array[top+1]     
   else: pass
   
def peek(self):
   if not self.isEmpty(): 
      return self.array[self.top]
   else: pass
   
def size(): return self.top+1 

스택 클래스의 사용

문자열 역순 출력 프로그램

s = ArrayStack(100)

msg = input('문자열 입력: ')
for c in msg:
   s.push(c)
   
print("문자열 출력: ", end='')
while not s.isEmpty():
   print(s.pop(), end='')
print()

Quiz

1. 5
2. 세요. 반갑습니다.

---

01-3 스택의 응용: 괄호 검사

괄호 검사 문제

소스코드나 주어진 문자열에서 괄호들이 올바르게 사용되었는지를 검사하는 문제

• 조건 1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 합니다.
• 조건 2: 같은 종류인 경우 왼쪽 괄호가 오른쪽보다 먼저 나와야 합니다.
• 조건 3: 다른 종류의 괄호 쌍이 서로 교차하면 안됩니다.

괄호 검사 알고리즘

• 빈 스택을 준비함
• 입력된 문자를 하나씩 읽어 왼쪽 괄호를 만나면 스택에 삽입
• 오른쪽 괄호를 만나면 가장 최근에 삽입된 괄호를 스택에서 꺼냄
• 스택이 비었다면 오른쪽 괄호가 먼저 나온 상황이므로 조건 2 위배
• 꺼낸 괄호가 오른쪽 괄호와 짝이 맞지 않으면 조건 3 위배
• 입력 문자열을 끝까지 처리했는데 스택에 괄호가 남아 있으면 괄호의 개수가 맞지 않으므로 조건 1 위배
• 모든 문자를 처리하고 스택이 공백 상태이면 검사 성공

괄호 검사 프로그램

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()

Quiz

1. 빈 스택이어야 함
2. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같지 않은 상황임

---

01-4 파이썬에서 스택 사용하기

파이썬 리스트를 스택으로 사용하기

push() - L.append(e)
pop() - L.pop()
size() - len(L)
isEmpty() - len(L)==0
isFull() - False
peek() - L[len(L)-1] or L[-1]

문자열 역순 출력(파이썬 리스트 이용)

s = list()

msg = input("문자열 입력: ")
for c in msg:
	s.append(c)

print("문자열 출력: ", end='')
while len(s) > 0:
	print(s.pop(), end='')
print()

queue 모듈의 LifoQueue 사용하기

• queue 모듈(module)에서 큐(Queue)나 스택(LifoQueue), 우선순위 큐(PriorityQueue) 등을 클래스로 제공함

import queue

s = queue.LifoQueue(maxsize=20)

push(), pop() - put(), get()
isEmpty(), isFull() - empty(), full()
peek() - 제공하지 않음

문자열 역순 출력(LifoQueue 이용)

s = queue.LifoQueue(maxsize=100)

msg = input("문자열 입력: ")
for c in msg:
	s.put(c)

print("문자열 출력: ", end='')
while not s.empty():
	print(s.get(), end='')
print()

• 모듈(module): 함수나 객체 또는 클래스를 모아 놓은 파일을 말함

Quiz

1. push() - L.insert(0, e)
   pop() - L.pop(0)

---

01-5 시스템 스택과 순환 호출

순환이란?

순환

• 어떤 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 방법
• 예) 팩토리얼 계산, 하노이 탑, 이진 트리

팩토리얼의 두 가지 구현

반복 구조의 팩토리얼 함수

def factorial_iter(n):
	result = 1
    for k in range(2, n+1):
    	result = result * k
    return result

순환 구조의 팩토리얼 함수

def factorial(n):
	if n == 1:
    	return 1                # 순환 호출을 멈추는 부분이 반드시 있어야 함
    else:
    	return n*factorial(n-1) # 문제의 크기는 작아져야 함

순환적인 팩토리얼 함수 동작의 이해

[그림]

• 순환 함수는 대부분 반복 구조로 구현 가능
• 함수 호출에 의한 부담이 있고 시스템 스택을 많이 사용해 반복보다 느림
• 특정한 문제에 대해 반복보다 명확하고 간결한 코딩 가능
• 효율적이고 유명한 알고리즘에 흔히 사용됨

하노이의 탑

막대 A에 쌓여 있는 n개의 원판을 모두 C로 옮기는 문제입니다.
단, 다음과 같은 조건을 만족해야합니다.

• 한 번에 하나의 원판만 옮길 수 있습니다.
• 맨 위에 있는 원판만 옮길 수 있습니다.
• 크기가 작은 원판 위에 큰 원판을 쌓을 수 없습니다.
• 중간 막대 B를 임시 막대로 사용할 수 있지만 앞의 조건을 지켜야 합니다.

def hanoi_tower(n, fr, tmp, to):
	if (n==1):
    	print("원판 1: %s --> %s" % (fr, to))
    else:
    	hanoi_tower(n-1, fr, to, tmp)
        print("원판 %d: %s --> %s" % (n, fr, to))
        hanoi_tower(n-1, tmp, fr, to)

Quiz

1. 문제의 크기는 작아져야하는데 그렇지 못하기 때문에 끊임없이 반복문이 진행된다
2. 4
3. 2

---

연습문제

01

push -> A, D, C, B
pop -> B, C, D, A

02

def clear(self):
	self.top = -1

03

def display(self):
    print(*self.items)

04

for (i=1; i<10; i++) a[i] = a[(i+1)];
a { b [ ( c + d ) - e ] * f }

05

0, 9, 18

06

def printReserve(msg, len):
	li = ''
    for i in range(len):
    	li.append(msg[i])
    for i in range(len):
    	print(li.pop(), end='')
instr = "자료구조"
printReserve(instr, len(instr))