[Data Structures & Algorithms] 03. 자료구조와 알고리즘 _ 스택

사용자 정의형 자료구조 중 스택과 큐는 비슷한 특징을 갖는 자료구조로, 배열 또는 리스트를 이용하면 쉽게 구현할 수 있다. 오늘은 스택에 대한 강의를 정리하려고 한다. 이번 정리부터는 구현하는 코드와 응용 문제도 포함되어있어서 나중에 문제 풀때 도움이 될 것 같다. 그럼 시작!!

 

스택 

 

 

목차

1. 스택

2. 구현

3. 응용 문제 : 괄호 짝 맞추기

 

 

스택 (Stack)

 

스택이란?

데이터를 쌓아 올리는 구조로, 나중에 넣은 데이터가 먼저 나오는 방식

ex) 선반에 접시를 쌓아 올림 -> 물건을 넣고 빼는 동작이 한쪽에서만 이루어짐 (맨 위 그릇 먼저 씀)

 

스택은 다른 통로들은 모두 막고 한쪽만을 열어둔 구조로써, 데이터를 넣을 수 있는 위치(열려있는 곳)를 스택상단(TOP)이라고 부름

-> 스택은 항목의 삽입과 삭제가 상단인 (TOP)에서만 이루어진다.

     스택처럼 자료를 한쪽 방향으로만 삽입, 삭제하는 방식을 후입선출 (Last-In, First-Out)이라고 한다.

    ex) 입력의 역순으로 자료를 꺼낼 때 : 되돌리기, 이전 페이지, 계산기 프로그램 수식 계산, 미로에서 출구를 찾을 때 왔던길 되돌아가기

 

데이터를 스택에 넣는 연산: push

데이터를 스택에서 꺼내는 연산: pop

스택에 항목이 하나도 없는 상태: Empty (공백 상태)

스택의 초기 용량: capacity

스택의 용량이 가득 찬 상태: Full (포화 상태)

 

오류 상황

1. 스택 오버플로우 (Stack Overflow) : 포화 상태인 스택에 새로운 요소를 삽입하는 경우

2. 스택 언더플로우 (Stack Underflow) : 공백 상태의 스택에서 팝을 실행하는 경우

 

스택의 ADT 연산

기능	스택 ADT	설명
삽입	push(X)	스택 상단에 새로운 요소 X 삽입
삭제	pop(P)	스택 상단에 있는 요소 반환 및 삭제
빈 상태 체크	isEmpty()	스택이 비어있으면 True, 그렇지 않으면 False
가득 찬 상태 체크	isFull()	스택이 가득 차있으면 True, 그렇지 않으면 False
개수	size()	스택에 있는 요소 개수 반환
출력	display()	전체 항목 화면 출력

 

구현

 

# 클래스 선언
class Stack:
	def __init__(self, capacity):
    	self.capacity = capacity
        self.array = [None] * self.capacity
        self.top = -1
        
	# 스택이 비어있는지 확인
	def isEmpty(self):
		return self.top == -1
        
	# 스택이 가득 차있는지 확인
	def isFull(self):
		return self.top == self.capacity -1
     
    # 스택에 항목 삽입
    def push(self, value):
    	if not self.isFull():
        	self.top += 1
        	self.array[self.top] = value
        else:
        	print("Stack Overflow")
            
	# 스택에서 항목 삭제
	def pop(self):
		if not self.isEmpty():
			self.top -= 1
			return self.array[self.top + 1]
		else:
			print("Stack Underflow")
            
	# 스택의 갯수 확인
	def size(self):
		return self.top + 1
        
	# 스택의 모든 항목 화면 츨력
	def display(self):
		for i in range(self.top + 1):
			print(self.array[i], " ", end="")

# 객체 생성
s1 = Stack(10)
s2 = Stack(100)

# 항목 입력
s1.push(10)
s2.push(20)
s3.push(30)

# 항목 삭제
s1.pop()
s1.pop()

s1.pop()
s1.pop()

# 항목 다시 입력
s1.push(10)
s1.push(20)
s1.push(30)

# 스택 사이즈 및 항목값 출력
s1.size()
s1.display

응용 문제 : 괄호 짝 맞추기

 

문제

입력된 수식에서 왼쪽 여는 괄호와 오른쪽 닫는 괄호의 짝이 맞는지를 체크

 

입력

( 10 + 2 ) * 5 - (( 7 - 1 ) / 2 + 9 )

-> 닫는 괄호는 가장 최근에 열린 괄호와 상쇄 -> 스택을 써야겠군!!

 

출력

괄호 짝이 맞으면 True, 괄호 짝이 맞지 않으면 False

 

과정

1. 문자열을 앞에서 하나씩 훑으면서 여는 괄호가 나오면 push

2. 닫는 괄호가 나오면 pop을 통해 문자열에서 여는 괄호와 닫는 괄호를 한 쌍씩 상쇄

3. 1~2 과정을 마지막 문자열까지 반복

4. 모든 문자열을 다 훑은 후, 스택에 괄호가 남아있지 않다면 짝이 맞는 것(True)이고, 괄호가 남아있다면 짝이 맞지 않는 것(False)으로 판단

 

코드

# 괄호 짝맞추기 체크 함수 (아래 코드보다 상단에 스택 클래스를 정의하는 코드가 있어야함)
def check_brackets(Str, length):
	s1 = Stack(length)
    for ch in str:
    	if ch == '(':
        	s1.push(ch)
        elif ch == ')':
        	if s1.isEmpty():
            	return False
        else:
        	pass
            
        return s1.isEmpty
        
# main
str = input("수식 입력: ")		# 수식입력 예: (10 + 2) * 5 - ((7 - 1) / 2 + 9)
print("괄호 짝맞추기 결과: ", check_brackets(str, len(str)))

 

이전글 & 다음글

 

2025.02.12 - [🖥️ 컴퓨터쟁이 공부] - [Data Structures & Algorithms] 02. 자료구조와 알고리즘 _ 배열과 리스트

[Data Structures & Algorithms] 02. 자료구조와 알고리즘 _ 배열과 리스트

 

2025.02.17 - [🖥️ 컴퓨터쟁이 공부] - [Data Structures & Algorithms] 04. 자료구조와 알고리즘 _ 큐

[Data Structures & Algorithms] 04. 자료구조와 알고리즘 _ 큐