• 개요
• stacks.py

기본 스택

스택

: 자료 data elemet 를 보관할 수 있는 (선형) 구조

• 단 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 ➡️ 푸시 push 연산
• 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음 ➡️ 팝 pop 연산
• 후입선출 LIFO (Last-In First-Out) 특징을 가지는 선형 자료구조
• 동작
  • 초기 상태 : 비어 있는 스택 empty stack S = Stack()
  • 데이터 원소 A를 스택에 추가 S.push(A)
  • 데이터 원소 B를 스택에 추가 S.push(B) 그림
  • 데이터 원소 꺼내기 r1 = S.pop() → A
  • 데이터 원소 또 꺼내기 r2 = S.pop() → B
• 오류 2가지

  • 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 r3 = S.pop()

    ➡️ 스택 언더플로우 stack underflow

  • 꽉 찬 스택에 데이터 원소를 넣으려 할 때 그림

    ➡️ 스택 오버플로우 stack overflow

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

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

1. 배열 array을 이용하여 구현

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

   class ArrayStack:
   
   	def __init__(self): # Constructor Method
   			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] # 스택의 꼭대기 원소 반환
   

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

   • 양방향 연결 리스트 이용

   from doublylinkedlist import Node
   from doublylinkedlist import DoublyLinkedList
   
   class LinkedListStack:
   
   	def __init__(self):
   		self.data = DoublyLinkedList() # 비어있는 dl로 초기화
   
   	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
   

3. 라이브러리

   from pythonds.basic.stack import Stack
   S = Stack() # Stack 초기화
   dir(S) # method 보기 
   

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

• 올바른 수식:

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

• 올바르지 않은 수식:

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

• 알고리즘 설계 - 수식을 왼쪽부터 한 글자씩 읽어서:

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

• 문제 설명