스택 (Stack)

is Yoon·2023년 10월 25일

자료구조와 알고리즘

목록 보기

8/15

'쌓다'라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 선형 자료구조이다.

후입선출 구조 (LIFO, Last In First Out) : 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제
스택의 윗부분을 꼭대기 top, 아랫부분을 바닥 bottom 이라고 한다.

스택은 단 2가지 연산을 지원하는 간단한 자료 구조이다.

데이터 원소 추가 (집어넣는 동작) : 푸시 (push) 연산
마지막에 추가된 원소 참조 및 삭제 (꺼내는 동작) : 팝 (pop) 연산

스택은 생성 방식에 따라 2가지로 구분된다.

정적 스택 : 데이터 구조와 크기의 규모가 고정된 스택 (배열로 설계)
동적 스택 : 실행 중에 스택의 크기를 늘릴 수 있고, 소비하는 메모리의 양도 변하는 스택 (단방향 연결 리스트로 설계)

스택은 여러 가지의 알고리즘을 구현에 있어서 활용도가 높다.

'프로그램 실행 > 함수 호출 > 함수 리턴'하는 과정에서 마지막 호출된 곳으로 돌아가는 동작을 구현하는 데 이용
응용프로그램 작성에 유용

컴퓨터 하드웨어(프로세서)는 어떤 방식으로든 스택을 내부적으로 관리하는 기능을 갖고 있다.

스택의 동작

초기 상태 : 비어 있는 스택 (empty stack)
Stack.push(Data) 형태를 통해서 데이터를 쌓을 수 있고,
Stack.pop() 형태를 통해서 마지막에 넣은 데이터를 삭제할 수 있다.

그런데, 스택에서 2가지 오류가 발생할 수 있다.

➀ EmptyStack.pop() ⇨ 스택 언더플로우 (Stack underflow)
비어있는 스택에서 원소를 꺼내려 할 때 발생하는 에러

➁ FullStack.push(data) ⇨ 스택 오버플로우 (Stack overflow)
꽉 찬 스택에 원소를 넣으려 할 때 발생하는 에러

추상적 자료 구조로 구현하기

여러 방법이 있지만, 대표적으로 배열을 이용하거나 연결 리스트를 이용해서 스택을 추상적 자료 구조로 구현할 수 있다.

방법1. 배열을 이용하여 구현하기
방법2. 연결 리스트를 이용하여 구현하기

스택의 추상적 자료구조 구현을 위한 연산은 다음과 같다.

size() : 현재 스택에 들어 있는 데이터 원소의 수를 구함
isEmpty() : 현재 스택이 비어 있는지를 판단 (size() == 0?)
isFull() : 현재 스택이 가득 차 있는지 판단
push(x) : 데이터 원소 x 를 스택에 추가
pop() : 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)
peek() : 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList


# 방법 1. 배열로 스택의 자료구조 구현하기
class AraayStack : 
	
	def __init__(self) :  # 빈 스택 초기화
		self.data = []   

	def size(self) :   # 스택의 크기를 리턴
		return len(self.data)

	def isEmpty(self) :   # 스택이 비어있는지 판단 (T/F)
		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. (양방향/이중) 연결 리스트로 스택의 자료구조 구현하기
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

사실 파이썬에 이미 라이브러리가 존재한다.

from pythonds.basic.stack import Stack

스택의 응용

수식의 괄호 유효성 검사

# 알고리즘 설계
수식을 왼쪽부터 한 글자씩 읽어서 :
	여는 괄호를 만나면 스택에 푸시
	닫는 괄호를 만나면 : 
		스택이 비어 있으면 올바르지 않는 수식
		스택에서 pop, 쌍을 이루는 여는 괄호인지 검사
			맞지 않으면 올바르지 않은 수식
	끝까지 검사한 후, 스택이 비어 있어야 올바른 수식

후위표기법

중위 → 후위 표현식 변환 후 계산하기

# 1. 중위표현식의 요소를 반환하는 코드
def splitTokens(exprStr) : 
	tokens = []
	val = 0
	valProcessing = False
	for c in exprStr : 
		if c == ‘ ‘ :
			continue
		if c in ’0123456789’ :   # 10진수 처리
			val = val * 10 + int(c)
			valProcessing = True
		else : 
			if valProcessing : 
				tokens.append(val)
				val = 0
			valProcessing = False   # 10진수 처리 x
			tokens.append(c)
	if valProcessing :   # 마지막에 10진수 처리 중이었다면
		tokens.append(val)
	return tokens


# 2. 중위 표현식을 후위 표현식으로 변환하는 코드
from stacks import ArrayStack as Stack

def infixToPostfix(tokenList) : 
	price = {‘*’: 3, ‘/‘: 3, ‘+’: 2, ‘-‘: 2, ‘(‘: 1}
	
	opStack = Stack()
	postfixList = []

	for token in tokenList : 
		if type(token) is int : 
			pass
		elif token == ‘(‘ :
			pass
		elif token == ‘)’ :
			pass
		else : 
			pass

	while not opStack.isEmpty() :
		pass

	return postfixList


# 3. 후위 표기 수식 계산 코드
from stacks import ArrayStack as Stack

def postfixEval(tokenList) :
	valStack = Stack()

	for token in tokenList : 
		if type(token) is int :
			pass
		elif token == ‘*’ :
			pass
		elif token == ‘*’ :
			pass
		elif token == ‘*’ :
			pass
		elif token == ‘*’ :
			pass

	return valStack.pop()

def solution(expr) : 
	tokens = splitTokens(expo)
	Postfix = infixToPostfix(tokens)
	val = postfixEval(Postfix)
	return val