데이터 구조 (3) -- 대기 열

1. 선형 저장 소

//Queue.h

#ifndef QUEUE_H_

#define QUEUE_H_

#define ElemType int 

#define MAXSIZE 100

typedef struct _Node

{

    ElemType data[MAXSIZE];

    int front;

    int rear;

    

}Node;



class Queue

{

private:

    Node data;

public:

    Queue();

    ~Queue();

    void EnQueue(ElemType e);

    ElemType DeQueue();

    int IsFull();

    int IsEmpty();

};



#endif





//Queue.cpp

#include "Queue.h"

#include <iostream>



Queue::Queue()

{

    data.front = 0;

    data.rear = 0;

}



Queue::~Queue(){}



void Queue::EnQueue(ElemType e)

{

    if (IsFull())

    {

        std::cout << "    " << std::endl;

        return;

    }

    data.rear = (data.rear + 1) % MAXSIZE;

    data.data[data.rear] = e;

}



ElemType Queue::DeQueue()

{

    if (IsEmpty())

    {

        std::cout << "    " << std::endl;

        return 0;

    }

    data.front = (data.front + 1) % MAXSIZE;

    return data.data[data.front];

}



int Queue::IsFull()

{

    if (data.front % MAXSIZE == (data.rear + 1) % MAXSIZE)

        return 1;

    else

        return 0;

}



int Queue::IsEmpty()

{

    if (data.front == data.rear)

        return 1;

    else

        return 0;

}

 
2. 체인 메모리

//PQueue.h

#ifndef PQUEUE_H_

#define PQUEUE_H_

#define ElemType int 

#define MAXSIZE 100



typedef struct _PNode

{

    ElemType data;

    _PNode *next;

    

}PNode;



class PQueue

{

private:

    PNode *front;

    PNode *rear;



public:

    PQueue();

    ~PQueue();

    void EnQueue(ElemType e);

    ElemType DeQueue();

    int IsFull();

    int IsEmpty();

};



#endif





//PQueue.cpp

#include "PQueue.h"

#include <iostream>



PQueue::PQueue()

{

    front = new PNode();

    rear = front;

    front->next = NULL;

}



PQueue::~PQueue()

{

    delete front;

    delete rear;

}



void PQueue::EnQueue(ElemType e)

{

    PNode *s = new PNode();

    s->data = e;

    rear->next = s;

    s->next = NULL;

    rear = s;

}



ElemType PQueue::DeQueue()

{

    if (IsEmpty())

    {

        std::cout << "    " << std::endl;

        return 0;

    }

    PNode *s;

    s = front;

    ElemType t = s->next->data;

    front = front->next;

    delete s;

    return t;

}



int PQueue::IsEmpty()

{

    if (rear == front)

        return 1;

    else

        return 0;

}

 
3. 테스트 사례

#include <iostream>

#include "PQueue.h"

#include <string>

using namespace std;







int main()

{

    PQueue q;

    for (int i = 0; i < 6; i++)

        q.EnQueue(i);

    for (int i = 0; i < 6; i++)

        cout << q.DeQueue();

    system("pause");

    return 0;

}