11강: 스택(Stacks)

강의

"스택"은 자료를 보관할 수 있는 선형 구조입니다.

후입선출 (LIFO) 구조입니다.

 

발생 가능한 오류

• 스택 언더플로우 : 비어있는 스택에서 원소를 꺼내려는 경우
• 스택 오버플로우 : 꽉 찬 스택에 원소를 넣으려는 경우

 

구현 방법

• 배열 : python의 리스트 매소드 이용

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]

• 연결 리스트 : 양방향 연결 리스트 이용

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

 

 

연산

• size() : 데이터 원소의 수
• isEmpty() : 비어있는지 판단
• push() : 원소 추가
• pop() : 원소 제거 및 반환
• peek() : 원소 반환

 

 

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

⭐ 프로그래머스 코딩테스트 연습문제 - 올바른 괄호