이번에는 자료구조 중 특정한 문제를 풀기위한 스택(Stacks)에 대해서 알아보도록 하겠습니다!

스택(Stacks)

• 자료 (data element)를 보관할 수 있는 (선형) 구조
• 일렬로 늘어나는 구조
• 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고,
  • 푸시 (push) 연산
• 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야하는 제약 존재
  • 팝 (pop) 연산
• 후입선출(LIFO-Last-In First-Out) 특징을 가지는 선형 자료 구조

스택의 동작

(1) 초기 상태: 비어 있는 스택(empty stack)

• S = Stack()

(2) 데이터 원소 A를 스택에 추가

• S.push(A)
• S.push(B)
• A다음에 B가 존재

(3) 데이터 원소 꺼내기

• r1 = S.pop() -> B 출력
• r2 = S.pop() -> A출력

스택에서 발생하는 오류

• 스택 언더플로우(stack underflow): 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 발생
• 스택 오버플로우(stack overflow): 꽉 찬 스택에 데이터 원소를 넣으려 할 때 발생

스택의 추상적 자료구조 구현

(1) 배열 (array)을 이용하여 구현

• Python 리스트와 메서드들을 이용

(2) 연결 리스트(linked list)를 이용하여 구현

• 양방향 연결 리스트 이용

연산의 정의

• size() - 현재 스택에 들어 있는 데이터 원소의 수 계산
• isEmpty() - 현재 스택이 비어 있는지를 판단
• push(x) - 데이터 원소 x를 스택에 추가
• pop() - 스택의 맨 위에 저장된 데이터 원소를 제거 (또한, 반환)
• peek() - 스택의 맨 위에 저장된 데이터 원소를 반환 (제거하지 않음)

배열로 구현한 스택

class ArrayStack:
	def __init__(self):
    	self.data = [] # 빈 스택을 초기화
    
    def size(self):
    	return len(self.data)
    
    def isEmpty(self):
    	return self.size() == 0

	def push(self, item):
    	self.data.append(item)
    
    def pop(self):
    	return self.data.pop()
    def peek(self):
    	retrun self.data[-1]

양방향 연결 리스트로 구현한 스택

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList


class ArrayStack:

	def __init__(self):
		self.data = []

	def size(self):
		return len(self.data)

	def isEmpty(self):
		return self.size() == 0

	def push(self, item):
		self.data.append(item)

	def pop(self):
		return self.data.pop()

	def peek(self):
		return self.data[-1]


class LinkedListStack:

	def __init__(self):
		self.data = DoublyLinkedList()

	def size(self):
		return self.data.getLength()

	def isEmpty(self):
		return self.size() == 0

	def push(self, item):
		node = Node(item)
		self.data.insertAt(self.size() + 1, node)

	def pop(self):
		return self.data.popAt(self.size())

	def peek(self):
		return self.data.getAt(self.size()).data

연습문제 - 수식의 괄호 유효성 검사

올바른 수식:

• (A + B)
• {(A + B) * C}
• [(A+B)*(C+D)]

올바르지 않은 수식:

• (A + B
• A + B )
• {A * (B+C})
• [(A+B)*(C+B)}

알고리즘 설계

• 수식을 왼쪽부터 한 글자씩 읽어서:
• 여는 괄호 - ( 또는 { 또는 [ - 를 만나면 스택에 푸시
• 닫는 괄호 - ) 또는 } 또는 ] - 를 만나면:
  • 스택이 비어 있으면 올바르지 않은 수식
  • 스택에서 pop, 쌍을 이루는 여는 괄호인지 검사
    • 맞지 않으면 올바르지 않은 수식
• 끝까지 검사한 후, 스택이 비어 있어야 올바른 수식