数据结构-链式队列的基本操作

//队列的基本操作 

#include <iostream> 

using namespace std;

#define datatype int

#define Status int

#define OK     1

#define ERROR  0

typedef struct linkqueuenode{           //定义队列节点 

        datatype data;

        struct linkqueuenode *next;                

}LinkQueueNode;

typedef struct {                        //定义链式队列     

        LinkQueueNode *front;

        LinkQueueNode *rear;        

}LinkQueue; 

//初始化

void InitQueue(LinkQueue *q)

{

q->front=NULL;

q->rear=NULL;

}

//入队 

Status InQueue(LinkQueue *q,datatype x)

{

//创建节点

LinkQueueNode *s=new LinkQueueNode;

s->data=x;

s->next=NULL;

//是否队空

if(q->front==NULL)

{

s->next=q->rear;

q->front=s;

q->rear=s;

}

else

{

q->rear->next=s;

q->rear=s;

}

return 0;

}

//出队 

Status OutQueue(LinkQueue *q,datatype &x)

{//若队空，返回0；出队完成，返回1

if(NULL==q->front) return 0;

LinkQueueNode *p=q->front;

x=p->data;

q->front=p->next;

delete p;

return 1;

}

//显示队列元素 

Status ShowQueue(LinkQueue *q)

{

if(q->front==NULL) {cout<<"栈空！"<<endl;return 0;}//队列空

LinkQueueNode *p;

p=q->front;

cout<<"遍历队列: ";

while(p!=NULL)

{

printf("%d ",p->data);

p=p->next;

}

cout<<endl;

return 1;

}

//读队首元素 

Status ReadQueue(LinkQueue *q)

{

if(NULL==q->front) return 0;

cout<<"队首元素为:"<<q->front->data<<endl;;

return 1;

}

//双队列，队首出栈

Status OutQueueFront(LinkQueue *q,datatype &x)

{//若队空，返回0；出队完成，返回1

if(NULL==q->front) return 0;

LinkQueueNode *p=q->front;

x=p->data;

q->front=p->next;

delete p;

return 1;

}

//双队列，队尾出栈

Status OutQueueRear(LinkQueue *q,datatype &x)

{

//对空，返回0

if(NULL==q->front) return 0;

//找q.rear的前驱

LinkQueueNode *ptr;

ptr=q->rear;//ptr指向对尾

LinkQueueNode *p=q->front;

while(p->next!=q->rear)//p指向q->rear的前驱

{

p=p->next;

}

x=q->rear->data;

p->next=q->rear->next;

q->rear->next=p->next;

q->rear=p;

delete ptr;

return 1;

}

int main()

{

    LinkQueue que;//创建队列

    InitQueue(&que);//初始化队列

InQueue(&que,1);//入队

InQueue(&que,2);

InQueue(&que,3);

InQueue(&que,4);

ShowQueue(&que);//1,2,3,4

datatype temp;//用于保存出队的data

OutQueue(&que,temp);//2,3,4

ShowQueue(&que);//显示队列元素

ReadQueue(&que);

OutQueueRear(&que,temp);//2,3

ShowQueue(&que);

    system("pause");

    return 0;    

} 

-----------------------------------------------------------

运行结果：

遍历队列: 1 2 3 4

出队！：

遍历队列: 2 3 4

队首元素为:2

队尾出队！

遍历队列: 2 3

Press any key to continue . . .

鲜少伟

2016-4-18