0x07강 덱(deque)-Double Ended Queue

 

덱에서도 원소의 추가, 제거 , 제일 앞 뒤의 원소 확인이 모두 가능한데

제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능이다

그런데 그동안의 STL 큐, STL 스택과는 다르게 

*독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. *

 

배열을 이용한 deque의 구현

여기서 중요한 부분은, 처음에 push_front를 

dat[--head]=x;를 통해서 작성한다는 것이다. 

여기서 --head는 -1을 한 head값을 사용하는 것이고, 만약 head--로 작성했다면 현재의 head값을 사용한뒤에 head에 -1을 시행해줘서 head 값을 바꿔주게 된다. 

이게 굉장히 미묘해 보이지만 아주 중요한 결과의 차이를 만들어낸다. 아주 주의해야할 부분이다. 

 

그리고 성능적인 측면에서도 물론 엄청 커다란 차이를 만들정도는 아니겠으나 i++가 추가적인 메모리를 사용한다. 

그래서 for(int i=0;i<n;i++) 라는 식으로 작성된 for문의 경우 컴파일러가 모두 ++i로 해석해서 동작시킨다고 설명해주는 부분도 검색해보면 나오는것을 알 수 있다. 

현재의 값 자체를 사용하는게 아니라면 ++i를 하거나 i++를 하거나 for문에서는 똑같이 해석 할 수 있지만, 

값에 접근해서 값을 변경하거나 할때는 ++i를 사용할때와 i++를 사용할때 값이 분명 다르게 사용된다. 

 

 

STL deque은 독특하게도

중간에 insert를 통해서 원소를 삽입 할수도 있고, 

iterator 를 통해서 원소에 개별적 접근을 할 수 있다. 

그래서 거의 vector와 같아보이기도 하는데,

차이점이라면 vector는 메모리에 원소의 연속적이게 저장되어있고,

deque는 그렇지 않다는 것이다.

 배열이나 vector나 메모리에 원소의 연속적인 배치가 특징인거고

deque는 그렇지 않다. 

 

 

1021번: 회전하는 큐 

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n, m;
	deque<int> DQ;
	for (int i = 1; i <= n; i++) DQ.push_back(i);
	int ans = 0;
	while (m--)
	{
		int t;
		cin >> t;
		int idx = find(DQ.begin(), DQ.end(), t) - DQ.begin();//idx:t가 있는 위치
		while (DQ.front() != t)
		{
			if (idx < DQ.size() - idx)
			{
				DQ.push_back(DQ.front());
				DQ.pop_front();
			}
			else {
				DQ.push_front(DQ.back());
				DQ.pop_back();
			}
			ans++;
		}
		DQ.pop_front();
	}
	cout << ans;
}

//20번째 줄에서, 지금은 idx가 항상 DQ.size()보다 작아서 문제가 없지만
//DQ.size()는 unsigned int(or unsigned long long) 이기 때문에
//만약 idx가 DQ.size()보다 컸다면 overflow 가 발생해
//의도한대로 동작하지 않을 수 있음을 인지해야 한다. 그래서 size()로
//받아온 값에 대해서는 안전하게 (int)DQ.size()로 항상 형변환을 하는것도
//괜찮다.

이 문제에서 내가 알고 있어야 하는 사항을 보자면, find(iterator p, iterator q, t)의 문법을 이해해야 한다. 

여기서 결국 find가 반환하는건 반복자이고, 반복자에서 DQ.begin(); 반복자를 뺐고 

그 위치의 차이만큼을 int idx에 넣어준거다

https://modoocode.com/261

C++ 레퍼런스 - find 함수 (<algorithm>)

find에 대해서 참고할만한 내용을 첨부한다. 

<algorithm>헤더에 있는 find

 

이 find는 <algorithm>헤더에 있는 find이고, 이건 string의 find 함수와는 다르다. 주의를 해야한다. 

이 find는 iterator에 관련된 find이고, 반환값도 iterator 값이다. 

보면 비교하는 값이 [first,last)까지이고, 있으면 그 iterator를, 없으면 last를 반환한다. 없다면 만약 last에 있는건데 [ ) 형태라 마지막은 제외된다면, 없으므로 마지막은 last iterator가 반환되면서 의도한 바대로 출력하게 된다.