Stack

Stack

---

스택

• 자료를 보관할 수 있는 선형 자료구조

• 단, 넣을 때에는 한쪽 끝에서 밀어 넣어야하며 꺼낼때에도 같은 쪽에서 뽑아 꺼내야 한다.

  push & pop

• 후입선출 (LIFO - Last In First Out ) 구조

• 스택의 주요 연산은 push & pop 뿐인 간단한 자료구조이지만, 여러 가지의 알고리즘을 구현함에 있어 활용도가 높다.

  예를 들어, 프로그램 내부에서 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출 위치로 돌아가는 동작을 구현하는데도 스택이 이용된다.

스택에서 발생 가능한 오류

• 비어있는 스택에서 pop 시도 -> 스택 언더플로우
• 스택이 꽉 차있는 상태에서 push 시도 -> 스택 오버플로우

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

(1) 배열 (array) 를 이용하여 구현

-    Python 리스트와 메서드들을 이용한다.

(2) 양뱡향 연결 리스트 이용

연산의 정의

​ 1) size() - 현재 스택에 들어 있는 데이터 원소의 수

​ 2) isEmpty() - 현재 스택이 비어 있는지 판단

​ 3) push(x) - 데이터 원소 x를 스택에 추가

​ 4) pop() - 스택 최상단 데이터 원소를 제거하며 반환

​ 5) peek() - 스택 최상단 데이터 원소 반환 ( 제거 x )

스택 구현

#-*- coding: utf-8 -*-
from DoublyLinkedLists import Node
from DoublyLinkedLists import DoublyLinkedList

#배열로 구현한 스택
class ArrayStack:

    def __init__(self):             # constructor method
        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]    

# 양방향 연결리스트로 구현한 스택

class LinkedListsStack:

    def __init__(self):             # constructor method
        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

# 괄호짝 검사
def solution(expr):
    match = {
        ')' : '(',
        '}' : '{',
        ']' : '['
    }

    s = ArrayStack()
    for c in expr:
        if c in '([{':
            s.push(c)
        elif c in match:
            if s.isEmpty():
                return False
            else:
                t = s.pop()
                if t != match[c]:
                    return False
    return S.isEmpty()