스택
스택은 마지막에 들어간 자료가 가장 먼저 처리되는 후입선출(LIFO) 자료구조이다.
스택 연산
push : 스택 맨 위에 원소 추가
pop : 가장 위에 원소를 삭제하고 반환
top : 스택 가장 위에 원소 반환(삭제는 하지 않는다)
empty : 스택이 비어있으면 1, 그렇지 않으면 0 반환
- python
push : list.append(i)
pop : list.pop()
구현
-
array(배열)
-
장점
인덱스를 이용하여 접근이 빠르다
비순차적 접근이 가능하다
구현이 쉽다 -
단점
길이가 정해져 있어 자원을 미리 할당받아야한다
삽입/삭제가 번거롭다
-
-
Linked List(연결 리스트)
-
장점
삽입/삭제가 용이하다
자원을 미리 할당받지 않아 쉽게 크기를 변경할 수 있다 -
단점
구현이 어렵다
순차적 접근이라 접근 속도가 떨어진다
-
큐
큐는 먼저 들어간 자료가 가장 먼저 처리되는 선입선출(FIFO) 자료구조이다
큐 연산
enqueue : 맨 뒤에 원소 추가
dequeue : 맨 앞에 원소 삭제하고 반환
isEmpty : 큐가 비어있으면 1, 그렇지 않으면 0 반환
peek : 큐 맨 앞에 있는 원소 반환(삭제는 하지 않는다)
- python
- list
enqueue : list.append(i)
dequeue : list.pop(0) - Queue
enqueue : put(i)from queue import Queue que = Queue()
dequeue : get()
- list
구현
-
array(배열)
-
장점
인덱스를 이용하여 접근이 빠르다
비순차적 접근이 가능하다
구현이 쉽다 -
단점
길이가 정해져 있어 자원을 미리 할당받아야한다
삽입/삭제가 번거롭다
-
-
Linked List(연결 리스트)
-
장점
삽입/삭제가 용이하다
자원을 미리 할당받지 않아 쉽게 크기를 변경할 수 있다 -
단점
구현이 어렵다
순차적 접근이라 접근 속도가 떨어진다
-
종류
-
선형 큐 : 막대 모양으로 dequeue로 인해 빈 공간이 발생하면 이를 해결하기 위해 한칸씩 이동해야한다
-
원형 큐 : 원형으로 연결한 큐로 선형 큐의 문제점을 해결
우선순위 큐
들어간 순서와 상관없이 우선순위가 높은 자료가 먼저 처리되는 자료구조이다. 우선순위가 높은 원소가 먼저 처리되고 같은 우선 순위인 경우는 queue의 순서에 따라 처리된다. 주로 힙으로 구현한다.
우선순위 큐 연산
enqueue : 우선순위 큐에 원소 추가
dequeue : 우선순위가 높은 원소 삭제 후 반환
isEmpty : 우선순위 큐가 비어있으면 1, 그렇지 않으면 0 반환
peek : 우선순위가 가장 높은 원소 반환
구현
- 힙
삽입 : 마지막 노드에 새로운 노드를 추가한다. 부모노드와 우선순위를 비교 후 교환을 한다. 최대 힙 일 경우 부모 노드보다 우선 순위가 높으면 교환하고 최소 힙일 경우 부모 노드보다 우선 순위가 낮으면 교환한다.
삭제 : 힙 트리에서 루트 노드가 우선순위가 가장 높으므로 루트 노드를 삭제한다. 루트 노드가 삭제된 자리에 완전이진트리의 마지막 노드를 가져온 후 자식 노드와 비교하여 교환한다. 최대 힙일 경우 자식 노드 중 더 큰 값과 교환하고 최소 힙일 경우 자식 노드 중 더 작은 값과 교환한다.
