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，能够不断读取指令输入并实时运行结果，很有用。