[자료구조] 스택 구현 : 연결리스트 이용 방법

 

스택을 구현하기 위해서는 이전 포스팅에서 다루었던, 배열을 이용하는 방법과 연결리스트를 이용하는 방법이 있다.

연결리스트는 단순 연결 리스트를 이용하여 진행한다.

 

단순 연결리스트에서 변수의 top은 가장 최근에 삽입된 요소를 가리키는 변수가 된다. (head와 유사) 초기화시에는 top= NULL로 설정하는데, 이는 공백 스택을 의미한다.

 

스택에서 가장 먼저 삽입된 요소는 마지막 노드가 되므로(스택의 특징) link field를 NULL로 설정하여야 한다. 그리고 가장 최근에 삽입된 요소는 첫번째 노드가 된다. 이는 단순 연결리스트에서 첫 번째 노드로 삽입하는 연산과 동일하다.

 

[스택 구현: 연결리스트 이용 방법 by 재민]

 

#스택 구현: 연결 리스트 이용 by 재민

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

class Stack:
    def __init__(self):
        self.top = None

    def is_empty(self):
        return self.top is None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            return None
        popped_data = self.top.data
        self.top = self.top.next
        return popped_data

    def peek(self):
        if self.is_empty():
            return None
        return self.top.data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" ")
            current = current.next
        print()

# 스택 테스트
stack = Stack()

print("Is the stack empty?", stack.is_empty())

stack.push(1)
stack.push(2)
stack.push(3)

print("Top of the stack:", stack.peek())
print("Is the stack empty?", stack.is_empty())

print("Stack elements:")
stack.display()

print("Popped element:", stack.pop())
print("Stack elements after pop:")
stack.display()