알고스팟(algospot) 19장 큐와 스택, 데크

728x90

큐 -- 한쪽으로 정보를 저장하고 다른 한쪽에서 정보를 꺼내는 (선입선출 FIFO) 스택 -- 한쪽으로 정보를 저장, 출력하는 (후입 선출 LIFO)

데크-- 양쪽에서 저장,출력을 하는

연결리스트를 통한 구현-- 구현하기에는 가장 간단

그러나 포인터를 통해 이동하는데 시간이 걸려 가장 효율적이지는 않다!

동적배열을 이용한 구현 -- 스택의 경우에는 Vector를 이용해서 쉽게 구현 가능 (--> 한쪽으로만 저장, 출력하기 때문)

그러나 큐와 데크(덱)같은 경우는 앞부분에서도 저장 또는 출력이 일어나기에 모든 변수를 이동해야 할 수도 있음!

---> 그래서 동적배열을 이용해서 큐와 덱을 구현할 때는 첫 번째 원소를 head, 마지막 원소를 tail로 유지하고

원소 전체를 옮기는 대신 head이나 tail의 위치를 이동 시킵니다.

그러나... 이런 방법은 공간 낭비가 심하다...

--> 환형 버퍼 --> 원형 큐..? 인 것 같네요

예제 문제 1. 큐를 이용한 조세푸스 문제

18장에서 풀었던 방법 --> 연결 리스트로 구성하여 죽을 사람을 가리키는 포인터를 옮김

여기서 풀방 법--> 하나의 큐에 모든 사람을 넣고 맨 앞의 사람을 한 명 한명 꺼내서 죽을 사람이면 없애고 안 죽을 사람이면 맨뒤로 보내는 작업을 두 명이 남을 때까지 반복

--> 큐를 사용해도 연결 리스트로 구현할 테지만 구현이 간단해짐!

예제 문제 2. 스택을 이용한 울타리 자르기

7장에서 풀었던 방법--> 이분법, 분할 정복을 통해 해결!

여기서 풀 방법--> 15장의 스위핑 알고리증 + 스택

스위핑 : 한쪽에서 다른 한쪽까지 훑어보기

1. 한쪽에서 탐색 시작 판자 스택에 추가

2. 스택에 들어 있는 판자와 현재 판자와의 높이 비교

--> 높으면 크기만 따로 저장

--> 낮으면 스택에 추가

3. 크기 비교 후 가장 큰 값 출력

여기까지가 19장

오늘도 열시미!