数据结构课程设计题目十二_计算机学院学生会的打印机（优先队列）

本文出自:http://blog.csdn.net/svitter

题目12：计算机学院学生会的打印机（优先队列）

小明抱怨学生会的打印机不符合FIFO的原则，看到很多在他后面来打印的同学比他先打印出来。五分钟前，小明的文件就是下一个候选的，如今小明的文件又排到了后面。学生会的同学给小明解释说，学生会的打印机不是採用传统的队列方式，而是採用一种自定义的优先队列方式：每一个要打印的文件被赋予了一个从1到9的优先级（9最高，1最低）。打印规定例如以下：

将队列中要打印的文件f从队列中拿出来；

假设在队列中有优先级高于f的文件，则不打印f，将f排到队列的最后；否则打印f。

小明知道打印新规以后，询问他的文件到底多长时间可以打印出来，如果没分文件打印的时间都是1分钟，小明的文件在打印队列中，而且不再有新的文件进入到打印队列。请你帮助小明计算一下他还须要等多长时间。建议完毕人数1人。

加入了小元素的筛选代码

PriorityQueue.cpp:

//============================================================================
// Name        : PriorityQueue.cpp
// Author      : vit
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include "Queue.h"
using namespace std;

int main() {
	Queue *q;
	q = new Queue();
	int i;
	int n, m, val, num;
        int mval;
	Node *p;
	freopen("test", "r", stdin);
	while(~scanf("%d%d", &n, &m))
	{
		num = 1;
		for(i = 1; i <= n; i++)
		{
			scanf("%d", &val);
			//printf("第%d号正在增加队列...\n", i);
			p = new Node(val, NULL, i);
                        if(i == m)
                        {
                               mval = val;
                        }
			q->push(p);
		}
                q->check(mval);


		//printf("队列增加完毕。\n");
		while(!q->IsEmpty())
		{
			p = q->top();
			//printf("当前打印的是第%d号\n", p->num);
			if(p->num == m)
			{
				printf("小明在第%d分钟打印。\n", num);
			}
			q->pop();
			num++;
		}
	}
	return 0;
}

Queue.cpp:

/*
 * Queue.cpp
 *
 *  Created on: 2014Äê6ÔÂ15ÈÕ
 *      Author: vit
 */

#include <stdio.h>
#include "Queue.h"

Queue::Queue() {
	// TODO Auto-generated constructor stub
	this->front = this->rear = NULL;
}

bool Queue::IsEmpty(){
	return this->rear == NULL;
}

void Queue::push(Node *n){
	if(IsEmpty())
	{
		this->front = this->rear = n;
	}
	else
	{
		this->rear->next = n;
		this->rear = n;
	}
	return;
}

void Queue::pop(){
	if(IsEmpty())
	{
		return;
	}
	Node *p = this->front;
	if(this->front == this->rear)
	{
		p = this->front;
		this->front = this->rear = NULL;
	}
	else
	{
		p = this->front;
		this->front = this->front->next;
	}
	delete p;
}

Node * Queue::top(){
	if(IsEmpty()){
		return NULL;
	}
	int value = this->front->value;
	Node *p = this->front;
	while(p->next != NULL)
	{
		if(p->next->value <= value)
			p = p->next;
		else
		{
			this->rear->next = this->front;
			this->rear = p;
			this->front = p->next;
			p->next = NULL;
			p = this->front;
			value = p->value;
		}
	}
	return this->front;
}

void Queue::check(int mval)
{
    Node *p = this->front;
    Node *temp;
    while(p->next != NULL)
    {
        if(p->next->value < mval)
        {
            temp = p->next;
            p->next = p->next->next;
            delete temp;
        }
        //p指向下一个节点
        p = p->next;
    }
}


Queue::~Queue() {
	// TODO Auto-generated destructor stub
	while(!IsEmpty())
	{
		Node *temp;
		temp = this->front;
		this->front= this->front->next;
		delete temp;
	}
}

Queue.h:

/*
 * Queue.h
 *
 *  Created on: 2014年6月15日
 *      Author: vit
 */

#ifndef QUEUE_H_
#define QUEUE_H_


class Node
{
public:
    int value;
    int num;
    Node *next;
    Node()
    {
        this->value = 0;
        this->num = 0;
        this->next = 0;
    }
    Node(int value, Node *next, int num)
    {
        this->value = value;
        this->next = next;
        this->num = num;
    }
};

class Queue
{
public:
    Queue();
    virtual ~Queue();

    //method
    void push(Node *n);
    void pop();
    Node* top();
    bool IsEmpty();
    void check(int mval);

    //member
    Node *front;
    Node *rear;
};
#endif /* QUEUE_H_ */