[알고리즘/파이썬] #1 자료구조 - 스택 Stack과 큐 Queue

January 18, 2020 / 알고리즘

python_image

요즘 파이썬으로 알고리즘 관련 공부를 하면서 블로그에 포스팅하면 어떨까 생각해서 블로그도 만들었겠다 글을 작성하게 되었다.

1. 스택 Stack!

stack_image

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다 — 위키백과 “스택”

즉 쉽게 말하면 마지막에 넣은 데이터를 먼저 나오는 구조로 저장하는 형식이다.
실생활에서는 대표적인 예로 뷔페의 접시, 엘리베이터가 있다

스택 용어 정리

  • pop() 스택에 자료 삭제 및 반환
  • push() 스택에 자료 삽입
  • top() 스택의 가장 위 데이터 반환

스택 사용하기

그럼 파이썬으로 스택을 사용해보자 파이썬에서는 구현이 필요 없이 리스트를 쓰면 쉽게 스택의 기능을 사용할 수 있다.

a = [] # 아무것도 없는 리스트 변수
a.append(5) # 5 추가 - push()
a.append(1) # 1 추가 - push()
a.append(3) # 3 추가 - push()

print(a) # [ 5, 1, 3 ] 
print(a.pop()) # 3 - pop()
print(a) # [ 5, 1 ]
print(a[-1]) # - top()

# a.append(5) : push(5)
# a.append(1) : push(1)
# a.append(3) : push(3)

# a.pop() : pop()
# a[-1] : top()

2. 큐 Queue!

queue_image

는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 형식을 말한다 — 위키백과 “큐 (자료구조)”

즉 먼저 넣은 데이터를 먼저 나오는 구조로 저장하는 형식이다. 실생활에서는 대표적인 예로 매표소 줄, 티켓팅 데이터 저장이 있다. (큐는 스택보다 공평하다)

큐 용어 정리

  • Front() 또는 head() 데이터의 가장 앞부분
  • Rear() 또는 tail() 데이터의 가장 뒷부분
  • Enqueue(), put() 또는 insert() 큐에 자료를 삽입
  • Dequeue(), get(), delete() 큐에 자료를 삭제 및 반환

큐 사용하기

그럼 파이썬으로 을 사용해보자 는 파이썬에서 모듈로 지원하고 있다.

import queue

a = queue.Queue() # 큐 생성
a.put(100) # - put(100)
a.put('abc') # - put('abc')

print(a.qsize()) # 2 - 큐 리스트의 크기

print(a.get()) # 100 - get() 
print(a.qsize()) # 1

# a.put(100) : put(100)
# a.put('abc') : put('abc')

# a.get() : get()

특수한 형태의 큐

  • 원형 큐 리스트의 맨 마지막 부분을 쓰면 처음부터 다시 큐를 채우기 시작하는 형태의 큐
  • 우선순위 큐 우선순위에 따라 빼는 큐

스택은 양심이 없고 큐는 양심이 있다고 생각하면 이해가 편하다(?)

이 포스팅을 통해 스택에 대해서 알아보았다. 스택은 BFS 와 DFS 등 여러 알고리즘에서 사용되므로 알고 있는 것이 도움이 된다!


Written by@JWN
Node.js와 Go를 좋아하는 개발자 & 학생입니다.요즘은 인공지능, 딥러닝 분야에 관심이 있습니다.

GitHub