본문 바로가기

Queue2

03. 스택(Stack) & 큐(Queue) 스택(Stack) LIFO(Last in, first out)구조이다. 즉, 배열의 끝에서만 데이터에 접근할 수 있다. 배열 인덱스 접근이 불가하다. 시간복잡도 : O(1)이다. stack의 동작 push : 스택 맨 끝에 항목을 삽입 pop : 스택 맨 끝 항목 반환 및 제거 top/peek : 스택 맨 끝 항목 반환 empty : 비어있는지 확인 size : 스택 크기 확인 스택 구현 1. python list를 활용한 stack 구현 2. Node(객체)의 컨테이너로 Stack 구현 2020. 5. 26.
자료구조: 우선순위 큐(Priority Queue) 우선순위 큐란? 우선순위를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나온다는 특징이 있다. 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우선순위 큐와 큐의 차이점 일반적인 큐는 선형 구조를 가지고 있지만 우선순위 큐는 트리(Tree) 구조로 보는 것이 합리적이다. 일반적으로 우선순위 큐는 최대 힙을 이용하여 구현한다. 최대 힙(Max Heap) 최대 힙은 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리이다. 우선순위 큐의 삽입 완전 이진 트리를 유지하는 형태로 순차적으로 삽입된다. 삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대 힙을 구성한다.(상향식) 우선순위 큐의 삭제 삭제할 때는 루트 노드를 삭제하.. 2019. 8. 30.