---

스택

가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료구조.

스택 메모리는 자동으로 할당되고 해제된다. 함수가 호출될 때 메모리가 할당되고, 함수가 종료될 때 메모리가 해제되는 방식으로 메모리 누수를 방지한다.
스택의 메모리 접근은 매우 빠르다. 이는 스택이 연속적인 메모리 블록을 사용하고, 스택 포인터를 사용하여 데이터에 접근하기 때문.

• 참고
  파이썬의 리스트는 메모리가 동적할당되는 배열로 구현되어있어 크기가 고정되어있지 않고 필요에따라 자동으로 크기 조정하므로 스택오버플로우 발생 x

삽입, 삭제 : O(1)
탐색 : O(n)

ex)

stack = []
stack.append(1)  # push 1
stack.append(2)  # push 2
stack.append(3)  # push 3
print(stack.pop())  # pop, 출력: 3
print(stack.pop())  # pop, 출력: 2
print(stack[-1])    # peek, 출력: 1
print(stack.pop())  # pop, 출력: 1
print(stack)       # 출력: []

push(append), pop 연산은 O(1)의 시간복잡도
주로 배열이나 연결리스트로 구현.

사용사례

• 재귀적인 함수, 알고리즘

  • 각 함수 호출이 스택 프레임을 차지하고 함수가 종료되면 해당 프레임이 제거된다.

• 웹 브라우저의 뒤로가기 기능

  • 사용자가 A,B,C 순으로 방문 했다고 가정하자. 뒤로 가기 버튼을 누르면 C -> B -> A 로 이동한다. 방문한 페이지들이 스택에 푸시되고, 뒤로가기 버튼을 누를 때 마다 스택에서 pop하여 이전 페이지로 돌아간다.

• 문자열 역순 처리

  • "hello" 라는 문자열을 거꾸로 만드는 상황을 가정하자.
    각 문자를 스택에 푸시한 후, 스택에서 팝하여 새로운 문자열을 구성하면 역순이 된다.

큐

먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료구조이며, 나중에 집어넣으 데이터가 먼저 나오는 스택과는 반대되는 개념을 가진다.
CPU작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다.

큐는 고정된 크기일 수도 있고 가변 크기일 수도 있다. 배연 기반 큐는 크기가 고정되며, 크기를 넘어서면 재할당이 필요하다. 연결리스트 기반 큐는 필요에 따라 동적으로 메모리가 할당된다.

연결리스트 기반 큐는 각 노드가 개별적으로 할당되고 해제되므로 메모리 누수에 주의해야한다. 크기 제한이 없지만 포인터를 따라가야 하므로 메모리 접근이 느릴 수 있다.
ex) 파이썬 queue 모듈의 Queue 클래스.

import queue

# 큐 생성
q = queue.Queue()

# 큐에 요소 추가 (enqueue)
q.put('a')
q.put('b')
q.put('c')

print(f"큐 크기: {q.qsize()}")

# 큐에서 요소 제거 (dequeue)
first_item = q.get()
print(f"제거된 요소: {first_item}")
print(f"큐 크기: {q.qsize()}")

# 결과:
# 큐 크기: 3
# 제거된 요소: a
# 큐 크기: 2

배열기반 큐는 메모리 블록이 한 번에 할당되므로 관리가 더 간단할 수 있다.
인덱스를 사용하여 데이터에 빠르게 접근가능하지만 크기를 넘어서면 재할당 필요.
ex) 파이썬 collentions 모듈의 deque (double-ended queue)클래스

삽입,삭제 : O(1)
탐색 : O(n)

ex)

from collections import deque

queue = deque()
queue.append(1)  # enqueue 1
queue.append(2)  # enqueue 2
queue.append(3)  # enqueue 3
print(queue.popleft())  # dequeue, 출력: 1
print(queue.popleft())  # dequeue, 출력: 2
print(queue[0])         # peek, 출력: 3
print(queue.popleft())  # dequeue, 출력: 3
print(queue)            # 출력: deque([])

enqueue(삽입), dequeue(삭제) 연산은 O(1)의 시간복잡도.
주로 배열, 연결리스트, 또는 이중 연결리스트(deque)로 구현.

사용사례

• 프린터 대기열
  • 여러 사용자가 동시에 프린터 인쇄작업을 요청한다고 가정하자.
    인쇄 작업이 도착하는 순서대로 큐에 추가되고, 프린터는 가장 먼저 도착한 작업부터 순서대로 처리한다.
• CPU 작업 스케줄링
  • 운영체제가 여러 프로세스를 순서대로 처리할 때 각 프로세스는 큐에 저장되고 CPU는 큐에서 프로세스를 하나씩 꺼내서 처리한다. 처리 완료 후 다음 프로세스를 큐에서 꺼낸다.
• 너비우선탐색(BFS) 알고리즘
  • 그래프의 모든 노드를 레벨 순서대로 탐색하는 상황을 가정하자.
    시작 노들르 큐에 넣고, 큐에서 노드를 하나씩 꺼내서 해당 노드의 인접 노드를 큐에 추가하는 방식으로 탐색한다. 큐를 사용함으로써 먼저 방문한 노드를 먼저 처리할 수 있다.
• 데이터 스트리밍
  • 실시간으로 데이터가 생성되고 이를 순서대로 처리하는 경우를 가정하자.
    생성된 데이터는 큐에 저장되고, 처리기는 큐에서 데이터를 하나씩 꺼내서 순서대로 처리한다. 예를들어 네트워크 패킷처리, 실시간 로그 수집 등의 작업이 있다.

결론

이와같이 스택과 큐는 각각의 고유한 특성과 용도를 가지며, 특정한 문제 해결에 적합한 방식으로 설계되었다. 두 자료구조의 차이점을 이해해서 다양한 문제를 더 효과적으로 해결해보자.