[Stacks]12. Linked list-based Stack(연결 리스트 기반 스택) 구현

목차

1. Linked list-based Stack(연결 리스트 기반 스택) 구현

2. class Node, S_linked_list

3. class Stack_linked

4. 테스트

 

1. Linked list-based Stack(연결 리스트 기반 스택) 구현

 Linked list-based Stack을 구현할 경우,

1. Singly linked list를 구현한다.

2. append, pop은 모드 singly linked list의 head에서 이루어진다.

3. 이를 기반으로 스택 알고리즘을 구현한다.

 

 Singly linked list를 활용하여 스택 알고리즘을 구현할 경우, head에서 append와 pop을 진행하야한다는 사실만 주의하면 됩니다. 지난 Linked list 게시물에서도 언급했지만, tail에 새로운 element를 추가하는 것은 O(1)만에 가능하지만, tail에서 element를 제거하는 것은 tail전의 node 주소에 대한 정보가 없어 비효율적이라는 사실만 주의하면 됩니다.

 

2. class Node, S_linked_list

class Node: # class Node
    def __init__(self, data: int):
        self.data = data # 저장하는 데이터 값
        self.next = None # 다음 node의 주소값 저장

class S_linked_list:
    def __init__(self): # 선언시 head와 tail값은 None
        self.head = None
        self.tail = None
    
    def empty(self)-> bool: # 리스트가 비어있는지 확인하는 함수
        if self.head == None and self.tail == None:
            return 1 # 비어있다면 1 return
        else:
            return 0 # 비어있지 않다면 0 return
    
    def peek(self)-> int: # tail값을 반환
        if self.empty(): # 비어있다면 -1 return
            return -1
        else:
            return self.head.data
    
    def list_size(self)-> int: # 리스트의 크기를 반환하는 함수
        list_size = 1
        our_node = self.head # head에서 시작
        
        if self.empty(): # 비어있다면 0 return
            return 0
        else:
            while True:
                if our_node.next == None: # 다음 node가 없다면
                    break
                else: # 다음 node가 있다면
                    list_size += 1
                    our_node = our_node.next
            return list_size
    
    def append(self, data: int): # 연결 리스트에 node를 추가하는 함수
        node = Node(data)
        
        if self.empty(): # 리스트가 비어있다면, head와 tail 지정해주기
            self.head = node
            self.tail = node
        else: # head가 가리키는 node 변경 후 head 변경
            node.next = self.head
            self.head = node
    
    def delete(self)-> int: # head에 해당하는 node를 삭제하고, 그 node의 data 출력
        if self.empty(): # 연결 리스트가 비어있는 경우
            return -1
        elif self.list_size() == 1: # 스택에 데이터가 1개밖에 남아있지 않은 경우
            tmp = self.head.data
            self.head = self.head.next
            self.tail = None
            return tmp
        else: # head node 제거
            tmp = self.head.data
            self.head = self.head.next
            return tmp

 

3. class Stack_linked

class Stack_linked:
    def __init__(self):
        self.stack = S_linked_list() # singly linked list기반 저장
        # self.t = -1 # top index -1로 default
    
    def size(self)->int: # 스택의 크기 return
        return self.stack.list_size()
    
    def empty(self)-> bool: # 스택이 비었는지 여부 return
        return self.stack.empty()
    
    def top(self)-> int: # top에 있는 값 return
        return self.stack.peek()
    
    def push(self, n: int): # 스택에 element 삽입
        self.stack.append(n)
    
    def pop(self)-> int: # 스택에 element 삭제
        return self.stack.delete()

 

4. 테스트

if __name__ == "__main__": # 테스트 케이스
    stack = Stack_linked()
    print('made stack')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()
    
    stack.push(1)
    print('push 1')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()
    
    stack.push(2)
    stack.push(3)
    stack.push(4)
    print('push 2, 3, 4')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()
    
    print('pop')
    print(f'stack.pop: {stack.pop()}')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()

 

예상 출력:

'''
made stack
stack.empty: 1
stack.size: 0
stack.top: -1

push 1
stack.empty: 0
stack.size: 1
stack.top: 1

push 2, 3, 4
stack.empty: 0
stack.size: 4
stack.top: 4

pop
stack.pop: 4
stack.empty: 0
stack.size: 3
stack.top: 3

'''

 

전체 코드는 github에 올려두었습니다.

github.com/imgzon3/algorithm/blob/main/Stack/stack_linked_list.py

imgzon3/algorithm