[자료구조] Stack과 Queue? (특징, 사용 사례, 예시)

 

Stack(스택)

스택(Stack)은 컴퓨터 과학에서 너리 사용되는 기본적인 자료구조 중 하나입니다. 스택은 데이터를 일시적으로 저장하기 위한 선형 구조로, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 '후입선출'(LIFO, Last In First Out)의 특성을 가지고 있습니다. 이러한 특성 때문에 스택은 데이터의 역순 저장, 실행 취소 기능 등에 유용하게 사용됩니다.

 

 

특징

• 후입선출(LIFO) 특성: 스택에 데이터를 추가하거나 제거할 때, 항상 스택의 맨 위에서만 작업이 이루어집니다. 이는 책을 쌓아 올린 후 가장 위에 있는 책을 먼저 꺼내는 것과 유사합니다.
• 용도: 스택은 프로그램에서 함수 호출과 반환 주소를 관리하는 데 사용되며, 괄호 검사, 역순 문자열 생성, 웹 브라우저의 뒤로 가기 기능 구현 등 다양한 알고리즘과 시스템에서 활용됩니다.
• 주요 연산
  • push: 스택의 맨 위에 새로운 요소를 추가합니다.
  • pop: 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환합니다. 스택이 비어 있으면, 연산을 수행할 수 없습니다.
  • peek 또는 top: 스택의 맨 위에 있는 요소를 반환하지만, 제거하지는 않습니다.
  • isEmpty: 스택이 비어 있는지 확인합니다.
  • size: 스택에 저장된 요소의 개수를 반환합니다.
• 구현 방법: 스택은 배열이나 연결 리스트를 사용하여 구현할 수 있습니다. 배열 기반 구현은 크기가 고정되어 있어, 스택의 크기를 미리 정해야 합니다. 반면, 연결 리스트 기반 구현은 동적으로 크기가 조정되어, 더 유연한 사용이 가능합니다.
• 효율성: 스택의 연산들은 일반적으로 상수 시간 복잡도 O(1)을 가집니다. 즉, 스택의 크기와 상관없이 push, pop, peek 연산을 매우 빠르게 수행할 수 있습니다.

사용 예시

1. 함수 호출 관리: 프로그래밍에서 함수가 호출될 때, 호출된 함수의 정보(반환 주소, 매개변수 등)를 스택에 저장합니다. 함수가 실행을 마치고 반환될 때, 스택에서 가장 최근에 저장된 정보를 꺼내어 프로그램의 실행을 이어갑니다.
2. 괄호 검사: 수학적 수식이나 프로그램 코드에서 괄호가 올바르게 닫혔는지 확인할 때 사용할 수 있습니다. 여는 괄호를 만날 때마다 스택에 추가하고, 닫는 괄호를 만날 때 스택에서 괄호를 꺼내어 짝을 맞춥니다. 모든 괄호가 올바르게 짝을 이루면 스택은 비어있게 됩니다.
3. 웹 브라우저의 뒤로 가기 기능: 사용자가 방문한 웹 페이지의 URL을 스택에 저장합니다. 사용자가 뒤로 가기 버튼을 클릭하면, 스택에서 가장 최근에 방문한 페이지의 URL을 꺼내어 사용자를 해당 페이지로 이동시킵니다.
4. 문자열 역순 출력: 문자열의 각 문자를 차례대로 스택에 삽입하고, 모든 문자가 스택에 들어간 후에 하나씩 꺼내어 출력하면 문자열이 역순으로 출력됩니다.
5. 수식의 후위 표기법 변환 및 계산: 중위 표기법으로 표현된 수식을 후위 표기법으로 변환하거나, 후위 표기법으로 표현된 수식을 계산할 때 스택을 사용할 수 있습니다. 연산자의 우선순위를 고려하여 스택을 활용하여 수식을 변환하고 계산합니다.
6. 재귀 알고리즘의 반복적 구현: 재귀 함수를 사용하지 않고 반복문과 스택을 사용하여 재귀 알고리즘을 구현할 수 있습니다. 이 방법은 재귀 호출의 깊이가 너무 깊어 스택 오버플로우가 발생할 위험이 있는 경우에 유용할 수 있습니다.

파이썬에서의 Stack

파이썬에서 스택을 사용할 때 기본적으로 제공되는 list 자료형을 사용하는 것이 일반적입니다. 이는 파이썬의 list가 이미 스택에서 필요한 주요 연산들을 지원하기 때문입니다. 예를 들어, append() 메소드로 스택의 맨 위에 새로운 요소를 추가할 수 있고(push 연산), pop() 메소드로 스택의 맨 위 요소를 제거하며 반환할 수 있습니다(pop 연산). 또한, list의 마지막 요소를 조회하는 것으로 스택의 맨 위 요소를 확인할 수 있습니다(peek 또는 top연산).

 

# 스택 생성 및 초기화
stack = []

# 스택에 요소 추가(push)
stack.append(1)
stack.append(2)
stack.append(3)

print("스택 상태:", stack)

#스택에서 요소 제거(pop)
top_element = stack.pop()
print("제거된 요소:", top_element)
print("스택 상태:", stack)

#스택 맨 위의 요소 확인(peek)
if stack:
	top_element = stack[-1]
    print("맨 위의 요소:", top_element)
    
#스택이 비어 있는지 확인
if not stack:
	print("스택이 비어 있습니다.")
else:
	print("스택에 요소가 있습니다.")

 

Queue(큐)

 

큐(Queue)는 컴퓨터 과학에서 매우 중요한 선형 자료구조 중 하나입니다. 큐의 가장 핵심적인 특징은 FIFO(First In First Out, 선입선출) 원칙을 따른다는 것입니다. 즉, 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다. 

 

특징

• FIFO 원칙: 큐의 가장 중요한 특징으로, 먼저 들어온 데이터가 먼저 나가는 구조입니다. 이는 실생활에서 줄을 서서 기다리는 것과 유사합니다.
• 연산
  • Enqueue: 큐의 뒤쪽에 새로운 요소를 추가합니다.
  • Dequeue: 큐의 앞쪽에서 요소를 제거하고 반환합니다.
  • Peek/Front: 큐의 맨 앞에 있는 요소를 조회하지만 제거하지는 않습니다.
  • isEmpty: 큐가 비어있는지 확인합니다.
  • size: 큐에 저장된 요소의 수를 반환합니다.
• 용도: 큐는 데이터가 처리되기를 기다리는 동안 순서를 유지해야 할 때 사용됩니다. 예를 들어, 프린트의 인쇄 작업 관리, 운영 체제에서 프로세스 스케줄링, 네트워크 요청의 처리 순서 등 다양한 시스템에서 큐는 중요한 역할을 합니다.
• 구현: 큐는 배열이나 연결 리스트를 사용하여 구현할 수 있습니다. 연결 리스트를 사용한 구현은 동적으로 크기가 조정될 수 있기 때문에 더 유연합니다. 반면, 배열을 사용할 경우, 큐의 크기가 고정되어 있거나 순환 배열을 사용하여 구현해야 합니다.
• 변형: 큐는 다양한 형태로 변형될 수 있습니다. 예를 들어, 우선순위 큐는 요소가 우선순위에 따라 처리되는 특별한 형태의 큐이며, 순환 큐는 배열을 사용하여 공간을 효율적으로 사용하는 큐의 변형입니다.

 

사용 예시

1. 운영 체제의 프로세스 스케줄링: 운영 체제에서는 여러 프로세스가 실행을 기다립니다. 큐를 사용하여 실행 대기 중인 프로세스를 관리하고, 프로세스 스케줄러는 큐에서 순서대로 프로세스를 선택하여 CPU 시간을 할당합니다. 
2. 프린터의 작업 관리: 여러 문서가 동시에 인쇄를 요청할 때, 프린터는 하나의 작업만 처리할 수 있습니다. 이때 인쇄 작업 요청을 큐에 저장하고, 하나씩 순서대로 처리합니다.
3. 웹 서버의 요청 처리: 웹 서버에 동시에 많은 요청이 들어올 때, 서버는 한 번에 하나의 요청만 처리할 수 있습니다. 큐를 사용하고 요청을 관리하고, 요청이 들어온 순서대로 처리할 수 있습니다.
4. 콜 센처의 전화 대기열: 콜 센터에 동시에 여러 전화가 걸려올 때, 모든 전화를 동시에 처리할 수 없습니다. 전화 요청을 큐에 넣어 관리하고, 상담원이 가능해질 때마다 큐에서 하나씩 요청을 꺼내 처리합니다.
5. 데이터 패킷 관리: 네트워크 라우터나 스위치에서는 데이터 패킷을 전송 대기열에 넣고, 순서대로 네트워크를 통해 전송합니다. 이를 통해 패킷이 순서대로 목적지에 도달할 수 있도록 합니다.
6. 실시간 시스템의 이벤트 처리: 실시간 시스템에서는 발생하는 이벤트를 순서대로 처리해야 할 때가 많습니다. 이벤트를 큐에 넣어 두고, 하나씩 순서대로 처리함으로써 시스템의 안정성과 반응성을 유지할 수 있습니다.

 

파이썬에서의 Queue

deque(double-ended queue)는 collections 모듈에서 제공하는 자료구조로, 양쪽 끝에서 아이템을 추가하거나 제거하는 연산을 효율적으로 수행할 수 있습니다. FIFO (First In First Out) 큐를 구현할 때 deque를 사용하는 것이 일반적인 리스트보다 더 효율적입니다. 

 

from collections import deque

#deque로 큐 생성
queue = deque()

#데이터를 큐에 추가 - Enqueue
queue.append(1)
queue.append(2)
queue.append(3)

prnit("큐 상태:", queue)

#큐에서 데이터를 처리 - Dequeue
while queue:
	item = queue.popleft()
    print(f"처리하는 아이템: {item}")
    
#출력:
#큐 상태:deque([1, 2, 3])
#처리하는 아이템: 1
#처리하는 아이템: 2
#처리하는 아이템: 3

 

 

오늘은 Stack과 Queue에 대해서 알아보았습니다.

추가적으로 ArrayList와 LinkedList도 중요한 자료구조이니 같이 참고해주세요!

2024.04.29 - [IT] - [자료구조] ArrayList VS LinkedList

[자료구조] ArrayList VS LinkedList