Stack(스텍)
스택(stack)은 LIFO (Last In First Out)의 자료구조를 갖고 있다. 즉 먼저 들어간 항목이 나중에 나오고, 나중에 들어간 항목이 먼저 나오는 자료 구조이다.
stack=[2,3,4]
stack.append(1)
print(stack)
#[2, 3, 4, 1]
stack.pop()
print(stack)
#[2, 3, 4]Queue(큐)
큐(queue)는 선입선출, FIFO(First In First Out) 기반의 매우 유명한 자료 구조입니다. 큐를 사용하면 데이터를 추가한 순서대로 제거할 수 있기 때문에 스트리밍(streaming), 너비 우선 탐색(breath first search) 등 소프트웨어 개발에서 널리 응용되고 있다.
queue=[3, 6, 9]
queue.append(2)
queue.append(4)
queue.append(8)
print(queue)
#[3, 6, 9, 2, 4, 8]
queue.pop()
print(queue)
#[3, 6, 9, 2, 4]
queue.pop()
print(queue)
#[3, 6, 9, 2]
queue.insert(0, 4)#insert메서드 insert(index, number)
queue.insert(0, 1)
print(queue)
#[1, 4, 6, 9, 2]
queue.pop()
print(queue)
##[1, 4, 6, 9]
queue.pop()
print(queue)
##[1, 4, 6]-Deque(데크)
데크(deque)는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료 구조이다. 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다.
데크는 다음처럼 임포트(import)해 사용한다
from collections import deque
deq = 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만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).데크 예제
from collections import deque
queue = deque([4, 5, 6])
queue.append(7)
queue.append(8)
print(queue)
#[4, 5, 6, 7, 8]
queue.popleft()
print(queue)
#[5, 6, 7, 8]
queue.popleft()
print(queue)
#[6, 7, 8]Hash(해쉬)
키(Key)와 값(Value)쌍으로 이루어진 데이터 구조를 의미한다. Key를 이용하여 데이터를 찾으므로, 속도를 빠르게 만드는 구조이며, 파이썬에서는 딕셔너리(Dictionary) 타입이 해쉬 테이블과 같은 구조이다. 검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용된다.
해쉬 용어
해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것
해쉬 테이블(Hash Table) : 키값의 연산에 의해 직접 접근이 가능한 데이터 구조
해싱 함수(Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address) : Key를 해싱 함수로 연산해서 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음
슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간
저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음
해쉬 예제
1. 간단한 해쉬 테이블 만들기
hash=[i for i in range(10)]
print(hash)
#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2. 간단한 해쉬 함수 만들기
def hash_func(key):
return key % 2
3. 해쉬 테이블 값 저장
def storage_data(data, value):
key = ord(data[0])
hash_address = hash_func(key)
hash_table[hash_address] = value
storage_data('seunghye', '01043809999')
storage_data('cy', '01045006622')
4. 데이터 읽어오기
def get_data(data):
key = ord(data[0])
hash_address = hash_func(key)
print(hash_table[hash_address])
get_data('seunghye') # 01043809999Heapq(힙큐)
힙(Heap)은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조 이다.
최소 힙 (min heap)
각 노드의 키값이 그 자식 노드의 키값보다 크지 않은 힙 즉 부모 노드가 자식의 노드 값 보다 항상 작아야 한다. 이때 자식 노드의 값은 하나일 수도 있다.
최대 힙 (max heap)
각 노드의 키값이 그 자식 노드의 키값보다 작지 않은 힙, 부모 노드가 자식 노드 값 보다 항상 커야 하며 자식 노드의 값은 하나 일 수도 있다.
#최대 힙은 입력 숫자를 음수로 바꿔서 이용하면 된다.
힙큐는 다음처럼 임포트(import)해 사용한다.
import heapq노드 값 추출 (heappop 메소드 사용)
a=[1,2,3] #리스트 생성
heapq.heappop(a, 1)노드 값 추가 (heappush 메소드 사용)
a=[] #빈 리스트 생성
heapq.heappush(a, 1)