📒 스택(Stack)

📌스택

• 자료를 보관할 수 있는 선형 구조
• 단 넣을 때는 한 쪽 끝에서 밀어 넣어야 하고 -> push 연산
• 꺼낼 때는 같은 쪽에서 뽑아 꺼내야 하는 제약이 존재 -> Pop 연산
• 후입 선출(LIFO) 특징을 가지는 선형 자료 구조

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

📌스택 구현 종류

1. 배열을 이용한 구현
   Python 리스트와 메서드들을 이용
2. 연결 리스트를 이용한 구현
   지난 강의에서 마련한 양방향 연결 리스트 이용

📌연산의 정의

1. size() -> 현재 스택에 들어 있는 데이터 원소의 수를 구함
2. isEmpty() -> 현재 스택이 비어 있는지를 판단
3. push(x) -> 데이터 원소x를 스택에 추가
4. pop() -> 스택의 맨 위에 저장된 데이터 원소를 제거 및 반환
5. peek() -> 스택의 맨 위에 저장된 데이터 원소를 반환 (제거 X)

📌배열 구현

class ArrayStack:
	def __init__(self):
		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]

📌양방향 연결 리스트 구현

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

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

📗 과제 정리
Stack 라이브러리
from pythonds.basic.stack import Stack
S = Stack()
연습문제 - 수식의 괄호 유효성 검사
알고리즘 설계 - 수식을 왼쪽부터 한 글자씩 읽어서
1. 여는 괄호를 만나면 스택에 푸시
2. 닫는 괄호를 만나면
a. 스택이 비어 있으면 올바르지 않은 수식
b. 스택에서 pop, 쌍을 이루는 여는 괄호인지 검사
-> 맞지 않으면 올바르지 않은 수식
3. 끝까지 검사한 후 스택이 비어 있어야 올바른 수식