스택과 큐

스택

스택(stack)은 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조

→ 후입선출은 삽입과 삭제가 한쪽에서만 일어남

스택 연산 과정

• 새 값이 스택에 들어가면 top이 새 값을 가리킨다.
• 스택에서 값을 빼낼 때 pop는 top이 가리키는 값을 스택에서 빼게 되어 결과적으로 가장 마지막에 넣었던 값이 나온다.

[파이썬의 스택]

위치

top: 삽입과 삭제가 일어나는 위치

 

연산(리스트 이름이 s일 때)

s.append(data): top 위치에 새로운 데이터를 삽입하는 연산

s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산

s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

---

큐

큐(queue)는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조

→ 먼저 들어온 데이터가 먼저 나가는 방식으로, 삽입과 삭제가 양방향에서 이뤄짐

큐 연산 과정

• 새 값 추가는 큐의 rear에서 이뤄짐
• 삭제는 큐의 front에서 이뤄짐
• deque를 이용하여 큐를 구현

[파이썬의 큐]

위치

rear: 큐에서 가장 끝 데이터를 가리키는 영역

front: 큐에서 가장 앞의 데이터를 가리키는 영역

 

연산(리스트 이름이 s일 때)

s.append(data): rear 부분에 새로운 데이터를 삽입하는 연산

s.popleft(): front부분에 있는 데이터를 삭제하고 확인하는 연산

s[0]: 큐의 맨 앞에 있는 데이터를 확인할 때 사용하는 연산

---

⭐️  우선순위 큐(priority queue)

• 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 큐 설정에 따라 front에 항상 최댓값 또는 최솟값 위치
• 힙(heap)을 이용해 구현