[자료구조] 스택(Stack) 큐(Queue) 해시테이블(Hash Table)

 

파이썬에서는 이미 구현되어있다.

클래스와 함수명을 외우기만 하면 된다!!!!

1. 스택 (Stack)

파이썬에서 스택은 리스트를 사용하여 쉽게 구현할 수 있습니다.

 

스택은 LIFO (Last In, First Out)의 원칙을 따르는 선형 자료구조입니다. 즉, 가장 나중에 추가된 요소가 가장 먼저 제거됩니다. 스택의 주요 연산은 다음과 같습니다.

• push: 스택의 맨 위에 요소를 추가합니다. - append()
• pop: 스택의 맨 위 요소를 제거하고 그 값을 반환합니다. - pop()
• peek/top: 스택의 맨 위 요소를 조회합니다. - ls[-1]
• isEmpty: 스택이 비어 있는지 확인합니다. - not ls # 비어있으면 True

stack = []
stack.append(1)        # 스택에 1을 push
stack.append(2)        # 스택에 2를 push
print(stack)           # 스택 출력 -> [1, 2]
top_element = stack.pop()  # 스택에서 pop, top_element는 2
print(top_element)     # 출력: 2
print(stack)           # 스택 출력 -> [1]

 

2. 큐(Queue)

큐는 collections 모듈의 deque 클래스를 사용.

리스트를 쓰면 시간복잡도가 훨씬 높음 Q(n), deque는 Q(1)

큐는 FIFO (First In, First Out) 원칙을 따르는 선형 자료구조로, 처음 추가된 요소가 가장 먼저 제거됩니다. 큐의 주요 연산은 다음과 같습니다.

• enqueue: 큐의 뒤쪽에 요소를 추가합니다. - append()
• dequeue: 큐의 앞쪽에서 요소를 제거하고 그 값을 반환합니다. - popleft()
• front: 큐의 첫 번째 요소를 조회합니다. - queue[0]
• isEmpty: 큐가 비어 있는지 확인합니다. - not queue # 비어있으면 True

from collections import deque

queue = deque()
queue.append(1)         # 큐에 1을 enqueue
queue.append(2)         # 큐에 2를 enqueue
print(list(queue))      # 큐 출력 -> [1, 2]
first_element = queue.popleft()  # 큐에서 dequeue, first_element는 1
print(first_element)    # 출력: 1
print(list(queue))      # 큐 출력 -> [2]

3. 해시테이블 (Hash Table)

파이썬에서 해시테이블은 딕셔너리(dict) 자료형으로 구현되어 있습니다. 키와 값의 쌍을 저장할 수 있으며, 매우 빠른 검색, 삽입, 삭제 연산을 제공합니다.

해시테이블은 키를 값에 매핑하여 데이터를 저장하는 자료구조입니다. 이 구조는 해시 함수를 사용하여 각 키를 배열의 인덱스로 변환하고, 해당 인덱스에 값을 저장합니다. 해시테이블의 주요 특징은 빠른 데이터 검색 속도입니다. 해시테이블의 주요 연산은 다음과 같습니다.

• insert: 키-값 쌍을 해시테이블에 추가합니다. - hash_table['키'] = 값
• delete: 주어진 키에 해당하는 요소를 해시테이블에서 삭제합니다. - del 연산자
• get: 주어진 키에 대응하는 값을 찾습니다. - get()
  
  • [] 를 사용했을때, 키가 존재하지 않으면 에러 발생
  • get 함수는 None값을 반환함

hash_table = {}
hash_table['apple'] = '사과'    # 키 'apple'에 값 '사과'를 저장
hash_table['banana'] = '바나나' # 키 'banana'에 값 '바나나'를 저장
print(hash_table)      # 해시테이블 출력 -> {'apple': '사과', 'banana': '바나나'}
value = hash_table.get('apple') # 키 'apple'의 값을 가져옴
print(value)           # 출력: 사과
hash_table['apple'] = '애플'    # 키 'apple'의 값을 '애플'로 업데이트
print(hash_table)      # 해시테이블 출력 -> {'apple': '애플', 'banana': '바나나'}
del hash_table['banana'] # 키 'banana'를 가진 항목을 삭제
print(hash_table)      # 해시테이블 출력 -> {'apple': '애플'}