📘 Stack 구현 - Linked List

🔍 Linked List 이용

- 단순 연결 리스트 이용

- 변수 top : 가장 최근에 삽입된 요소를 가리키는 변수

• 단순 연결 리스트의 head와 유사
• 초기화 : top = NULL → 공백 스택을 의미

- 가장 먼저 삽입된 요소는 마지막 노드가 됨 → linked field가  NULL

- 가장 최근에(마지막에) 삽입된 요소는 첫 번째 노드가 됨 → 단순 연결 리스트에서 첫 번째 노드로 삽입하는 연산과 동일

 

🔍 노드 구조체

 

- 항목들의 타입은 element로 정의

- Data field에 요소 값을 저장

- Link field에 이전에 삽입된 노드의 주소를 저장

 

 

 

- 스택의 마지막 요소(가장 최근에 삽입된 요소)를 나타내는 top

 

 

 

 

 

- Stack* create() 연산

# 공백 스택 생성

 

 

 

 

 

 

-  int isEmpty() 연산

# 스택이 비어 있으면 1을 반환

# 그렇지 않으면 0으로 반환

 

 

 

 

 

- int isFull() 연산

# 연결리스트로 구현 시 StackFull 상황이 발생하지 않으므로 항상 0

 

 

 

 

 

- Stack push() 연산

# 단순 연결 리스트에서 맨 처음 노드로 삽입하는 경우와 같음

 

 

 

 

 

 

 

- Stack pop() 연산

# 단순 연결 리스트에서 맨 처음 노드를 삭제하는 경우와 같음

 

 

 

 

 

 

 

 

 

 

 

 

 

- Stack peek() 연산

 

 

 

 

 

 

 

 

 

 

🔍 파이썬일 경우?

 

class StackNode:

    def __init__(self, data):

        self.data = data

        self.link = None

class LinkedStack:

    def __init__(self):

        self.top = None

    def is_empty(self):

        return self.top is None

    def push(self, element):

        new_node = StackNode(element)

        new_node.link = self.top

        self.top = new_node

    def pop(self):

        if self.is_empty():

            raise Exception("StackUnderflowError")

        else:

            popped_node = self.top

            self.top = self.top.link

            return popped_node.data

    def peek(self):

        if self.is_empty():

            raise Exception("EmptyStackError")

        else:

            return self.top.data