19장 큐와 스택, 데크

neptunes032·2020년 9월 20일
0

종만북

목록 보기
5/6

큐와 스택, 데크

큐와 스택, 데크

큐와 스택, 데크는 일렬로 늘어선 같은 형태의 자료들을 저장합니다. 차이점은 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가입니다.

한쪽 끝에서 자료를 넣고 반대쪽 끝에서 자료를 꺼낼 수 있습니다. 따라서 가장 먼저 들어간 자료를 가장 먼저 꺼내게 됩니다. 이러한 속성을 FIFO(First In First Out)이라고 부릅니다.

스택

한 쪽 끝에서만 자료를 넣고 뺄 수 있습니다. 따라서 가장 늦게 넣은 자료를 가장 먼저 꺼내게 됩니다. 이러한 속성을 LIFO(Last In First Out)이라고 부릅니다.

데크

데크는 양쪽 끝에서 자료들을 넣고 뺼 수 있는 자료 구조를 말합니다. 따라서 데크를 이용하면 스택과 큐를 모두 구현할 수 있습니다.


큐와 스택, 데크의 구현

연결리스트를 통한 구현

이 세 가지 자료 구조를 구현하는 가장 간단한 방법은 연결 리스트를 이용하는 것이다. 연결 리스트를 이용하면 양쪽 끝에서 추가와 삭제 모두 상수 시간에 할 수 있기 때문에, 모든 연산이 상수 시간이어야 한다는 요구 조건을 쉽게 충족할 수 있다. 물론 이 경우 노드의 할당과 삭제 그리고 포인터를 따라가는 데 드는 데 시간이 걸리기 떄문에 연결 리스트가 가장 효율적인 구현은 아니다.

동적 배열을 이용한 구현

스택의 경우 한쪽 끝에서만 자료의 추가와 삭제가 일어나므로 동적 배열을 곧장 사용할 수 있다.


스택과 큐의 활용

예제: 큐를 이용한 조세푸스 문제의 해법

예제: 스택을 이용한 울타리 자르기 문제의 해법

  • 스위핑 알고리즘
    • 다시읽기
    • 15.11 참조

문제: 찍이 맞지 않는 괄호(BRACKETS2, 하)


문제: 외계 신호 분석(ITES, 중)


풀이: 외계 신호 분석

  1. 단순한 알고리즘
  2. 최적화된 알고리즘
  3. 온라인 알고리즘
  • 온라인 알고리즘

오란인 알고리즘이란 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘을 말한다. 알고리즘 수행 중 새 입력을 받아 계산을 계속하기 때문에, 입력 전체가 메모리에 올라와 있지 않아고 계산을 시작 할 수 있습니다.

  • 오프라인 알고리즘

오프라인 알고리즘이란 입력 전체를 이미 가지고 있다고 가정하고 동작하는 알고리즘을 말한다. 예를 들어 삽입 정렬은 새 원소를 이전의 정렬된 목록에 끼워넣는 방식으로 동작하므로, 처음에 모든 원소가 없더라도 시작할 수 있다. 반면 선택정렬은 남아있는 모든 원소 중에서 최소의 원소를 찾아서 맨 앞에 옮기는 방식으로 작동하므로 모든 원소를 알고 있어야만 동작을 시작할 수 있습니다. 따라서 삽입정렬은 온라인 알고리즘, 선택 정렬은 오프라인 알고리즘이라 할 수 있다.

profile
개발자가 되고싶다.

0개의 댓글