Queue/Stack

1. Queue

먼저 저장한 데이터가 먼저 출력되는 FIFO형식으로 데이터를 저장하는 자료구조이다

enqueue

Queue 뒤(rear)에 데이터를 저장하는 것

dequeue

Queue 앞(front)에 데이터를 저장하는 것

1-1. LinkedList / ArrayList

큐는 보통 링크드 리스트로 구현한다 왜 어레이 리스트를 쓰지 않을 까???

예를 들어보자

1부터 6을 하나씩 넣는다고 가정했을 때 enqueue(추가)할때는 뒤에서 apend함수로 넣어주면 되지만 dequeue 할때는 앞에서 하나씩 빼줘야 하기 때문에 뒤에있는 숫자들을 한칸씩 앞으로 옮겨줘야하는 상황이 발생한다

그래서 어레이 리스트로 구현했을 경우 enqueue는 O(1)의 시간복잡도를 가지고 dequeue는 O(n)의 시간복잡도를 가진다

2023.12.11 - [coding test] - Linked List

Linked List

이전 글에서 양방향 수정 삭제 이동이 가능한 doubly linkedlist에 대해서 공부를 했었는데 벌써 deque함수와 비슷하다 그래서 linkedlist로 구현을 한다

2. Deque

파이썬은 이러한 부분이 deque(덱)이라는 자료구조로 잘 구현이 되어있다 이 자료구조는 앞에서 설명한 것 처럼 linkedlist로 구현되어있다.

from collections import deque
queue = deque()

이렇게 자바처럼 콜렉션에 있는 덱을 임포트 시켜놓고 진행한다

덱은 더블리 링크드 리스트 처럼 앞뒤의 요소들을 빼고 넣을 수 있는데

맨 앞(왼쪽) 맨 뒤(오른쪽)

삽입	appendleft()	append()
제거	popleft()	pop()

이 큐는 이 자체의 문제 보다는 다른 알고리즘을 구현할때 재료로 사용된다

3. Stack

stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO형식으로 데이터를 저장하는 자료구조

stack의 top에 데이터를 추가하는 것을 push라고 하고 stack의 top에서 데이터를 추출 하는 것은 pop이라고 한다.

자바스크립트의 콜스택을 생각하면 된다.