stack-queue.md

스택

Last In First Out으로 최근에 추가한 항목이 가장 먼저 제거되는 데이터 방식

✔ 함수

• pop() : 스택에서 가장 위에 있는 항목을 제거
• push() : item하나를 스택의 가장 윗 부분에 추가
• peek() : 스택의 가장 위에있는 항목을 제거없이 값만 반환
• isEmpty() : 스택이 비었는지 검사

✔ 사용 예

• 재귀 알고리즘
• 웹 방문기록
• 실행 취소

연결 list를 이용한 코드 예(C 언어)

큐

First In First Out으로 가장 먼저 추가한 데이터가 먼저 제거되는 데이터 방식

✔ 함수

• add(inQueue)() : 큐의 끝 부분에 데이터 추가
• remove(deQueue)() :큐의 첫번째 항목을 제거
• peek() : 큐의 가장 위에있는 항목을 제거없이 값만 반환
• isEmpty() : 큐가 비었는지 검사

✔ 사용 예

• 프로세스 관리
• 너비 우선 탐색(BFS)
• 캐시 구현
• 우선순위 큐
• 덱

연결 list를 이용한 코드 예(C 언어)

우선순위 큐 ( Priority Queue )

---

우선순위의 개념을 큐에 도입한 자료 구조.
일반적인 큐는 FIFO의 규칙으로 먼저 들어온것이 나가게 되나 우선순위 큐는 우선순위가 높은 순서대로 나가게 된다.

구현 방법

• 배열
• 리스트
• 힙(Heap)

표현 방법	삽 입	삭 제
순서 없는 배열 / 리스트	O(1)	O(n)
정렬된 배열 / 리스트	O(n)	O(1)
힙	O(logn)	O(logn)

덱 ( Deque )

---

Double-ended queue의 약자.
양 끝에서만 자료를 넣고 뺄 수 있는 자료구조
일반 큐와의 차이점은 push,pop 할 수 있는 방향이 양방향이라는 것이 차이점이다.