[03-10] Stack - Linked list

1. 개요 & 알고리즘

"C로 배우는 알고리즘"^[각주:1]에서는 Stack을 배열과 Linked list로 구현하는 방법을 설명하는데, 이번글에서는 Linked list로 Stack을 구현해 봅니다. Stack은 입/출구가 하나이므로 단순 연결 리스트를 사용합니다.

2. 동작 코드

앞서 단순 연결 리스트와 관련해서 사용한 코드를 기초로 진행합니다.^[각주:2]

새로운 Node를 생성해서 linked list의 head쪽에 연결하는 push()를 아래와 같이 구현합니다. Python을 사용하므로 메모리 제한과 관련해서 특별히 고려하지 않았습니다.

def push(self, i):
    new_node = Node(i)
    new_node.key = i
    # Input to head side
    new_node.next = self.head.next
    self.head.next = new_node

    return i

Linked list의 head쪽에서 Node를 빼내오도록 pop()을 아래와 같이 구현합니다. empty case에 대해서도 고려했습니다.

def pop(self):
    # Output to head side
    t = self.head.next
    # Stack empty case
    if t == self.tail:
        return -1

    output = t.key
    self.head.next = t.next

    return output

Python이 자체적으로 메모리를 관리하므로, Stack을 지우는 경우는 단순히 head와 tail을 연결했습니다. 

def clear_stack(self):
    # Python manage memory automatically
    self.head.next = self.tail

3. 실행 코드

구현한 Stack을 사용한 예제 코드는 다음과 같습니다("C로 배우는 알고리즘" 리스트 3-10 : STACK2.C에 대응).

#main() function
if __name__ == "__main__":
    stack = Stack()

    print("Push 5, 4, 7, 8, 2, 1")
    stack.push(5)
    stack.push(4)
    stack.push(7)
    stack.push(8)
    stack.push(2)
    stack.push(1)
    stack.print_stack()

    print("Pop")
    i = stack.pop()
    stack.print_stack()
    print("Poped value is : ", i)

    # Don't test for memory full case

    print("Initialize stack")
    stack.clear_stack()
    stack.print_stack()

    print("Now stack is empty, pop")
    i = stack.pop()
    stack.print_stack()
    print("Poped value is : ", i)

4. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_10.py

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. http://steadyandslow.tistory.com/102 [본문으로]