[Python] 스택 구현

파이썬에서 제공하는 리스트를 사용하면 스택의 기능을 모두 사용할 수 있다. push연산은 append, pop연산은 그대로 pop을 이용하면 된다. 여기서는 노드를 이용해 스택을 구현해보려 한다.

 

구현하려는 스택의 추상 데이터 타입은 다음과 같다.

• empty() : 비었다면 True를, 아닐 경우 False를 반환
• push(item) : 스택에 item을 삽입
• pop() : 스택에 마지막으로 들어온 item을 반환, 스택이 비어있는 경우 False를 반환
• peek() : 스택에 마지막으로 들어온 item을 반환
• __len__() : 스택에 크기를 반환

 

---

1. 노드

class Node(object):
    def __init__(self, item, pointer):
        self.item = item
        self.pointer = pointer

연결리스트에서 사용된 노드와 마찬가지로 값을 저장하는 value와 다음 노드를 가리키는 pointer를 멤버로 갖는다

 

2. 스택

class Stack(object):
    def __init__(self):
        self.head = None
        self.size = 0

제일 최근에 들어온 원소를 가리키는 head와 길이를 저장하는 length를 갖는다
head는 항상 스택의 peek를 가리킨다

 

1) empty()

def empty(self):
    return not bool(self.head)

head가 존재하는 경우 False를, 존재하지 않는 경우 True를 반환한다

 

2) push(item)

def push(self, item):
    self.head = Node(item, self.head)
    self.size += 1

스택의 head를 가리키며 값을 저장하는 노드를 생성한다. head는 새로 생성된 노드를 가리키게 된다

 

3) pop()

def pop(self):
    if self.empty():
        raise IndexError('stack is empty')
    item = self.head.item
    self.head = self.head.pointer
    self.size -= 1
    return item

 

head가 가리키고 있는 노드의 값을 미리 저장한 후 head가 다음값을 가리키도록 한다.

노드는 한 쪽 방향만 가리키고 있으므로 이전 노드에는 접근할 수 없다.

스택이 비어있지 않은 경우 없앤 노드의 값을 반환하고, 스택이 비어있는 경우 False를 반환한다

 

4) peek()

def peek(self):
    if self.empty():
        raise IndexError('stack is empty')
    return self.head.item

head가 가리키고 있는 노드의 값을 반환한다. pop연산과 달리 스택의 크기는 변하지 않고 값만 반환한다

스택이 비어있는 경우 False를 반환한다

 

5) __len__()

def __len__(self):
    return self.size

스택의 크기를 반환한다

 

3. 예제 코드

if __name__ == '__main__':
    stack = Stack()
    print('stack is empty: ', stack.empty())
    stack.push(1); print('peek is', stack.peek())
    stack.push(3); print('peek is', stack.peek())
    stack.push(5); print('peek is', stack.peek())
    print('stack is empty: ', stack.empty())
    print('stack size is', len(stack))
    stack.pop(); print('peek is', stack.peek())
    stack.pop(); print('peek is', stack.peek())
    stack.pop(); print('stack is empty: ', stack.empty())
    print('peek is', stack.peek())

stack is empty:  True
peek is 1
peek is 3
peek is 5
stack is empty:  False
stack size is 3
peek is 3
peek is 1
stack is empty:  True
Traceback (most recent call last):
  File "stack.py", line 47, in <module>
    print('peek is', stack.peek())
  File "stack.py", line 29, in peek
    raise IndexError('stack is empty')
IndexError: stack is empty

 

4. 전체코드

class Node(object):
    def __init__(self, item, pointer):
        self.item = item
        self.pointer = pointer


class Stack(object):
    def __init__(self):
        self.head = None
        self.size = 0

    def empty(self):
        return not bool(self.head)

    def push(self, item):
        self.head = Node(item, self.head)
        self.size += 1

    def pop(self):
        if self.empty():
            raise IndexError('stack is empty')
        item = self.head.item
        self.head = self.head.pointer
        self.size -= 1
        return item

    def peek(self):
        if self.empty():
            raise IndexError('stack is empty')
        return self.head.item

    def __len__(self):
        return self.size


if __name__ == '__main__':
    stack = Stack()
    print('stack is empty: ', stack.empty())
    stack.push(1); print('peek is', stack.peek())
    stack.push(3); print('peek is', stack.peek())
    stack.push(5); print('peek is', stack.peek())
    print('stack is empty: ', stack.empty())
    print('stack size is', len(stack))
    stack.pop(); print('peek is', stack.peek())
    stack.pop(); print('peek is', stack.peek())
    stack.pop(); print('stack is empty: ', stack.empty())
    print('peek is', stack.peek())