알고리즘

[알고리즘 마스터] 12. 스택과 큐

개발하는 감자입니다 2024. 1. 8. 19:19
728x90

 

안녕하세요. 개발감자 박그냥입니다!🥔

오늘은 알고리즘 중 <스택과 큐> 에 대해 정리해보도록 하겠습니다.

 

12. 스택과 큐

 

 

스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 가장 기본적이면서도 중요한 자료구조입니다. 

이 두 가지 자료구조는 데이터를 저장하고 조작하는 방식에 있어서 서로 다른 특징을 가지고 있습니다. 

아래의 그림은 개발감자가 복습하며 그려본 그림입니다. 참고하여 학습에 도움이 되셨으면 좋겠습니다.

 

1. 스택(Stack) 

1-1 특징

  • 선입후출(LIFO, Last-In-First-Out) 구조를 가지고 있습니다. 
  • 가장 최근에 추가된 요소가 가장 먼저 제거됩니다. 
  • 스택에 요소를 추가하는 작업을 "push", 제거하는 작업을 "pop"이라고 합니다. 
  • 주요 동작: push, pop, top(가장 상단 요소 확인), empty(비어있는지 확인) 
  • 예시: 함수 호출의 재귀적 호출을 관리할 때, 웹 브라우저의 뒤로 가기 버튼 등 
  • top : 삽입과 삭제가 일어나는 위치

1-2. 연산 방법

여기서 s는 스택의 이름입니다. data는 넣을 값을 의미합니다

  • 삽입 : s.append(data) - top 위치에 data를 삽입합니다.
  • 삭제 : s.pop() - top 위치에 있는 data를 삭제 합니다.

스택의 삽입과 삭제 과정

삽입 시에는 1->4->3->2이지만, 삭제 시에는 2->3->4->1 이라는 것을 알 수 있습니다.
Last-In-First-Out, 즉 마지막에 들어간 것이 처음으로 나온다라는 것을 직접 눈으로 확인하였습니다.

 

 

2. 큐(Queue) 

 

2-1. 특징

  • 선입선출(FIFO, First-In-First-Out) 구조를 가지고 있습니다. 
  • 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 
  • 큐에 요소를 추가하는 작업을 "enqueue", 제거하는 작업을 "dequeue"라고 합니다. 
  • 주요 동작: enqueue, dequeue, front(가장 앞 요소 확인), empty(비어있는지 확인) 
  • 예시: 프린터 대기열, 작업 스케줄링 등 

2-2. 연산 방법

여기서 s는 스택의 이름입니다. data는 넣을 값을 의미합니다

 

  • 위치 : rear - 큐에서 가장 끝 데이터를 가리키는 영역, front - 큐에서 가장 앞의 데이터를 가리키는 영역
  • 삽입 : s.append(data) - front 위치에 data를 삽입합니다.
  • 삭제 : s.popleft() - rear 위치에 있는 data를 삭제 합니다.

큐의 삽입과 삭제 과정

삽입 시에는 1->4->3->2이지만, 삭제 시에는 1->4->3->2 이라는 것을 알 수 있습니다.
First-In-First-Out, 즉 처음으로 들어간 것이 처음으로 나온다라는 것을 직접 눈으로 확인하였습니다.

 

2-3. 구현

1) 큐

from collections import deque

# 빈 큐 생성
queue = deque()

# 큐에 요소 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

# 큐에서 요소 제거 (dequeue)
print(queue.popleft())  # 출력: 1

# 큐가 비어있는지 확인
print(len(queue) == 0)  # 출력: False

 

2) 우선순위 큐

 

우선순위 큐를 활용하는 경우는 우선순위를 적용해야 할 때이다. 

우선순위 큐에서는 우선순위에 따라서 정렬하고 절댓값이 같은 경우에는 음수 우선으로 정렬한다.

from queue import PriorityQueue

# 우선순위 큐 생성
pq = PriorityQueue()

# 요소 추가
pq.put((3, "Apple"))
pq.put((1, "Banana"))
pq.put((2, "Orange"))

# 요소 제거
print(pq.get())  # 출력: (1, 'Banana')
print(pq.get())  # 출력: (2, 'Orange')

 

 

 

3. 주요 차이점 

  • 구조적인 차이: 스택은 한 쪽 끝에서만 삽입과 삭제가 일어나는 반면, 큐는 한 쪽 끝에서는 삽입, 다른 쪽 끝에서는 삭제가 발생합니다. 
  • 데이터 접근 방식: 스택은 접근이 LIFO 방식이므로 최근에 추가된 요소에 먼저 접근합니다. 
  • 반면 큐는 FIFO 방식으로 가장 먼저 추가된 요소에 먼저 접근합니다. 
  • 활용 분야의 차이: 각각의 특성에 따라 스택과 큐는 서로 다른 용도로 사용됩니다. 스택은 재귀적인 문제 해결, 역추적(backtracking), 브라우저의 뒤로 가기 등에 사용되고, 큐는 대기열 관리, 작업 스케줄링, 데이터 버퍼 등에 사용됩니다. 

 

스택과 큐는 프로그래밍에서 매우 중요한 역할을 하며, 다양한 문제를 해결하는 데에 활용됩니다. 개발자가 자료구조를 이해하고 적절하게 활용할 수 있다면 프로그램을 더 효율적으로 작성할 수 있습니다.

 

그럼 더 유익한 포스팅으로 돌아올게요! 개발감자였습니다 :)
728x90
반응형