顺序队列

队列是先进先出的线性结构，也是只能从队头删除，从队尾插入的线性表，为了使空间利用更加充分，从而避免假溢出，通常采用循环队列

创建

typedef struct 
{
	Elemtype *base;				//储存空间的基址指针
	int front;					//定义一个头指针
	int rear;					//定义一个尾指针
}SQqueue;

注：此处front和rear指针仅仅设为了int类型，而并非真正的指针类型，所表述的是队头队尾元素所在的位置下标

初始化

bool initqueue(SQqueue &sq)
{
	sq.base=new Elemtype[MAXSIZE];			//为队列分配空间
	if(!sq.base) return false;				//没能分配成功，返回失败
	sq.front=sq.rear=0;						//头尾指针置为零，队列为空
	return true;
}

求队列长度

int queuelength(SQqueue &sq)
{
	return (sq.rear-sq.front+MAXSIZE)%MAXSIZE;
}

注：在没有特殊注明的情况下，所说队列都为循环队列，front指向队头元素，rear指向队尾元素的后一个元素，为区分队空与队满，此处少用一个元素空间，即队列空间大小为m-1个元素时队满，故而当队列满足“rear=front“时队空，当队列满足”(rear+1)%MAXSIZE=front“时队满。

入队（从队尾插入）

bool enterqueue(SQqueue &sq,Elemtype e)		  //传址需要操作的表，传值入队元素
{
	if((sq.rear+1)%MAXSIZE==sq.front) return false;    //判断队满时返回失败
	sq.base[sq.rear]=e;					 //让队尾元素的后一个元素等于e
	sq.rear=(sq.rear+1)%MAXSIZE;		 //队尾指针后移
	return true；						//返回成功入队
}

出队（从队头删除）

bool deletequeue(SQqueue &sq,Elemtype &e)
{
	if(sq.front==sq.rear) return false;		//若队空，则返回出队失败
	e=sq.base[sq.front];					//用e获得出队的队头元素
	sq.front=(sq.front+1)%MAXSIZE;			//队头指针后移
	return true;							//返回成功出队
}

取队头元素

Elemtype gethead(SQqueue &sq)
//仅返回表的队头元素，不修改头指针
{
	if(sq.front!=sq.rear) 			//判断队列非空
	return 	sq.base[sq.front];		//返回队头元素
}

实际题目

R7-4 队列操作 (20 分)

请实现一个MyQueue类，实现出队，入队，求队列长度.

实现入队函数 void push(int x); 实现出队函数 int pop(); 实现求队列长度函数 int size();

输入格式:
每个输入包含1个测试用例。每个测试用例第一行给出一个正整数 n (n <= 10^6) ，接下去n行每行一个数字，表示一种操作： 1 x ：表示从队尾插入x，0<=x<=2^31-1。 2 ：表示队首元素出队。 3 ：表示求队列长度。

输出格式:
对于操作2,若队列为空，则输出 “Invalid”,否则请输出队首元素。对于操作3，请输出队列长度。每个输出项最后换行。

输入样例:

输出样例:

0
Invalid
1
100

解法：

#include<iostream>
using namespace std;

typedef struct
{
    int *base;
    int front;
    int rear;
}SQueue;

bool init(SQueue &sq)
{
    sq.base=new int[50];
    if(!sq.base) return false;
    sq.front=0;
    sq.rear=0;
    return true;
}

int length(SQueue &sq)
{
    return (sq.rear-sq.front+50)%50;
}

bool enter(SQueue &sq,int a)
{
    if((sq.rear+1)%50==sq.front) return false;
    sq.base[sq.rear]=a;
    sq.rear=(sq.rear+1)%50;
    return true;
}

bool out(SQueue &sq,int &a)
{
    if(sq.front==sq.rear) return false;
	a=sq.base[sq.front];
	sq.front=(sq.front+1)%50;
	return true;
}

int main()
{
    SQueue L;
    init(L);
    int n,i,j,k;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>j;
        switch(j)
        {
            case 1:
                cin>>k;
                enter(L,k);
                break;
            case 2:
                if(out(L,k)) cout<<k<<endl;
                else cout<<"Invalid"<<endl;
                break;
            case 3:
                cout<<length(L)<<endl;
                break;
        }
    }
    return 0;
}