STL 의 stack & quue & priorityqueue 스 택, 대기 열 및 우선 대기 열

4820 단어 STL기초
스 택, 대기 열 과 우선 대기 열 은 모두 용기 어댑터 에 속 합 니 다. 즉, 기 존의 STL 용기 류 의 템 플 릿 류 를 패키지 하여 서로 다른 기능 을 제공 합 니 다. 보통 제한 적 인 기능 을 제공 합 니 다. 아래 부분 은 세 가지 특수 한 데이터 구조 에 대한 용법 요약 입 니 다.
하나.
stack 템 플 릿 클래스 의 정 의 는 헤더 파일 에 있 습 니 다.스 택 이란 후진 선 출 데이터 구조 에 부합 하 는 것 이다.stack 템 플 릿 류 는 두 개의 템 플 릿 매개 변수 가 필요 합 니 다. 하 나 는 요소 형식 이 고 하나의 용기 유형 이지 만 요소 유형 만 필요 합 니 다. 용기 유형 을 지정 하지 않 을 때 기본 용기 유형 은 deque 입 니 다.stack 대상 을 정의 하 는 예제 코드 는 다음 과 같 습 니 다: stack s1;stack s2; stack 의 기본 동작 은 다음 과 같 습 니 다. 예 를 들 어 s. push (x);스 택 을 나 갑 니 다. 예 를 들 어 s. pop ();스 택 작업 은 스 택 상단 요 소 를 삭제 할 뿐 이 요 소 를 되 돌려 주지 않 습 니 다.스 택 꼭대기 에 접근 합 니 다. 예 를 들 어 s. top () 은 스 택 이 비어 있 는 것 을 판단 합 니 다. 예 를 들 어 s. empty () 는 스 택 이 비어 있 을 때 true 로 돌아 갑 니 다.스 택 에 있 는 요소 갯 수 를 방문 합 니 다. 예 를 들 어 s. size ().
stacka [100] 동작 지원
int main()
{
    stacka[100];
    a[0].push(1);
    a[0].push(2);
    cout<

둘.
queue 템 플 릿 클래스 의 정 의 는 헤더 파일 에 있 습 니 다.대기 열 은 선진 적 인 선 출 원칙 인 quue 템 플 릿 류 에 도 두 개의 템 플 릿 매개 변수 가 필요 합 니 다. 하 나 는 요소 유형 이 고 하나의 용기 유형 이 며 요소 유형 은 필요 합 니 다. 용기 유형 은 선택 할 수 있 습 니 다. 기본 값 은 deque 형식 입 니 다.
queue 대상 을 정의 하 는 예제 코드 는 다음 과 같 습 니 다.
queue q1;
queue q2;
queue >q3;
queue 의 기본 동작 은 다음 과 같 습 니 다. 예 를 들 어 q. push (x);x 를 대기 열의 끝 에 받 습 니 다.예 를 들 어 q. pop ();팝 업 팀 의 첫 번 째 요 소 는 팝 업 된 요소 의 값 을 되 돌려 주지 않 습 니 다.방문 팀 의 첫 번 째 요소, 예 를 들 어 q. front (), 즉 최초 로 대기 열 에 눌 린 요소 입 니 다.예 를 들 어 q. back (), 즉 마지막 으로 대기 열 에 눌 린 요소 입 니 다.대기 열 이 비어 있 는 지 판단 합 니 다. 예 를 들 어 q. empty (), 대기 열 이 비어 있 을 때 true 로 돌아 갑 니 다.대기 열 에 있 는 요소 갯 수 에 접근 합 니 다. 예: q. size ()
queuea [100] 동작 이 지원 되 지 않 습 니 다.
int main()
{
    queue Q;
    Q.push(1);
    Q.push(2);
    Q.push(3);
    while(!Q.empty()){
        cout<

출력:
1------3 2------3 3------3
셋.
헤더 파일 에 서 는 또 다른 유용 한 템 플 릿 류 priority 를 정의 합 니 다.queue (우선 대기 열). 우선 대기 열과 대기 열의 차 이 는 우선 대기 열 이 입 대 된 순서대로 나 오 는 것 이 아니 라 대기 열 에 있 는 요소 의 우선권 순서에 따라 나 오 는 것 이다.. 맨 위 에는 항상 가장 큰 우선 순위 가 있 습 니 다. quue 와 달리 대기 열 백 엔 드 에 접근 할 수 없 기 때문에 팀 을 나 가 는 방법 은 quue 의 front 에서 top () 으로 바 뀌 었 습 니 다."priority queue 템 플 릿 류 는 세 개의 템 플 릿 매개 변수 가 있 습 니 다. 첫 번 째 는 요소 유형, 두 번 째 용기 유형, 세 번 째 는 비교 연산 자 입 니 다. 그 중에서 두 개 는 모두 생략 할 수 있 습 니 다. 기본 용 기 는 vector 이 고 기본 연산 자 는 less 입 니 다. 마치 큰 꼭대기 더미 처럼 우선 순위 가 작 을 수록 아래 에 있 고 우선 순위 가 높 은 것 은 더미 위 에 있 습 니 다. 이렇게 이해 할 수 있 습 니 다. 즉, 작은 앞줄, 큰 것 입 니 다."뒤로 줄 을 서 세 요. (줄 을 서 있 을 때 꼬리 요소 가 줄 을 서 있 습 니 다.) priority quue 대상 을 정의 하 는 예제 코드 는 다음 과 같 습 니 다. priority quue q1; / / 작 을 수록 정수 우선 순위 가 낮 습 니 다 priority quue < pair > q2; priority quue, greater > q3; / 작 을 수록 정수 우선 순위 가 큽 니 다.
priority queue 의 기본 동작
예 를 들 어 q. push (x), x 를 대기 열의 끝 에 받 습 니 다. 예 를 들 어 q. pop (), 팝 업 팀 의 첫 번 째 요 소 는 팝 업 요소 의 값 을 되 돌려 주지 않 습 니 다. 방문 팀 의 첫 번 째 요 소 는 예 를 들 어 q. top (), 즉 우선 순위 가 가장 높 은 요소 판단 팀 이 비어 있 습 니 다. 예 를 들 어 q. empty (), 대기 열 이 비어 있 을 때 true 를 되 돌려 줍 니 다. 대기 열 에 있 는 요소 갯 수 를 방문 합 니 다. 예: q. size ()
priorrity_queue,cmp>q4;//  cmp          

struct cmp{

bool operator()(const int a,const int b)const {  //     cmp,  ()   。

return a>b;
}
};
         ,            ,     STL  less    greater
  ——     less   ,      ,     。
            ,     ,         :       。   
        x  y        ( less   ,  xy),
     , x   y   ,y    x   ,  ,  y   x   ,x     。
          :
#include 

#include 
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator < (const T &t1, const T &t2)
{
return t1.z < t2.z; //   z       t1  t2    
}
main()
{
priority_queue q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 1;
}
     (     z           ):
3 3 6
2 2 5
1 5 4
4 4 3
      z             :
#include 
#include 
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator > (const T &t1, const T &t2)
{
return t1.z > t2.z;
}
main()
{
priority_queue, greater > q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 1;
}
     :
4 4 3
1 5 4
2 2 5
3 3 6
                    :
bool operator < (const T &t1, const T &t2)
{
return t1.z > t2.z; //   z       t1  t2    
}
                            。

참고 블 로그:http://www.cnblogs.com/mfryf/archive/2012/08/09/2629992.html

좋은 웹페이지 즐겨찾기