队列和优先级队列的简单实现

//普通顺序队列的实现

/*
 * 2008/06/20 By YaoJianming
 */
#include
#include
#include

#define maxsize 1000
enum status {empty, full, ok};

struct queue {
    int queue[maxsize];
    int front;
    int rear;
};

void initqueue(queue* &q)
{
    q = (queue*)malloc(sizeof(queue));
    q->front = 0;
    q->rear = 0;
}

status addqueue(queue *q, int value)
{
    if((q->rear+1)%maxsize == q->front)
        return full;
    q->queue[q->rear] = value;
    q->rear = (q->rear+1)%maxsize;
    return ok;
}

status delqueue(queue *q, int *value)
{
    if(q->front == q->rear)
        return empty;
    *value = q->queue[q->front];
    q->front = (q->front+1)%maxsize;
    return ok;
}

void print(queue *q)
{
    for(int i=q->front; irear; ++i) {
        printf("%d ", q->queue[i]);
    }
}

int main()
{
    queue *q;
    initqueue(q);
    for(int i=0; i<100; ++i) {
         status ret = addqueue(q, i);
         if(ret == full) {
             printf("queue full\n");
             exit(1);
         }
    }
    for(int j=0; j<30; ++j) {
        int num;
        status ret = delqueue(q, &num);
        if(ret == empty) {
            printf("queue empty\n");
            exit(1);
        }
    }
    print(q);
    return 0;
}

 

//简单优先级队列的实现

/*
 * 2008/06/20 By Yao Jianming
 * */

#include
#include
#include
using std::string;

static const unsigned int sizes[] = {
    53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
    196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
    50331653, 100663319, 201326611, 402653189, 805306457, 1610612741
};

struct queue {
        int *data;
        int size;
        int index;
};

void init_queue(queue *q)
{
        q->size = 0;
        q->index = 0;
        q->data = (int*)malloc(sizes[q->index]);
}

void add_queue(queue *q, int value)
{
        if((q->size+1) == sizes[q->index]) {
                int w[q->size+1];
                memcpy(w, q->data, (q->size+1)*sizeof(int));
                q->data = (int*)malloc(sizes[++q->index]);
                memcpy(q->data, w, (q->size+1)*sizeof(int));
        }
        q->size++;
        int i;
        for(i=q->size; i/2>0 && q->data[i/2]>value; i/=2) {
                q->data[i] = q->data[i/2];
        }
        q->data[i] = value;
}

int del_queue(queue *q)
{
        if(q->size < sizes[q->index-1]) {
                int w[q->size];
                memcpy(w, q->data, (q->size+1)*sizeof(int));
                q->data = (int*)malloc(sizes[--q->index]);
                memcpy(q->data, w, (q->size+1)*sizeof(int));
        }
        int value = q->data[1];
        q->data[1] = q->data[q->size];
        int i=1;
        while(2*i < q->size) {
                int min = q->data[2*i] < q->data[2*i+1] ? q->data[2*i] : q->data[2*i+1];
                int pos = q->data[2*i] < q->data[2*i+1] ? (2*i) : (2*i+1);
                if(q->data[i] > min) {
                        int tmp = q->data[i];
                        q->data[i] = min;
                        q->data[pos] = tmp;
                        i = pos;
                } else {
                        break;
                }
        }
        q->size--;
        return value;
}

void print_queue(queue *q)
{
        for(int i=1; isize; ++i) {
                printf("%d ", q->data[i]);
        }
        printf("\n");
}

int main()
{
        queue s;
        init_queue(&s);
        for(int i=100; i>=1; --i) {
                add_queue(&s, i);
        }
        while(s.size > 0) {
                int value = del_queue(&s);
                printf("%d ", value);
        }
}