티스토리 뷰


'어서와! 자료구조와 알고리즘은 처음이지?'


스택(Stack)

✔  자료(data element)를 보관할 수 있는 선형 구조이다.

✔  데이터를 넣을 때는 한 쪽 끝에서 밀어넣어야 한다 (push 연산).

✔  데이터를 꺼낼 때에는 데이터를 밀어 넣었던 쪽과 같은 쪽에서 뽑아 꺼내야 하는 제약이 있다 (pop 연산).

✔  후입선출(LIFO, Last- In First - Out) 특징을 가진다. 

 

스택에서 발생하는 오류 

1. 비어있는 스택에서 데이터 원소를 꺼내려 하는 경우  

    ✔  스택 언더 플로우 (Stack underflow)

 

2. 꽉 찬 스택에 데이터 원소를 넣으려 할 때  

    ✔  스택 오버플로우(Stack overflow)

 

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

1. 배열(Array)을 이용하여 구현한다.

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

 

2. 연결 리스트(Linked list)를 이용하여 구현한다.

   ✔  양 방향 연결리스트 이용   

 

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

연산의 정의

1. size(): 현재 스택에 들어있는 데이터 원소의 수를 구한다.

2. isEmpty(): 현재 스택이 비어 있는지를 판단한다.

3. push(element): 데이터 원소 element를 스택에 추가한다.

4. pop(): 스택의 맨 위에 저장된 데이터 원소를 제거, 반환한다.

5. peek(): 스택의 맨 위에 저장된 데이터 원소를 반환한다. (제거하지 않음)

 

배열로 구현한 스택

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]

 

[ 문1. 수식의 괄호 유효성 검사]

알고리즘 설계

수식을 왼쪽부터 한글자 씩 읽어서,

✔  여는 괄호( '(' or '{' or '[')를 만나면 스택에 push 한다.

✔  닫는 괄호(')' or '}' or ']')를 만나면

      -  스택이 비어 있으면 올바르지 않은 수식

      -  스택에서 pop, 쌍을 이루는 여는 괄호 인지 검사(맞지 않으면 올바르지 않은 수식)

✔  끝 까지 검사한 후, 스택이 비어 있어야 올바른 수식 

 

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]

def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        
        # 여는 괄호 만나면 스택에 push()
        if c in '({[':
            S.push(c)
        
        # 닫는 괄호 만난 경우
        elif c in match:
            # 스택이 비어 있으면 올바르지 않은 수식
            if S.isEmpty():
                return False
            # 스택에서 pop, 쌍을 이루는 괄호인지 검사
            else:
                t = S.pop()

                if t != match[c]:
                    return False
    # 끝까지 검사한 후, 스택이 비어있어야 올바른 수식. 
    return S.isEmpty()
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함