Introduction

본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다.

자료구조 추가 학습

본 내용은 정리를 하던 도중 파이썬 내장 함수들 및 추가적으로 알아야 할 것들을 정리 할 겸, 쉴 겸 겸사겸사 작성해보는 포스트입니다. 위키 및 파이썬 공식문서들을 참조하여 정리한 내용입니다. 더불어 기본 개념은 16번 포스트를 참조 부탁드립니다 ㅎㅎ; 주된 참고 링크는 여기 입니다.

스택과 함께 사용되는 함수 :

아래의 개념들이 필요하다는 의미로 보시면 됩니다.

  • empty() : 스택이 비어있는지 여부를 판단합니다. 시간 복잡도 O(1)
  • size() : 스택의 사이즈를 반환합니다. 시간 복잡도 O(1)
  • top() : 스택의 가장 위의 요소의 참조를 반환합니다. 시간 복잡도 O(1)
  • push(a) : ‘a’ 라는 요소를 삽입합니다. 시간 복잡도 O(1)
  • pop() : 스택의 top 위치의 원소를 제거합니다. 제거하면서 해당 값을 반환하므로, 다른 변수 등에 저장이 가능합니다. 시간 복잡도 O(1)

구현

  • 스택을 구현하는 방법은 굉장히 다양합니다. 그 중 파이썬 라이브러리로부터 모듈그리고 데이터 구조체를 사용하는 스택의 구현에 대해서만 이야기 하겠습니다. 스택을 구현할 수 있는 방식은 :
  1. list
  2. Collections.deque
  3. queue.LifoQueue

List 를 활용한 구현 방법

stack = []

# append() 메서드는 리스트 뒤에
# 입력받은 값을 붙이는 역할을 합니다.
# 시간 복잡도 O(1)
stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack')
print(stack)

# pop() 후입선출 순서로 스택 상의
# 원소를 top 위치 부터 빼냅니다.
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

collections.deque를 사용한 구현

파이썬 스택 구현을 위해 덱 클래스를 ollections module을 통해 사용하여 구현할 수 있습니다. 덱은 리스트를 사용하는 것보다 append, pop에서 더 빠른 걸 원하른 경우 사용됩니다. 덱은 시간복잡도에서 O(1) 시간이 걸리지만, list 의 경우 O(n)의 시간 복잡도가 필요시 됩니다.

from collections import deque

stack = deque()

stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack:')
print(stack)

print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

queue module을 사용한 구현

  • Queue는 LIFO(후입선출)의 큐 기능을 포함합니다. 데이터는 queue사용하는 put() 함수를 사용하며, get() 함수로 데이터를 queue로부터 가져올 수 있습니다.
  • 이 모듈에는 사용 가능한 다양한 함수가 존재합니다.
  1. maxsize : 해당 큐에 허용되는 아이템 수
  2. empty() : 큐가 비어있으면 True, 아니면 False를 반환합니다.
  3. full() : 큐 안에 최대 사이즈로 값들이 차 있으면 True, 그렇지 않으면 False를 반환합니다. 큐가 최대 사이즈 = 0 으로 초기화되고(기본 값으로), 이 함수는 True를 절대 반환하지 않습니다.
  4. get() : 큐에서 값 하나를 제거하고 반환합니다. 큐가 비어있을 경우 값ㅇ 사용 가능해질 때까지 기다립니다.
  5. get_nowait() : get과 동일하게 작동합니다. 단 값이 존재하지 않으면 Queue를 발생시킵니다.
  6. put(item) : 큐에 값을 넣습니다. 큐가 만약 최대일 경우 빈 공간이 생길 때까지 대기 합니다.
  7. put_nowait(item): 큐에 값을 넣습니다.
  8. qsize() : 큐의 아이템 숫자를 반환합니다. 즉시 사용할 수 있는 여유 슬롯이 없으면 QueueFull을 발생시킵니다.
from queue import LifoQueue

# 스택 초기화
stack = LifoQueue(maxsize=3)

# qsize() 는 스택 안의 숫자를 보여줍니다.
print(stack.qsize())

# 요소 집어 넣기
stack.put('a')
stack.put('b')
stack.put('c')

print("Full: ", stack.full())
print("Size: ", stack.qsize())

# get() 함수는 pop 기능을 수행합니다.
print('\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())

print("\nEmpty: ", stack.empty())

sigly linked list 를 사용하여 구현하기

  • 연결 리스트는 두가지 메서드를 갖고 있습니다. addHead(item), removeHead(), 이 두 메서드는 스택을 구현하는데 적절합니다.
  1. getSize() : 스택의 원소의 길이를 반환합니다.
  2. isEmpty() : 비어있으면 True, 반대이면 False 를 반환합니다.
  3. peek() : 스택의 top의 원소를 반환합니다. 스택이 빈 경우, 예외를 발생시킵니다.
  4. push(value) : 스택의 head에 값을 넣습니다.
  5. pop() : 스택의 head에 있는 값을 반환하고 제거합니다. 스택이 비워있다면 예외를 발생시킵니다.
 Python program to demonstrate
# stack implementation using a linked list.
# node class

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


class Stack:

    # 스택을 초기화 합니다.
	# 엣지 케이스 다루기 더 쉽도록 하는 더미 노드를 사용합니다.
    def __init__(self):
        self.head = Node("head")
        self.size = 0

    # 스택의 문자열 표현
    def __str__(self):
        cur = self.head.next
        out = ""
        while cur:
            out += str(cur.value) + "->"
            cur = cur.next
        return out[:-3]

	# 현재의 스택 크기를 출력합니다.
    def getSize(self):
        return self.size

    # 스택이 비어있는 지를 확인하기
    def isEmpty(self):
        return self.size == 0

	# 스택의 top의 값을 취합니다.
    def peek(self):
		# 빈 스택에서 빼는 건지 아닌 지를 확인하는 검사를 진행합니다,
        if self.isEmpty():
            raise Exception("Peeking from an empty stack")
        return self.head.next.value

	# 스택에 값을 집어 넣습니다.
    def push(self, value):
        node = Node(value)
        node.next = self.head.next
        self.head.next = node
        self.size += 1

	# 스택으로부터 값을 제거하고 리턴합니다.
    def pop(self):
        if self.isEmpty():
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = self.head.next.next
        self.size -= 1
        return remove.value


# Driver Code
if __name__ == "__main__":
    stack = Stack()
    for i in range(1, 11):
        stack.push(i)
    print(f"Stack: {stack}")

    for _ in range(1, 6):
        remove = stack.pop()
        print(f"Pop: {remove}")
    print(f"Stack: {stack}")

🧑🏻‍💻 알고리즘 박살내기 시리즈🧑🏻‍💻