Exist Technote

Circular Queue란 선입선출 특성을 지니는 Queue의 일종으로, 최대 크기가 고정된 대기열이 필요할 때 사용할 수 있는 자료구조이다. 배열의 처음과 끝을 원처럼 연결한 것처럼 바라보아 요소를 넣을 지점과 꺼낼 지점에 해당하는 커서들을 이동시키며 큐로 사용하도록 구현되어 있다. 아래 구현 코드는 덮어쓰기가 불가능하도록 작성되어 있다. 그러나 일부 상황에서는 이를 허용해야 하는 상황이 생긴다. (소리 출력 버퍼가 원형 큐로 구현되어 있다고 하자. 소비자의 속도가 느릴 경우 공급자는 데이터를 덮어쓴다. 소비자는 손실된 출력 데이터를 무시하고 항상 최신 데이터를 소비한다.) 구현 from abc import ABCMeta, abstractmethod from typing import Generic, ..

Queue Queue란 선입선출(First In First Out) 특성을 지니는 자료구조를 말한다. 예로 들어 1차선 터널의 구조와 유사하다. 추상 자료형 위키피디아의 요구사항에 따라 구현되었다. 필수 Enqueue: 요소를 큐에 삽입한다. Dequeue: 요소를 큐에서 꺼낸다. 꺼낼 요소가 없는 경우 예외가 발생한다. 비필수 Peek: 요소를 꺼내지 않고 가장 앞 요소를 반환한다. 요소가 하나도 없는 경우 예외가 발생한다. Empty: 스택에 아무 요소도 포함되어있지 않으면 True, 아니면 False를 반환한다. Size: 스택에 삽입되어 있는 요소의 갯수를 반한한다. 구현 Deque 기반 구현 python에서 제공하는 deque를 활용. 아래 코드처럼, '인터페이스 변환 목적으로 감싸는 형..

Stack이란 후입선출(First In Last Out) 특성을 지니는 자료구조를 말한다. 예로 들어 프링글스 통의 형태와도 유사하며, 다른 예로는 책을 읽다가 모르는 단어가 나와 다른 책을 기존 책 위에 펼치고, 또 모르는 단어가 나와 위에 펼치는 형태로 중첩되어 쌓이는 형태를 들 수 있다. 힙 영역에서 일반적인 데이터를 저장할 때 사용되는 스택과 스택 영역 메모리에서 함수 콜 중첩 상태에서 사용되는 스택을 혼동할 수 있다. 추상 자료형 위키피디아의 요구사항에 따라 구현되었다. 필수 Push: 요소를 스택에 삽입한다. Pop: 요소를 스택에서 꺼낸다. 꺼낼 요소가 없는 경우 예외가 발생한다. 비필수 Top(or Peek): 요소를 제거하지 않고 스택 가장 위의 요소를 반환한다. 요소가 하나도 업는 경우..