buffer, queue, heap, stack

data structure 는 언어별이라기보다 paradigm 으로 이해하기

buffer

• 데이터를 일시적으로 저장하는 임시 저장 공간

• I/O 작업의 효율적 처리에 주로 사용

• 데이터를 미리 모아서 한번에 처리, 데이터 도착/처리 속도의 차이 완화 (buffering)

• ex)

1. video streaming: 버퍼링이 되는 동안 인터넷을 통해 순차적으로 도착한 데이터를 모아서 화면에 한 번에 재생할 수 있도록 함

2. programming: 데이터를 파일에서 읽거나 쓸 때

with open('example.txt', 'r') as file:
    buffer = file.read(1024)  # 1024바이트씩 데이터를 읽어오는 버퍼

queue

• first in, first out

• 출구 따로 입구 따로: 뒤로 줄을 서고 앞에서 부터 나감

• python: collections.deque

• java: linkedList, priorityQueue

• ex)

1. call center system
2. programming: 이벤트 처리 시스템; 사용자가 버튼을 클릭하거나, 서버로부터 데이터를 받아야할 때, 이벤트 처리하기 위한 작업이 큐에 추가됨

from collections import deque

queue = deque()
queue.append("First Task")  # 큐의 끝에 데이터를 추가
queue.append("Second Task")
print(queue.popleft())      # 큐의 맨 앞에서 데이터를 꺼냄 (FIFO)

heap as priority queue

• complete binary tree

• max-heap & min-heap

• 우선순위나 정렬 알고리즘에 적합

• 스택, 큐와 다르게 heap은 우선순위에 따라 처리 순서를 결정

• 모 아니면 도, 양자택일, min 아니면 max 값에 집중

• insertion, deletion -> O(log n)

• finding min or max value -> O(1)

• ex)

1. 네트워크 패킷 처리 시스템에서 중요도가 높은 패킷을 먼저 처리하는 우선순위 큐
2. heap sort algorithm -> O(n log n)

PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(10);
heap.add(5);
heap.add(20);
System.out.println(heap.poll());  // 5가 출력됨

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
print(heapq.heappop(heap))  # 가장 작은 값인 5가 출력됨

stack

• last in, first out

• 출입구가 하나: 접시 쌓으면 맨 위부터 나감

• python: list

• ex)

1. 뒤로 가기, 취소 버튼 등은 스택에 일정 시간 동안 작업을 쌓아놓음
2. programming: recursion; 마지막에 들어온 것부터 계산해 나감

stack = []
stack.append(10)  # 스택에 데이터 추가 (push)
stack.append(20)
print(stack.pop())  # 스택에서 데이터 꺼냄 (pop), 20이 먼저 나옴 (LIFO)