C Programming :: Queue

<C언어>

//배열로구현된원형큐프로그램

#include <stdio.h>

#include <stdlib.h>

     

#define MAX_QUEUE_SIZE 100

typedef int element;

typedef struct QueueType{

    element queue[MAX_QUEUE_SIZE];

    int front, rear;

}QueueType;

void error(char *message)

{

    fprintf(stderr,"%s\n",message);

    exit(1);

}

void init(QueueType *q)

{

    q->front = q->rear = 0;

}

int is_full(QueueType *q)

{

    return (q->front == (q->rear +1)%MAX_QUEUE_SIZE);

}

int is_empty(QueueType *q)

{

    return q->front == q->rear;

}

void enqueue(QueueType *q, element item)

{

    if(is_full(q)){

        error("큐포화에러\n");

    }

    else{

        q->rear = (q->rear + 1)% MAX_QUEUE_SIZE;    //이렇게안하면증가하지않는다.

        q->queue[q->rear] = item;

    }

}

element dequeue(QueueType *q)

{

    if(is_empty(q)){

        error("큐공백에러\n");

    }

    else{

        q->front = (q->front +1)%MAX_QUEUE_SIZE;

        return q->queue[q->front];

    }

}

element peek(QueueType *q)

{

    if(is_empty(q)){

        error("큐공백에러\n");

    }

    else{

        return q->queue[(q->front+1)%MAX_QUEUE_SIZE];

    }

}

void main()

{

    QueueType q;

    init(&q);

    printf("front=%d, rear=%d\n",q.front, q.rear);

    enqueue(&q, 1);

    enqueue(&q, 2);

    enqueue(&q, 3);

    printf("dequeue()=%d\n",dequeue(&q));

    printf("dequeue()=%d\n",dequeue(&q));

    printf("dequeue()=%d\n",dequeue(&q));

    printf("front=%d rear=%d\n",q.front, q.rear);

}

     

     

//연결리스트로구현된큐

#include <stdio.h>

#include <stdlib.h>

     

typedef int element;

typedef struct queue_node{

    element item;

    queue_node *link;

}queue_node;

     

typedef struct LinkedQueue{

    queue_node *front;

    queue_node *rear;

}LinkedQueue;

void error(char *message)

{

    fprintf(stderr,"%s\n",message);

    exit(1);

}

void init(LinkedQueue* q)

{

    q->front = q->rear = NULL;

}

int is_empty(LinkedQueue *q)

{

    return q->front == NULL;

}

int is_full(LinkedQueue *q)

{

    return 0;

}

void enqueue(LinkedQueue *q, element item)

{

    queue_node *new_queue = (queue_node *)malloc(sizeof(queue_node));

    if(new_queue == NULL) error("메모리를할당할수없습니다.");

    else{

        new_queue->item = item;

        new_queue->link = NULL;

        if(is_empty(q)){

            q->front = new_queue;

            q->rear = new_queue;

        }

        else{

            q->rear->link = new_queue;

            q->rear = new_queue;

        }

    }

}

element dequeue(LinkedQueue *q)

{

    queue_node *temp = q->front;

    element item;

    if(is_empty(q)) error("큐공백에러\n");

    else{

        //queue_node *temp = (queue_node *)malloc(sizeof(queue_node)); 이럴필요없음

        item = temp->item;

        q->front = q->front->link;

        if(q->front == NULL)

            q->rear = NULL;    //q->rear는메모리에남아있다?!

        free(temp);

        return item;

    }

}

element peek(LinkedQueue *q)

{

    if(is_empty(q)) error("큐공백에러\n");

    else

    {

        return q->front->item;

    }

}

void main()

{

    LinkedQueue q;

    init(&q);

     

    enqueue(&q, 1);

    enqueue(&q, 2);

    enqueue(&q, 3);

    printf("dequeue()=%d\n",dequeue(&q));

    printf("dequeue()=%d\n",dequeue(&q));

    printf("dequeue()=%d\n",dequeue(&q));

}

     

     

//이중연결리스트로구현된deque(덱)

#include <stdio.h>

#include <stdlib.h>

     

typedef int element;

typedef struct DlistNode{    //노드의타입

    element data;

    struct DlistNode *rlink;

    struct DlistNode *llink;

}DlistNode;

typedef struct DequeType{    //덱의타입

    DlistNode *head;

    DlistNode *tail;

}DequeType;

void error(char *message)

{

    fprintf(stderr,"%s\n",message);

    exit(1);

}

void init(DequeType *dq)

{

    dq->head = dq->tail = NULL;

}

int is_empty(DequeType *dq)

{

    return dq->head == NULL;

}

int is_full(DequeType *dq)

{

    return 0;

}

/*

DlistNode* create_node(element item)

{

    DlistNode *new_node = (DlistNode* )malloc(sizeof(DlistNode));

    if(new_node == NULL) error("메모리할당실패\n");

    new_node->data = item;

    new_node->rlink = NULL;    

    new_node->llink = NULL;

    return new_node;

}*/

DlistNode* create_node(DlistNode* llink, element item, DlistNode* rlink)

{

    DlistNode *new_node = (DlistNode*)malloc(sizeof(DlistNode));

    if(new_node == NULL) error("메모리할당실패\n");

    new_node->llink = llink;        //좀더효율적일수있겠군

    new_node->rlink = rlink;

    new_node->data = item;

    return new_node;

}

void add_front(DequeType *dq, element item)    

{

    DlistNode *new_node = create_node(NULL, item, dq->head);    //요걸해주면new_node에대해선안건드려도되는군

    if(is_empty(dq)){

        dq->tail = new_node;

    }

    else{

        dq->head->llink = new_node;

    }

    dq->head = new_node;

        

}

void add_rear(DequeType *dq, element item)

{

    DlistNode *new_node = create_node(dq->tail, item, NULL);

    if(is_empty(dq)){

        dq->head = new_node;

    }

    else{

        dq->tail->rlink = new_node;

    }

    dq->tail = new_node;

}

/*

void add_front(DequeType *dq, element item)

{

    DlistNode *new_node = create_node(item);

    if(is_empty(dq)){

        dq->head = new_node;

        dq->tail = new_node;

    }

    else{

        new_node->rlink = dq->head;

        dq->head->llink = new_node;

        dq->head = new_node;

    }

}

void add_rear(DequeType *dq, element item)

{

    DlistNode *new_node = create_node(item);

    if(is_empty(dq)){

        dq->head = new_node;

        dq->tail = new_node;

    }

    else{

        dq->tail->rlink = new_node;

        new_node->llink = dq->tail;

        dq->tail = new_node;

    }

}

*/

element delete_front(DequeType *dq)

{

    element item;

    DlistNode* tmp;

    if(is_empty(dq)) error("덱공백에러\n");

    else{

        tmp = dq->head;

        item = tmp->data;

        dq->head = tmp->rlink;

        free(tmp);

        if(dq->head == NULL)

            dq->tail = NULL;

        else

            dq->head->llink = NULL;

    }

    return item;

}

element delete_rear(DequeType *dq)

{

    element item;

    DlistNode* tmp;

    if(is_empty(dq)) error("덱공백에러\n");

    else{

        tmp = dq->tail;

        item = tmp->data;

        dq->tail = tmp->llink;

        free(tmp);

        if(dq->tail == NULL)

            dq->head = NULL;

        else

            dq->tail->rlink = NULL;

    }

    return item;

}

/*

element delete_front(DequeType *dq)

{

    element item;

    DlistNode *tmp = dq->head;

    if(tmp == NULL) error("덱공백에러\n");

    else{

        item = tmp->data;

        dq->head = tmp->rlink;

        dq->head->llink = NULL;

        free(tmp);

        if(dq->head == NULL)

            dq->tail = NULL;

        return item;

    }

}

element delete_rear(DequeType *dq)

{

    element item;

    DlistNode *tmp = dq->tail;

    if(tmp == NULL) error("덱공백에러\n");

    else{

        item = tmp->data;

        dq->tail = tmp->llink;

        dq->tail->rlink = NULL;

        free(tmp);

        if(dq->tail == NULL)

            dq->head = NULL;

        return item;

    }

}

*/

void display(DequeType *dq)

{

    DlistNode *tmp = dq->head;

    if(tmp == NULL) error("덱공백에러\n");

    else{

        while(tmp != NULL)

        {

            printf("%d->",tmp->data);

            tmp = tmp->rlink;

        }

        printf("\n");

    }

}

void main()

{

    DequeType deque;

     

    init(&deque);

    add_front(&deque, 10);

    add_front(&deque, 20);

    add_rear(&deque, 30);

    display(&deque);

     

    delete_front(&deque);

    delete_rear(&deque);

    display(&deque);

     

}

     

     

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

   

#define TRUE 1

#define FALSE 0

#define MAX_QUEUE_SIZE 100

typedef struct{

    int id;

    int arrival_time;

    int service_time;

}element;

   

typedef struct{

    element queue[MAX_QUEUE_SIZE];

    int front, rear;

}QueueType;

QueueType queue;

   

void error(char *message)

{

    fprintf(stderr,"%s\n",message);

    exit(1);

}

void init(QueueType *q)

{

    q->front = q->rear = 0;

}

//공백상태검출함수

int is_empty(QueueType *q)

{

    return q->front == q->rear;

}

//포화상태검출함수

int is_full(QueueType *q)

{

    return q->front == (q->rear+1)%MAX_QUEUE_SIZE;

}

//삽입함수

void enqueue(QueueType *q, element item)

{

    if(is_empty(q)){

        q->queue[(q->rear+1)%MAX_QUEUE_SIZE] = item;

        q->rear = (q->rear+1)%MAX_QUEUE_SIZE;

    }

    else{

        if(is_full(q)) error("큐포화에러\n");

        else{

            q->queue[(q->rear+1)%MAX_QUEUE_SIZE] = item;

            q->rear = (q->rear+1)%MAX_QUEUE_SIZE;

    }

}

element dequeue(QueueType *q)

{

    if(is_empty(q)) error("큐공백에러\n");

          

    q->front = (q->front+1)%MAX_QUEUE_SIZE;

          

    return q->queue[q->front];

}

   

element peek(QueueType *q)

{

    if(is_empty(q)) error("큐공백에러\n");

    else{

        return q->queue[(q->front+1)%MAX_QUEUE_SIZE];

    }

}

//0에서1사이의실수난수생성함수

double random()

{

    return rand()/(double) RAND_MAX;

}

//시뮬레이션에필요한여러가지상태변수

int duration = 10;    //시뮬레이션시간

double arrival_prob = 0.7;    //하나의시간단위에도착하는평균고객의수

int max_serv_time = 5;    //하나의고객에대한최대서비스시간

int clock;

   

//시뮬레이션의결과

int customers=0;    //전체고객수

int served_customers=0;    //서비스받은고객수

int waited_time=0;        //고객들이기다린시간

   

//랜덤숫자를생성하여고객이도착했는지도착하지않았는지를판단

int is_customer_arrived()

{

    if(random() < arrival_prob)

        return TRUE;

    else return FALSE;

}

//새로도착한고객을큐에삽입

void insert_customer(int arrival_time)

{

    element customer;

   

    customer.id = customers++;

    customer.arrival_time = arrival_time;

    customer.service_time = (int)(max_serv_time*random()) + 1;

    enqueue(&queue,customer);

    printf("고객%d이%d분에들어옵니다. 서비스시간은%d분입니다.\n",customer.id, customer.arrival_time, customer.service_time);

}

//큐에서기다리는고객을꺼내어고객의서비스시간을반환한다.

int remove_customer()

{

    element customer;

    int service_time=0;

   

    if(is_empty(&queue)) return 0;

    customer = dequeue(&dequeue);

    service_time = customer.service_time -1;

    served_customers++;

    waited_time += clock - customer.arrival_time;

    printf("고객%d이%d분에서비스를시작합니다. 대기시간은%d분이었습니다.\n",customer.id, clock, clock - customer.arrival_time);

    return service_time;

}

//통계치를출력한다.

void print_stat()

{

    printf("서비스받은고객수= %d\n", served_customers);

    printf("전체대기시간= %d분\n",waited_time);

    printf("1인당평균대기시간= %f분\n",(double)waited_time/served_customers);

    printf("아직대기중인고객수= %d\n",customers-served_customers);

}

   

void main()

{

    int service_time = 0;

      

    clock = 0;

    while(clock < duration){

        clock++;

        printf("현재시각=%d\n",clock);

        if(is_customer_arrived()){

            insert_customer(clock);

        }

        if(service_time >0)

            service_time--;

        else{

            service_time = remove_customer();

        }

    }

    print_stat();

}

 

 

---------------------<C ++>---------------------------------

 

//배열로구현된큐

 

#include <iostream>

 

using namespace std;

 

class Queue{

public:

    Queue(int queueCapacity = 10);

    //처음에크기가queueCapacity인공백큐를생성

    

    inline int getFront(){return front;}

    inline int getRear(){return rear;}

 

    inline bool IsEmpty() const{return front == rear;}

    //큐의원소수가0이면treu, 아니면false를반환

 

    int& Front() const;

    //큐의앞에있는원소를반환

 

    int& Rear() const;

    //큐의뒤에있는원소를반환

 

    void Push(const int& item);

    //큐의뒤에item을삽입

 

    void Pop();

    //큐의앞원소를삭제

private:

    int* queue;    //큐원소를위한배열

    int front,    //첫번째원소로부터반시계방향으로한위치뒤

        rear,    //마지막원소의위치

        capacity;    //큐배열의크기

};

Queue::Queue(int queueCapacity):capacity(queueCapacity)

{

    if(queueCapacity < 0) throw "Queue capacity must be > 0";

    queue = new int[capacity];

    rear = front = 0;

}

//큐의앞에있는원소를반환

int& Queue::Front() const

{

    if(IsEmpty()) throw "Queue is empty. No front element";

    return queue[(front+1)%capacity];

}

int& Queue::Rear() const

{

    if(IsEmpty()) throw "Queue is empty. No rear element";

    return queue[rear];    

}

/*

void ChangeSizeID(int*& a,const int oldSize,const int newSize)

{

    if(newSize <0) throw "newSize >0";

    

    int* temp = new int[newSize];    //새로운배열까먹음

    int number = min(oldSize, newSize);    //복사할원소수

    copy(a,a+number,temp);    //이것도틀리구요.

    delete []a;        //까먹고이전메모리제거

    a = temp;        //까먹음

 

}

*/

 

void Queue::Push(const int& item)    //IsEmpty()할필요가없나?

{

    if((rear+1)%capacity == front)

    {/*

        ChangeSizeID(queue,capacity,2*capacity);

        capacity *=2;    //이거까먹었네. */

        //두배크기의배열을할당

        int* newQueue = new int[2*capacity];

        

        //queue를newQueue로복사

        int start = (front+1)%capacity;

        if(start<2)        //이건왜또?

            copy(queue+start, queue+start+ capacity-1,newQueue);    //copy(시작주소, 마지막까지,,새로운것)

        else

        {

            copy(queue+start, queue+capacity,newQueue);                //여기모르겠다.

            copy(queue,queue+rear+1, newQueue + capacity-start);    //여기도모르겠다.

        }

        //newQueue로전환

        front = 2*capacity -1;

        rear = capacity -2;

        capacity*=2;

        delete[] queue;

        queue= newQueue;

 

    }

    rear = (rear+1)%capacity;

    queue[rear] = item;

}

void Queue::Pop()

{

    if(IsEmpty()) throw " Queue is empty!";

    front = (front+1)%capacity;

    //queue[front].~T();    //T를위한소멸자<- 이거아직도모르겠다.

}

 

void main()

{

Queue q;

    cout<<"front="<<q.getFront()<<" rear="<<q.getRear()<<endl;

    q.Push(1);

    q.Push(2);

    q.Push(3);

    q.Push(1);

    q.Push(2);

    q.Push(3);

    q.Push(1);

    q.Push(2);

    q.Push(3);

    q.Push(1);

    q.Push(2);

    q.Push(3);

    q.Push(1);

    q.Push(2);

    q.Push(3);

    cout<<"Pop()="<<q.Front()<<endl;

    q.Pop();

    cout<<"Pop()="<<q.Front()<<endl;

    q.Pop();

    cout<<"Pop()="<<q.Front()<<endl;

    q.Pop();

    cout<<"front="<<q.getFront()<<" "<<"rear="<<q.getRear()<<endl;

    /*

enqueue(&q, 1);

enqueue(&q, 2);

enqueue(&q, 3);

printf("dequeue()=%d\n",dequeue(&q));

printf("dequeue()=%d\n",dequeue(&q));

printf("dequeue()=%d\n",dequeue(&q));

printf("front=%d rear=%d\n",q.front, q.rear); */

}