[공부] 자료구조 - 스택과 큐

zero_0·2021년 9월 24일
0

알고리즘

목록 보기
9/10
post-thumbnail

스택

스택 구조 : Last In First Out (LIFO), 선입후출 = 후입선출

  • 박스가 쌓여있는 모습을 생각하면 쉬움, 또는 프링글스 통에 담긴 감자칩
# 코드로 stack 표현
stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 먼저 들어온 순서대로 출력 : >>>[5231]
print(stack[::-1]) # 나중에 들어온 순서대로 출력 : >>>[1325]

큐 : First In First Out(FIFO), 선입선출

  • 데이터가 오른쪽에서 왼쪽으로 이동한다고 생각하고 시작, 왼쪽부터 나감.
  • 은행 번호표, 터널(입구와 출구가 모두 뚫려 있는 터널) , 대기열
  • 큐를 사용할 때 리스트를 사용할 수 있지만 시간복잡도가 높아서 deque(데크) 라이브러리를 사용한다.
# 코드로 queue 표현
from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력 : >>>deque([3, 7, 1, 4])
queue.reverse()
print(queue) # 나중에 들어온 순서대로 출력 : >>>deque([4, 1, 7, 3])

데크(deque)의 개념

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다.
양방향 큐가 있는데 그것이 바로 데크(deque)다.
즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

데크(deque)에 존재하는 메서드(method)는 대략 다음과 같다.

deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
deque.remove(item): item을 데크에서 찾아 삭제한다.
deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
profile
차근차근 채워가는 it일지

0개의 댓글