큐와 스택, 데크는 뭘까?

 

큐와 스택, 데크

• 일렬로 늘어선 같은 형태의 자료들을 저장한다.
• 셋의 차이는 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가 이다.
• 셋 다 O(1)에 이루어진다.
• push : 자료를 넣는 것
• pop : 자료를 빼는 것

큐

• 선입선출
• 가장 먼저 들어간 자료 순으로 빠진다.
• 줄서기

스택

• 후입선출
• 가장 늦게 들어간 것 순으로 빠진다.
• 컨텍스트 관리

데크

• 양쪽 끝에서 자료들을 넣고 뺄 수 있다.
• 스택과 큐를 모두 구현 가능하다.

19.2 큐와 스택, 데크의 구현

• 연결 리스트
  • 양쪽 끝에서 추가와 삭제를 모두 상수 시간에 할 수 있다.
  • 노드의 할당과 삭제, 포인터를 따라가는데 드는 시간이 걸리기 때문에 가장 효율적이진 않다.
• 동적 배열
  • 스택은 쉽게 가능하다.
  • 하지만 앞에서 추가와 삭제가 일어나는 것은 동적 배열에서 쉽지 않다.
• 대부분 표준 라이브러리에서 지원한다.

ref

• 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략