[개념정리] 큐, 스택, 덱(Queue, Stack, Deque)

오늘은 추상화된 자료구조 3대장인 큐 스택 덱을 정리한다.

First In First Out
head는 큐의 시작부분, tail은 큐의 마지막 원소 다음 칸을 가리킨다.
동적 배열로 구현되어있다.(pop하면 head를 한 칸 우측으로, push하면 tail을 한 칸 우측으로 이동시킨다. 만약 용량을 초과한다면 tail을 원래 배열의 처음 부분으로 돌린다(=환형 버퍼, circular buffer

6549번: 히스토그램에서 가장 큰 직사각형

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤

www.acmicpc.net

스택이라는 쉬운 개념을 가르쳐놓고 막상 예제문제는 플래티넘급으로 풀으라고 한다 ㅜㅜ

문제 해설하는 글은 아니니 간략하게만 해결 전략을 적자면,

직사각형(판자)을 처음부터 순회하면서 직사각형을 막는 양 끝을 각각 left[i], right[i]로 둔다.

여기서 높이가 0인 가상의 직사각형이 왼쪽 맨 끝에 있다고 가정한다. (h[0] = 0)

h[i] > h[i+1] : right[i] = i+1이 되고, left[i], right[i]를 모두 알고 있으므로 넓이를 계산할 수 있다. 여기서 (i+1)번 직사각형이 더 낮기 때문에, 이후의 어떤 직사각형 k라도 left[k]=0이 될리 없으므로 i번째 직사각형은 지워버린다. 그러고 나면 left[i+1] = left[i]가 된다.(지우기 전에 해야한다)
h[i]<h[i+1] : i 직사각형이 (i+1)직사각형을 막고 있으므로 left[i+1]=i이다. 나머지는 알 수 없으므로 냅둔다.
h[0]=h[1] : 두 직사각형의 최대 사각형은 완전히 똑같다. 따라서 i번 판자를 계속 남겨둘 필요가 없으므로 1번 경우와 똑같이 하면 된다.

남겨진 직사각형은 스택에 두고 push, pop을 계속 진행하면 된다! (시간복잡도는 O(N)이다.)