3-1. 스택

1. 스택이란?

 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), 가장 최근에 저장된 값이 먼저 나간다(pop). 스택은 데이터를 순서대로 쌓아두었다가 가장 최근 데이터부터 봐야 할 때 쓰이는데 예를 들어 편집기의 되돌리기 기능(undo)이 스택의 예이다.

스택

스택의 기본 연산은 아래와 같다.

Operation	Comment
S.push(e)	Top에 새로운 요소 추가
S.pop()	- Top 요소를 반환하면서 제거 - 단, 스택이 비어 있으면 error 생성
S.top()	- Top 요소 반환 - 스택이 비어 있으면 error 생성
S.is_empty()	스택이 비어 있으면 True를 반환
len(S)	스택이 저장된 요소의 개수를 반환

 

2. 배열 기반의 스택 구현

 파이썬 리스트로 스택을 구현해보자. 간단히 객체 레퍼런스는 표기를 생략하고 데이터를 넣어서 표기한다. 리스트에선 Top이 끝에 있어야 스택 연산의 성능이 좋다.

리스트로 스택 구현하기

어댑터 패턴으로 구현할 때 이런 느낌이라고 생각하면 이해하기 쉬울 것이다.

Stack(Adaptor)	List(Adaptee)
S.push(e)	L.append(e)
S.pop()	L.pop()
S.top()	L[-1]
S.is_empty()	Len(L) == 0
len(S)	len(L)

 

3. ArrayStack 클래스

 전체 코드를 보고 함수 부분마다 다시 설명한다.

class Empty(Exception):
	"""Error attempting to access an element from an empty computer."""
pass

class ArrayStack:
	"""LIFO Stack implementation using a Python list as underlying storage."""
    
    def __init__(self):
    	"""Create an empty stack."""
        self._data = []			# nonpublic list instance
    
    def __len__(self):
    	"""Return the number of elements in the stack."""
        return len(self._data)
        
    def is_empty(self):
    	"""Return True if the stack is empty."""
        return len(self._data) == 0
        
    def push(self, e):
    	"""Add element e to the top of the stack."""
        self._data.append(e)		# new item stored at end of list
        
    def top(self):
    	"""Return (but do not remove) the element at the top of the stack.
        Raise Empty exception if the stack is empty."""
        if self.is_empty():
        	raise Empty('Stack is empty')
        return self._data[-1]		# the last item in the list
        
    def pop(self):
    	"""Remove and return the element from the top of the stack (i.e., LIFO).
        Raise Empty exception if the stack is empty."""
        if self.is_empty():
        	raise Empty('Stack is empty')
        return self._data.pop()		# remove last item from list

---

1) 클래스 선언

class Empty(Exception):
	"""Error attempting to access an element from an empty computer."""
pass

class ArrayStack:
	"""LIFO Stack implementation using a Python list as underlying storage."""

2) 초기화: self._data는 스택 데이터를 담고 있는 리스트이다. 

    def __init__(self):
    	"""Create an empty stack."""
        self._data = []			# nonpublic list instance

3) 스택에 저장된 요소 개수: 데이터가 저장된 리스트의 길이를 반환

    def __len__(self):
    	"""Return the number of elements in the stack."""
        return len(self._data)

4) 스택이 비었는지 확인: 데이터가 저장된 리스트의 길이가 0이면 True로 반환

    def is_empty(self):
    	"""Return True if the stack is empty."""
        return len(self._data) == 0

5) Push: 데이터가 저장된 리스트의 끝에 append

    def push(self, e):
    	"""Add element e to the top of the stack."""
        self._data.append(e)		# new item stored at end of list

6) Top 요소를 반환: 스택이 비어 있으면 Empty 오류 발생, 비어 있지 않으면 리스트의 마지막 요소 반환

    def top(self):
    	"""Return (but do not remove) the element at the top of the stack.
        Raise Empty exception if the stack is empty."""
        if self.is_empty():
        	raise Empty('Stack is empty')
        return self._data[-1]		# the last item in the list

7) Pop: 스택이 비어 있으면 Empty 오류 발생, 비어 있지 않으면 리스트의 마지막 요소를 pop

    def pop(self):
    	"""Remove and return the element from the top of the stack (i.e., LIFO).
        Raise Empty exception if the stack is empty."""
        if self.is_empty():
        	raise Empty('Stack is empty')
        return self._data.pop()		# remove last item from list

리스트로 스택을 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다.

Operation	Running Time(amortized)
S.push(e)	O(1)
S.pop()	O(1)
S.top()	O(1)
S.is_empty()	O(1)
len(S)	O(1)

 

4. 스택의 예: 수식에서 괄호문법 체크

 스택에 왼쪽 괄호를 넣어두고 오른쪽 괄호가 나타나면 하나씩 꺼내서 같은 쌍인지 비교한다. 왼쪽 괄호가 나타나면 스택에 push, 오른쪽 괄호가 나타나면 스택에서 pop한다.

수식에서 괄호문법 체크

전체 코드를 살펴본 후 부분으로 나누어 설명한다.

def is_matched(expr):
	"""Return True if all delimeters are properly match; False otherwise."""
    lefty = '[{('					# opening delimiters
    righty = ')}]'					# respective closing delims
    S = ArrayStack()
    for c in expr:
    	if c in lefty:
        	S.push(c)				# push left delimiter on stack
        elif c in righty:
        	if S.is_empty():
            	return False				# nothing to match with
            if righty.index(c) != lefty.index(S.pop()):
            	return False				# mismatched
     return S.is_empty()				# were all symbols matched?

---

1) 스택 생성: 괄호의 왼쪽과 오른쪽을 lefty와 righty로 설정 후 스택 생성

def is_matched(expr):
	"""Return True if all delimeters are properly match; False otherwise."""
    lefty = '[{('					# opening delimiters
    righty = ')}]'					# respective closing delims
    S = ArrayStack()

2) 왼쪽 괄호는 스택에 넣기: 수식의 문자를 하나씩 읽으면서 lefty에 해당되면 스택에 push

    for c in expr:
    	if c in lefty:
        	S.push(c)				# push left delimiter on stack

3) 오른쪽 괄호가 나오면 스택에 왼쪽 괄호를 꺼내서 비교

  - righty에 해당되면 스택에서 lefty를 pop해서 같은 괄호 쌍인지 확인(lefty와 righty의 index 순서로 비교)

  - 단, 비교 도중 스택이 비면 괄호가 매칭되지 않는 것으로 간주해 False return

        elif c in righty:
        	if S.is_empty():
            	return False				# nothing to match with
            if righty.index(c) != lefty.index(S.pop()):
            	return False				# mismatched

4) 괄호 매칭 여부 반환: 비교가 끝났는데 스택이 비지 않으면 매칭되지 않는 것으로 간주해 False Return 

     return S.is_empty()				# were all symbols matched?

 

다음 게시글에서는 큐와 덱에 대해 다룬다!