C++数据结构之Queue（队列）

Queue，队列，和我们日常生活中的队列是同样的规则，“先进先出”，从尾入，从首出。

Queue，主要有三种基本操作，append（添加元素至队尾）；serve（队首元素出列）；retrieve（查看队首元素）。

有外加的一些操作如 full（队列是否已满），serve_and_retrieve（查看队首元素同时去除）等等。

代码（在eclipse运行通过）：
.h头文件

/*
 * queue.h
 *
 *  Created on: 2015年8月22日
 *      Author: Administrator
 */

#ifndef QUEUE_H_
#define QUEUE_H_

enum Error_code {overflow,underflow,success};
typedef int Queue_entry;
const int maxqueue = 2;

class Queue
{
public:
	Queue();
	bool empty()const;
	Error_code append(const Queue_entry &item); //从队尾入队
	Error_code serve(); //从队首出队
	Error_code retrieve(Queue_entry &item)const; //查看队首元素
	bool full()const; //此处const表示该函数不改变成员变量（属性）
	int size()const;  //同上
	void clear();
	Error_code serve_and_retrieve(Queue_entry &item);
protected:	//protected表示子类可以直接调用下面的成员变量
	int count;
	int front,rear;	//头和尾  for circular implementation
	Queue_entry entry[maxqueue];
};

#endif /* QUEUE_H_ */

.cpp类实现文件

/*
 * queue.cpp
 *
 *  Created on: 2015年8月22日
 *      Author: Administrator
 */
#include "queue.h"

Queue::Queue()
{
	count = maxqueue - 1;
	rear = maxqueue - 1;
	front = 0;
}
bool Queue::empty()const
{
	return count == 0;  // 精辟写法，好比while(n--)
}
Error_code Queue::append(const Queue_entry &item)
{
	if(count >= maxqueue)
		return overflow;
	else
	{
		count++;
		rear = ((rear + 1) == maxqueue)?0:(rear + 1);
		//若加一个刚满则令rear等0，否则+1
		entry[rear] = item;
		return success;
	}
}
Error_code Queue::serve()
{
	if(count == 0)
		return underflow;
	else
	{
		count--;
		front = ((front + 1) == maxqueue)?0:(front + 1);
		return success;
	}
}
Error_code Queue::retrieve(Queue_entry &item)const
{
	if(count <= 0)
		return underflow;
	else
	{
		item = entry[front];
		return success;
	}
}
bool Queue::full()const
{
	return count == maxqueue;
}
int Queue::size()const
{
	return count;
}
void Queue::clear()
{
	count = 0;
}
Error_code Queue::serve_and_retrieve(Queue_entry &item)
{
	if(count == 0)
		return underflow;
	else
	{
		count--;
		item = entry[front];
		return success;
	}
}

main主函数测试文件

/*
 * main.cpp
 *
 *  Created on: 2015年8月23日
 *      Author: 吕奉先
 */

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

void introduction();
char get_command();
bool do_command(char command, Queue &test_queue);

int main()
{
	Queue test_queue;
	introduction();
	while(do_command(get_command(),test_queue));
	return 0;
}

void introduction()
{
	cout<<"Hello. This is Queue-Test in C plus plus. ^_^ "<<endl;
}
void help()
{
	cout<<"Enter 'a' means appending a item to the front of the queue;\n"
		<<"      's' means taking the rear item out from the queue;\n"
		<<"  and 'r' means checking the first item of the queue…\n" //'\n' means newline
		<<"  The last, Enter 'h' for help,'q' for quit."<<endl;
}
char get_command()
{
	char command;
	bool waiting = true;
	cout<<"Select command and press <Enter>: ";
	while(waiting)
	{
		cin>>command;
		command = tolower(command);// 转换为小写字母
		if(command == 'a' || command == 's' ||
		   command == 'r' || command == 'h' ||
		   command == 'b' || command == 'q')
			waiting = false;
		else
		{
			cout<<"Please enter a calid command."<<endl;
		}
	}
	return command;
}
bool do_command(char command, Queue &test_queue)
{
	bool continue_input =  true;
	Queue_entry item;
	switch(command)
	{
	case'a':
		if(test_queue.full())
			cout<<"Queue is full!Appeding fails."<<endl;
		else
		{
			cout<<"Enter the item(for integer) you want to append into the queue: ";
			cin>>item;
			test_queue.append(item);
		}
		break;
	case'q':
		cout<<"Queue demonstration finished."<<endl;
		continue_input = false;
		break;
	case'h':
		help();
		break;
	}
	return continue_input;
}

这里有两个很有趣的函数，get_command 和 do_command，能够不断读取指令输入并实时运行结果，很有用。