Stack , Queue, Deque (스택, 큐, 덱)

✅Stack, Queue, Deque(스택, 큐, 덱)

저장공간 = [[1],[2],[3],[4],[5],[6]]

 

저장공간에서 필요한 데이터를 꺼낼 것이다.

저장공간은 자료가 선형으로 저장되어 있다.

 

Stack : 마지막에 들어온 데이터를 먼저 꺼내자, 후입선출 LIFO(Last In First Out) 구조

   ex) 크롬의 뒤로 가기, 접시 꺼내기, 후입 선출

 

# Stack 완전 기본 코드 (개념 이해)
stack = [] # 동적 메모리, 컴파일 될 때 크기가 확정되는게 아니라, 실행단계에서 계속 왔다가 갔다가 함.

stack.append(1)
stack.append(2)
stack.append(3)

print(stack.pop())
print(stack.pop())
print(stack.pop())

---

 

Stack 주요 연산

stack = []

# 1. push(x): 스택의 맨 위에 원소 x 추가
stack.append(10)  # [10]
stack.append(20)  # [10, 20]

# 2. pop(): 스택의 맨 위 원소 제거 후 반환
top = stack.pop()  # 20 제거 → [10]

# 3. peek(): 스택의 맨 위 원소 반환 (제거하지 않음)
top = stack[-1]  # 10

# 4. isEmpty(): 스택이 비어있는지 확인
is_empty = len(stack) == 0  # False

# 5. size(): 스택의 크기 반환
size = len(stack)  # 1

 

 

 

---

 

 

 

Queue : 먼저 들어온 데이터를 먼저 꺼내자, FIFO(First In First Out) 구조

   ex) 매표소, 선입 선출, 컴퓨터 작업 내역

# Queue 기본 코드
queue = []

queue.append(1)
queue.append(2)
queue.append(3)

# pop(0): 제일 앞에 있는 데이터를 없애는 과정
# -> 주소값은 변경이 없다.
# -> 즉 하나 씩 앞으로 당겨준 후, 맨 뒤 메모리를 제거
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

 

Queue 주요 연산

from collections import deque

queue = deque()

# 1. enqueue(x): 큐의 뒤(rear)에 원소 x 추가
queue.append(10)  # [10]
queue.append(20)  # [10, 20]

# 2. dequeue(): 큐의 앞(front) 원소 제거 후 반환
front = queue.popleft()  # 10 제거 → [20]

# 3. peek(): 큐의 앞(front) 원소 반환 (제거하지 않음)
front = queue[0]  # 20

# 4. isEmpty(): 큐가 비어있는지 확인
is_empty = len(queue) == 0  # False

# 5. size(): 큐의 크기 반환
size = len(queue)  # 1

 

---

append의 한계

 

 리스트는 메모리를 연속적으로 저장하기 때문에 규모가 커지게 되면  다른 데이터랑 충돌 날 경우 새로운 공간을 만들어 리스트를 저장한다. 많은 데이터가 있을 경우 append는 사용하지 못한다.

 

그래서 메모리를 불연속적으로 저장하고 다음 요소의 메모리주소를 알려주는 방식으로 효율적으로 한다.

 

Linked List (연결리스트) 

 리스트의 연속된 메모리로 인한 문제를 해결하는 자료구조 

 각 요소가 떨어진 메모리에 저장된다.

 각 요소는 자기의 다음 요소 주소를 알고 있도록 구현한다.

 

✅ 장점: 데이터 추가 및 삭제 시에 리스트보다 훨씬 빠르다. O(1)

❌ 단점: 시작부터 하나씩 다 봐야 한다. 조회할 때 매우 느려서 O(N)

---

 

 

 

Deque : 이중 연결리스트 자료구조

 

# 실전용
# deque : 이중 연결리스트 자료구조
from collections import deque

dq = deque()
# dq = deque([10, 20, 30]) 초기 데이터값을 넣고 싶을 때

dq.append(1)
dq.append(2)
dq.append(3)

print(dq[2])

# O(1) 만에 제일 처음과 마지막 데이터 삭제 가능
last = dq.pop()            # 제일 마지막 데이터를 제거
first = dq.popleft()        # 제일 앞에 데이터를 제거
print(last, first)

 

Deque 주요 연산

from collections import deque

deque_obj = deque()

# 1. append(x): 덱의 오른쪽 끝(rear)에 원소 x 추가
deque_obj.append(10)  # [10]
deque_obj.append(20)  # [10, 20]

# 2. appendleft(x): 덱의 왼쪽 끝(front)에 원소 x 추가
deque_obj.appendleft(5)  # [5, 10, 20]

# 3. pop(): 덱의 오른쪽 끝(rear) 원소 제거 후 반환
right = deque_obj.pop()  # 20 제거 → [5, 10]

# 4. popleft(): 덱의 왼쪽 끝(front) 원소 제거 후 반환
left = deque_obj.popleft()  # 5 제거 → [10]

# 5. extend(iterable): 여러 개의 원소를 덱의 오른쪽 끝(rear)에 추가
deque_obj.extend([30, 40])  # [10, 30, 40]

# 6. extendleft(iterable): 여러 개의 원소를 덱의 왼쪽 끝(front)에 추가 (거꾸로 삽입됨)
deque_obj.extendleft([1, 2])  # [2, 1, 10, 30, 40]

# 7. rotate(n): 덱을 n만큼 회전 (양수: 오른쪽, 음수: 왼쪽)
deque_obj.rotate(1)  # [40, 2, 1, 10, 30]
deque_obj.rotate(-1)  # 다시 원래대로 [2, 1, 10, 30, 40]