파이썬으로 연결 리스트 기반 스택(Stack) 구현하기

스택(Stack)은 LIFO(Last In, First Out, 후입선출) 방식으로 데이터를 저장하고 꺼내는 대표적인 자료구조입니다. 연결 리스트(Linked List)를 이용해 스택을 구현할 때는 새로운 요소를 추가하는 push 메서드와 맨 위의 요소를 제거하는 pop 메서드를 정의하게 됩니다.

배열 기반 구현과 달리 연결 리스트로 스택을 만들면 미리 크기를 정해 둘 필요가 없으며, 삽입과 삭제가 항상 헤드(head)에서 일어나므로 두 연산 모두 O(1)의 시간 복잡도를 유지할 수 있다는 장점이 있습니다.

예제 코드

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack_structure:
    def __init__(self):
        self.head = None

    def push_val(self, data):
        if self.head is None:
            self.head = Node(data)
        else:
            newNode = Node(data)
            newNode.next = self.head
            self.head = newNode

    def pop_val(self):
        if self.head is None:
            return None
        else:
            del_Val = self.head.data
            self.head = self.head.next
            return del_Val

my_instance = Stack_structure()
while True:
    print('push <value>')
    print('pop')
    print('quit')
    my_input = input('What action would you like to perform ? ').split()

    operation = my_input[0].strip().lower()
    if operation == 'push':
        my_instance.push_val(int(my_input[1]))
    elif operation == 'pop':
        del_Val = my_instance.pop_val()
        if del_Val is None:
            print('The stack is empty.')
        else:
            print('The deleted value is : ', int(del_Val))
    elif operation == 'quit':
        break

실행 결과

push <value>
pop
quit
What action would you like to perform ? push 56
push <value>
pop
quit
What action would you like to perform ? push 78
push <value>
pop
quit
What action would you like to perform ? push 90
push <value>
pop
quit
What action would you like to perform ? pop
The deleted value is : 90
push <value>
pop
quit
What action would you like to perform ? quit

코드 설명

저장할 데이터와 다음 노드를 가리키는 참조를 담는 Node 클래스를 정의합니다.
스택에 필요한 속성을 갖춘 Stack_structure 클래스를 정의합니다.
__init__ 함수는 스택의 시작점인 head를 None으로 초기화합니다.
push_val 메서드는 전달받은 값을 스택의 맨 위에 추가합니다. 헤드가 비어 있으면 새 노드가 헤드가 되고, 그렇지 않으면 새 노드의 next가 기존 헤드를 가리킨 뒤 헤드가 새 노드로 교체됩니다.
pop_val 메서드는 스택이 비어 있으면 None을 반환하고, 그렇지 않으면 헤드의 값을 꺼낸 뒤 헤드를 다음 노드로 이동시켜 삭제된 값을 반환합니다.
Stack_structure 클래스의 인스턴스를 생성합니다.
사용자에게 'push', 'pop', 'quit' 세 가지 옵션을 제공합니다.
'push' 옵션은 입력한 값을 스택에 추가합니다.
'pop' 옵션은 스택의 최상단 요소를 삭제하고 그 값을 출력하며, 스택이 비어 있으면 안내 메시지를 표시합니다.
'quit' 옵션은 반복문을 종료하여 프로그램을 마칩니다.
사용자의 입력과 선택에 따라 각각의 연산이 수행되며, 그 결과가 콘솔에 출력됩니다.

위 예제에서 56, 78, 90 순서로 값을 넣은 뒤 pop을 실행하면 가장 마지막에 넣은 90이 먼저 반환됩니다. 이것이 바로 스택의 핵심 특성인 LIFO(후입선출) 방식이며, 연결 리스트의 헤드만 조작하면 되기 때문에 push와 pop 연산 모두 매우 효율적으로 처리됩니다.

파이썬으로 연결 리스트 기반 스택(Stack) 구현하기 – 예제 코드와 상세 설명

예제 코드

실행 결과

코드 설명