알고리즘 기초 입문을 위해 공부한 DO IT! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬편을 통해 새로 알게 된 내용을 정리한다.

1. 스택(Stack)

: 데이터를 임시저장하는 자료구조(LIFO : Last In First Out)

1-1. 용어

• push : 데이터 넣는 작업
• pop : 데이터 꺼내는 작업
• bottom : stack[0]
• stack pointer(ptr) : 쌓여 있는 데이터 수 (0~len(stack))

1-2. 스택 포인터(Stack Pointer(ptr)) *

: push, pop, clear 등 대부분 메서드에 계속 사용된다. 즉, 스택의 맹점은 '스택 포인터'

[Push]
self.stack[ptr] = value
ptr+=1

[Pop]
self.ptr -=1
return self.stack[ptr] 

[Clear]
self.ptr = 0

* collections.deque

: 표준 라이브러리로 이를 사용하여 stack 구현 가능
: 맨 앞과 맨 끝 양쪽에서 데이터 삽입, 삭제가 가능하다.

2. 큐(Queue)

: 데이터를 임시저장하는 자료구조(FIFO)

2-1. 용어

• enqueue : 데이터 넣는 작업
• dequeue : 데이터 꺼내는 작업
• front : 데이터를 꺼내는 가장 앞쪽
• rear : 데이터를 넣는 가장 뒤쪽

2-2. 링 버퍼(Ring Buffer) 큐

: 일반 큐 자료구조의 dequeue는 가장 앞의 원소를 빼고 뒤의 원소들을 다 앞으로 당겨줘야해서 복잡도가 O(n)이다.
: 이를 해결하기 위해, 고리 형태의 큐(=링버퍼)를 고안했다.
: 링버퍼에서 enqueue, dequeue의 복잡도는 모두 O(1)이다.

2-3. front, rear, no *

1) Queue 초기화에 필요한 5가지 변수

1) que : 큐 배열
2) capacity
3) front, rear
: rear은 다음 인큐할 데이터를 저장하는 원소 인덱스
: 둘 다 0으로 초기화
4) no
: 큐의 데이터 개수
: front와 rear의 값이 같을 경우 큐가 비었는지 꽉 차있는지 구별하기 위해

 def __init__(self, capacity:int = 256) ->None:
    self.capacity = capacity
    self.que = [None] * capacity
    self.front = 0
    self.rear = 0
    self.no = 0

2-4. enqueue

def enque(self, value:Any) -> None:
    # 1. 꽉 차있는 지 본다
    if self.isFull():
      raise FixedQueue.Full
      
    # 2. 넣어준다
    self.que[self.rear] = value    
    
    # 3. rear, no을 올린다.
    self.rear+=1
    self.no +=1

    # 4. rear가 마지막 원소까지 도달했으면 다시 0으로!
    if self.rear == self.capacity : 
      self.rear = 0

2-5. dequeue

def deque(self) -> Any :
    # 1. 비었는 지 본다
    if self.isEmpty():
      raise FixedQueue.Empty
    
    # 2. 뺀다.
    target = self.que[self.front]
    
    # 3. front +1, no -1
    self.front +=1
    self.no -=1
    
    # 4. front가 마지막 원소에 도달하면 다시 0으로!
    if self.front == self.capacity : 
      self.front = 0
    return target

2-6. clear

def clear(self) -> None:
    self.no = self.front = self.rear = 0

* 우선순위 큐

: 인큐할 때 데이터에 우선순위를 부여하고, 디큐할 때 우선순위에 따라 데이터를 꺼낸다.
: heapq모듈에서 제공한다.