[CS기초] 스택(Stack), 큐(Queue)

스택(Stack)

스택 개요

스택(Stack)은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조이다.

 

 

 

스택의 특징

• 먼저 들어온 데이터가 가장 늦게 나갈 수 있는 FILO(선입후출) 구조이다
• 무조건 최상단(맨 뒤)에 요소를 넣고 빼야 하기 때문에 요소를 추가하거나 제거하는 데 O(1)의 시간이 걸린다
• 최상단(맨 뒤)의 요소를 확인하는 데 O(1)의 시간이 걸린다.
  • 원칙적으로는 최상단(맨 뒤)의 요소만 확인이 가능하다
  • 다만, 배열로 스택을 구현하면 스택 중간의 원소도 확인 가능하게 구현이 가능하다

 

파이썬에서 스택의 구현

파이썬에서는 단순 배열로 스택을 구현해 사용한다.

# 배열로 스택 자료구조를 구현해 사용
stack = []

# push: 스택 최상단에 요소 추가
stack.append(28)

# pop: 스택 최상단에서 요소 제거(및 활용)
# 단, 스택이 비어있을 경우 IndexError가 발생하므로 주의
number = stack.pop()

# size: 스택에 들어있는 요소의 개수 확인
stack_size = len(stack)

# empty: 스택이 비어있는지 여부 확인
# 스택에 아무 요소도 없다면 False, 하나라도 있다면 True를 반환.
# 이를 이용해 스택이 비어있을 경우에 대한 처리가 가능
if stack:
    print("스택에 요소가 있습니다.")
else:
    print("스택에 요소가 없습니다.")
    
# top: 스택 최상단의 정수 확인
# 단, 스택이 비어있을 경우 IndexError가 발생하므로 주의
top_element = stack[-1]

 

 

 

큐(Queue)

큐 개요

큐(Queue)는 한쪽 끝에서 데이터를 넣고 다른쪽 끝에서 데이터를 뺄 수 있는 자료구조이다.

 

큐의 특징

• 먼저 들어온 데이터가 가장 먼저 처리되는 FIFO(선입선출) 구조이다
• 무조건 맨 뒤에 요소를 넣고 맨 앞에서 빼기 때문에 요소를 추가하거나 제거하는 데 O(1)의 시간이 걸린다
• 맨 앞(또는 맨 뒤)의 요소를 확인하는 데 O(1)의 시간이 걸린다
  • 원칙적으로 맨 앞(또는 맨 뒤)의 요소만 확인이 가능하다

 

파이썬에서 큐의 구현

파이썬에서는 표준 라이브러리의 Collections 모듈 안에 있는 deque 클래스를 이용한다. 원래는 양쪽 끝에서 삽입과 삭제가 모두  가능한 덱을 구현한 클래스이지만, 위에서 배열로 스택을 구현하듯이 큐 또한 deque 클래스로 구현해 사용한다.

# Collections.deque 모듈로 큐를 구현해 사용
from collections import deque
q = deque()

# push: 큐에 요소 추가
q.append(28)

# pop: 큐의 가장 앞에 있는 정수를 제거(및 활용)
# 단, 큐가 비어있을 경우 IndexError가 발생하므로 주의
number = q.popleft()

# size: 큐에 들어있는 요소의 개수 확인
q_size = len(q)

# empty: 큐가 비어있는지 여부 확인
# 큐에 아무 요소도 없다면 False, 하나라도 있다면 True를 반환. 이를 이용해 큐가 비어있을 경우에 대한 처리가 가능
if q:
    print("큐에 요소가 있습니다.")
else:
    print("큐에 요소가 없습니다.")
    
# front: 큐의 가장 앞에 있는 정수 확인
# 단, 큐가 비어있을 경우 IndexError가 발생하므로 주의
front_element = q[0]

# back: 큐의 가장 뒤에 있는 정수 확인
# 단, 큐가 비어있을 경우 IndexError가 발생하므로 주의
back_element = q[-1]