假设以不带头节点的循环链表表示队列。

Question

并且只设一个指针指向队尾节点，但不设头指针。是设计相应的入队和出队算法。
用C++，请给我一份完整的程序代码，谢谢！求赐教。

Answer 1

不明白你的意思，下面是一个链队的C语言示例，没有C++版本的：

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

#define  OK 1
#define  ERROR 0
#define  TRUE 1
#define  FALSE 0

typedef int QElemType;
typedef int Status;

typedef struct QNode //定义结点类型
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct     //定义链表指针
{
QueuePtr front; //队头指针
QueuePtr rear;  //队尾指针
}LinkQueue;

Status visit(QElemType d)
{
printf("%d ",d);
return OK;
}

Status InitQueue(LinkQueue &Q)//构造一个空队列Q
{

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //动态分配内存,生成头结点,使头指针尾指针都指向它
if(!Q.front) exit(1);
Q.front->next=NULL; //头指针指向的头结点的指针域为NULL
return OK;
}

Status DestroyQueue(LinkQueue &Q)
{
//销毁队列Q
while (Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}

Status EnQueue(LinkQueue &Q,QElemType e)//插入元素e为Q的新的队尾元素
{
QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); //动态分配内存,生成新结点
if(!p) exit(1);
p->data=e; 
p->next=NULL; //新结点p作为尾指针,故其指针域为NULL
Q.rear->next=p; //使p链到原队尾结点后面
Q.rear=p;       //使队尾指针指向新结点p
return OK;
}

//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
Status DeQueue(LinkQueue &Q,QElemType &e)
{

QueuePtr p;
if(Q.front==Q.rear) return ERROR; //队列为空
    p=Q.front->next; //令p指向队头结点
e=p->data;       //将队头元素值赋值给e
Q.front->next=p->next; //令头结点的指针域指向p后面的结点
if(Q.rear==p) Q.rear=Q.front;//原队中只有一个结点,删去后队尾指针丢失,所以需对队尾重新赋值(指向队头结点)
free(p);
return OK;
}

Status ClearQueue(LinkQueue &Q)
{
QueuePtr p,q;
Q.rear=Q.front;
p=Q.front->next;
Q.front->next=NULL;
    while(p)
{
q=p;
p=p->next;
free(q);
}
return OK;
}

/*若Q为空队列,则返回TRUE否则返回FALSE*/
Status QueueEmpty(LinkQueue Q)
{
   if(Q.front==Q.rear)  return TRUE;
   else return FALSE;
}

/*求队列的长度*/
int QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p;
p=Q.front;
while(Q.rear!=p)
{
i++;
p=p->next;
}
return i;
}

/*若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR*/
Status GetHead(LinkQueue Q,QElemType *e)
{
QueuePtr p;
if (Q.front==Q.rear)
   return ERROR;
p=Q.front->next;
*e=p->data;
return OK;
}

/*从队头到队尾依此对队列Q中每个元素输出*/
Status QueueTraverse(LinkQueue Q)
{
   QueuePtr p;
   p=Q.front->next;
   while(p)
   {
   visit(p->data);
   p=p->next;
   }
   printf("\n");
   return OK;
}

来自：求助得到的回答