[C++ 자료구조] STL deque

"deque" 디큐가 아니다. 덱이라고 부른다.

 

deque를 사용하여, queue와 stack을 구현할 수 있다.

 

STL에 queue와 stack 이 있는데, 왜 따로 구현하냐고?

 

http://www.cplusplus.com/reference/queue/queue/

queue - C++ Reference

http://www.cplusplus.com/reference/stack/stack/

stack - C++ Reference

 

위 링크에서 STL의 queue, stack이 지원하는 함수를 살펴보면, element access 를 지원하지 않는다.

 

뭐 element access 필요 없을 수도 있다.

 

그러나, 연산 후 남아 있는 queue의 값을 print 하거나

 

연산 후 두개의 queue를 비교할 때 유용할 수 있다.

 

 

1. element access with deque

 
#include <iostream>
#include <deque>
#include <string>
 
using namespace std;
 
struct Data
{
    int value;
    string name;
    
    Data(int v, string n) : value(v), name(n) {}
};
 
deque<Data> queue;
 
int main()
{
    // using deqeue for queue
    queue.push_back(Data(1, "charsy"));
    queue.push_back(Data(2, "merry"));
    queue.push_back(Data(3, "sumy"));
    queue.push_back(Data(4, "sunny"));
    queue.push_back(Data(5, "farng"));
    queue.push_back(Data(6, "strew"));
    queue.push_back(Data(7, "macy"));
    queue.push_back(Data(8, "salon"));
    queue.push_back(Data(9, "tue"));
    queue.push_back(Data(10, "neggy"));
    
    // print only
    for(int i=0; i<queue.size(); i++)
    {
        Data el = queue[i];
        cout << el.value << ", " << el.name << endl;
    }
    
    // pop & print
    while(!queue.empty())
    {
        Data out = queue.front();
        queue.pop_front();
        cout << out.value << ", " << out.name << endl;
    }
    
}

 

 

다음으로 sort 다.

 

sort 가 종종 필요한 경우가 있는데, 아래와 같이 적용할 수 있다.

 

#include <algorithm> 을 헤더에 넣고, sort() 함수를 사용한다.

 

단, 정렬을 위한 함수를 하나 만들어 주어야 한다.

 

아래 예제는 Data 비교시, 

 

1. 우선, name(string) 을 비교하여 오름차순

2. name(string) 이 동일한 경우, value(int)를 비교하여 오름차순

 

을 기준하고 있다.

 

comp 함수를 참고하라.

 

2. sort with deque

 
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
 
using namespace std;
 
struct Data
{
    int value;
    string name;
    
    Data(int v, string n) : value(v), name(n) {}
};
 
deque<Data> queue;
 
 
bool comp(Data e1/*big*/, Data e2/*small*/)
{
    if (e1.name > e2.name)
    {
        return true;
    }    
    else
    {
        if (e1.name == e2.name && e1.value > e2.value)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
        
}
 
int main()
{
    // using deqeue for queue
    queue.push_back(Data(7, "charsy"));
    queue.push_back(Data(2, "sunny"));
    queue.push_back(Data(1, "charsy"));
    queue.push_back(Data(4, "sunny"));
    queue.push_back(Data(5, "farng"));
    queue.push_back(Data(3, "charsy"));
    queue.push_back(Data(7, "macy"));
    queue.push_back(Data(4, "salon"));
    queue.push_back(Data(9, "tue"));
    queue.push_back(Data(10, "sunny"));
 
    sort(queue.begin(), queue.end(), comp);
    
    // print only
    for(int i=0; i<queue.size(); i++)
    {
        Data el = queue[i];
        cout << el.value << ", " << el.name << endl;
    }
 
}