Stack Queue

스택


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 할 수 있는 방향이 양방향이라는 것이 차이점이다.