자료 구조에 대해 계속 배우고 있는데, 기존에 배웠던 list, set, tuple, dictionary와는 다른 개념이라 추가 정리한다.

게시물 링크(private stackoverflow)를 기반으로 정리했고, 검색하면서 살을 조금 붙였다.

1. Stack

설거지한 접시를 하나 하나 쌓아올리는 것, 혹은 팬케이크를 차곡 차곡 쌓는 것을 상상하면 쉽다. 특징은 다음과 같다.

• LIFO(Last In First Out)
• 마지막으로 저장한 데이터가 처음으로 읽힌다.

데이타 입/출력이 한쪽으로만 접근 할 수 있는 자료 구조라고 한 것이 조금 더 이해를 도운 것 같다. 아래 이미지는 링크에서 가져왔는데, 무려 13년전 게시물이다;;;;

1.1 method

• push: 데이터 저장
• pop: 데이터를 읽어들이기. 다만 읽어들임과 동시에 stack에서 삭제한다.

아래는 class에서 리스트를 만들어서 stack이 어떻게 작동하는지를 설명해주는 코드다. 파이썬에는 내장 자료형 중에 하나인 리스트형이 스택을 표현하는데 사용돼서, 스택을 따로 구현할 필요가 없다고 한다.

 class Stack:
   def __init__(self):
     self._stack = []

   # append method를 통해 넣는 순서 대로 저장하는 함수. 마지막이 가장 최신 @ 
   def push(self, data):
     self._stack.append(data)
     
   # 마지막 데이터를 변수에 넣고 삭제하는 함수
   def pop(self):
     if len(self._stack) == 0:
       return None

     data = self._stack[-1]
     del self._stack[-1]

     return data

   # 제일 위에 있는 값(=최신값)은 맨 마지막에 있는 값이에요! 
   def peek(self):
     if len(self._stack) == 0:
       return None
 
     data = self._stack[-1]

     return data

1.2 When to use

프로그램에서 함수 호출 기록을 stack으로 저장한다 그래서 StackOverflow 에러가 있는 것이다. Web browser 내역 혹은 최신 내역이 먼저 나와야 하는 경우 사용하게 된다.

2. Queue

Queue는 Stack과 반대로 생각하면 된다.

• FIFO(First In First Out)
• 먼저 push 된게 먼저 pop 된다.

스택은 데이타가 입/출력하는 부분이 한 부분밖에 없다고 한다면, 큐는 양쪽이 뚫려있다. 한쪽으로는 데이타를 넣기(put)만 하고, 다른쪽에서는 데이타를 빼내기만(get) 한다.

2.1 method

method는 stack과 동일하게 push, pop 두 가지 메소드가 있다. 리스트를 통해 queue가 어떻게 작동하는지 보여주는 코드는 다음과 같다.

class Queue:
    def __init__(self):
        self._queue = []

    # 데이터를 순서대로 넣는 함수
    def push(self, data):
        return self._queue.append(data)

    # 처음에 넣은(배열 맨 마지막에 있는) 요소를 제거하는 함수
    def pop(self)
        if len(self._queue) == 0:
            return None

        return self._queue.pop()

    # 제일 위에 있는 값(=최신값)은 첫 번째 인덱스예요! 
    def peek(self):
        if len(self._queue) == 0:
            return None

        return self[0]

데이터를 계속 앞에다가 밀어 넣기 때문에, pop method처럼 마지막에 있는 요소를 return하면서 제거한다.

2.2 When to use

맛집 예약 시스템
OS 프로세스 스케쥴링 시스템 (priority queue 사용)

2.3 queue의 종류

일반적인 queue 말고도 double ended queue, priority queue 등도 있다.

- double ended queue

덱(deque, "deck"과 발음이 같음 ←double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

- priority queue

우선순위 큐는 최대 우선순위 큐와 최소 우선순위 큐 두 가지로 나뉜다. 우선순위가 가장 높은, 혹은 가장 낮은 데이터가 가장 먼저 나오는 구조로 보면 될 것 같다.

우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소힙을 구성해 찾아내는 형식이다. 힙은 데이터에서 최대값(혹은 최소값을) 빠르게 찾을 수 있는 자료구조라고 한다.
요거는 코드카타를 풀면서 더 정리하고, 시간 있을 때 maze 만들기 코드를 짜서 내용을 추가하면 좋을 것 같다!