연결 리스트 기반 스택 (Linked List-based Stack)

스택(Stack)은 LIFO(Last In, First Out) 구조를 가지는 자료 구조로, 마지막에 삽입된 요소가 가장 먼저 제거된다. 스택은 배열(Array) 또는 연결 리스트(Linked List)로 구현할 수 있다. 연결 리스트 기반 스택은 스택의 요소를 노드(Node)로 관리하여 동적으로 메모리를 할당한다. 이 방법은 스택의 크기가 가변적이어서 메모리 사용이 효율적이다.

연결 리스트 기반 스택의 구조

1. 노드 (Node): 스택의 각 요소를 나타내는 기본 단위로, 데이터와 다음 노드를 가리키는 포인터를 포함한다.
   • 데이터 (Data): 노드가 저장하는 값.
   • 다음 (Next): 다음 노드를 가리키는 포인터.
2. 스택 (Stack): 연결 리스트의 헤드(Top) 노드를 가리키는 포인터를 포함한다.
   • 탑 (Top): 스택의 가장 상단 노드를 가리키는 포인터.

주요 연산

1. 삽입 (Push): 스택의 가장 상단에 새로운 노드를 추가한다.
2. 삭제 (Pop): 스택의 가장 상단 노드를 제거하고 그 노드의 데이터를 반환한다.
3. 탑 (Top): 스택의 가장 상단 노드의 데이터를 반환한다. 노드를 제거하지 않는다.
4. 비어 있는지 확인 (IsEmpty): 스택이 비어 있는지 확인한다.
5. 크기 확인 (Size): 스택에 있는 노드의 개수를 반환한다.

연결 리스트 기반 스택의 장단점

장점:

1. 동적 크기 조정: 스택의 크기를 동적으로 조정할 수 있어 메모리 사용이 효율적이다.
2. 빠른 삽입과 삭제: 새로운 노드를 추가하거나 제거하는 연산이 O(1) 시간 복잡도를 가진다.

단점:

1. 추가 메모리 사용: 각 노드가 데이터 외에도 다음 노드를 가리키는 포인터를 저장해야 하므로 추가 메모리를 사용한다.
2. 임의 접근 불가: 배열 기반 스택에 비해 임의의 인덱스로 접근하는 것이 불가능하다.

주요 연산 설명

1. push: 새로운 노드를 생성하여 스택의 가장 상단에 추가한다. 기존의 top 포인터를 새로운 노드의 next 포인터로 설정하고, top 포인터를 새로운 노드로 갱신한다.
2. pop: 스택의 가장 상단 노드를 제거하고 그 노드의 데이터를 반환한다. top 포인터를 다음 노드로 갱신한다.
3. peek: 스택의 가장 상단 노드의 데이터를 반환한다. 노드를 제거하지 않는다.
4. is_empty: 스택이 비어 있는지 확인한다. top 포인터가 None이면 스택이 비어 있는 것이다.
5. size: 스택에 있는 노드의 개수를 반환한다.
6. display: 스택의 모든 노드를 순서대로 출력한다.

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.prev = None

class LinkedListBasedStack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data) -> None:
        new_data = Node(data)
        if self.is_empty():
            self.top = new_data
        else:
            new_data.prev = self.top
            self.top = new_data

        self.size += 1

    def pop(self):
        if self.is_empty():
            return None
        else:
            cur = self.top
            self.top = self.top.prev
            self.size -= 1
            return cur.data

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

    def is_empty(self) -> bool:
        return self.size == 0

    def get_size(self) -> int:
        return self.size

    def display(self) -> None:
        cur = self.top
        while True:
            if cur is None:
                print("None")
                return
            print(cur.data, "-> ", end="")
            cur = cur.prev

stack = LinkedListBasedStack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.display()  # Output: 30 -> 20 -> 10 -> None
print(stack.pop())  # Output: 30
print(stack.peek())  # Output: 20
print(stack.is_empty())  # Output: False
print(stack.get_size())  # Output: 2
stack.display()  # Output: 20 -> 10 -> None

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms