数据结构之链队列

[jyzwf]

链队列即有一个头结点和一个尾结点，然后依次在队尾后面插入节点，形成链队列

基本操作：

1. initQueue 初始化操作
2. queueEmpty 判断队列是否为空
3. enterQueue 入队
4. deleteQueue 出队
5. getHead 取队头元素
6. clearQueue 清空队列
7. displayQueue 显示队列所有元素

主文件

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

#include "linkQueue.h"

int main()
{
       LinkQueue Q;
       char str[] = "ABCDEFGH";
       int i,length = 8;
       char x;

       initQueue(&Q);


       for(i=0;i<length;i++)
       {
              enterQueue(&Q,str[i]);
       }

         displayQueue(Q);

         deleteQueue(&Q,&x);
         printf("出队元素的值为：%2c\n",x);

         printf("当前队列中的元素：\n");
         displayQueue(Q);
         printf("\n");
         return 0;
}

头文件

#ifndef LINKQUEUE_H_INCLUDED
#define LINKQUEUE_H_INCLUDED

// 结点类型定义
struct QNode
{
       char data;
       struct QNode *next;
};

typedef struct QNode LQNode,*QueuePtr;

// 队列类型定义
typedef struct
{
       QueuePtr front;
       QueuePtr rear;
}LinkQueue;


// 初始化操作
void initQueue(LinkQueue *LQ)
{
       LQ->front = (QueuePtr)malloc(sizeof(LQNode));
       if(LQ->front==NULL)
              exit(-1);
       LQ->front->next = NULL;
       LQ->rear=LQ->front;
}

// 判断队列是否为空
int queueEmpty(LinkQueue LQ)
{
       if(LQ.rear->next==NULL)
              return 1;
       return 0;
}


// 入队
int enterQueue(LinkQueue *LQ,char e)
{
       QueuePtr s;
       s = (QueuePtr) malloc(sizeof(LQNode));
       if(!s)
              exit(-1);
       s->data = e;
       s->next = NULL;
       LQ->rear->next = s;
       LQ->rear = s;
       return 1;
}

// 出队
int deleteQueue(LinkQueue *LQ,char *e)
{
       QueuePtr s;
       if(LQ->front == LQ->rear)
              return 0;

       s = LQ->front->next;
       *e = s->data;
       LQ->front->next=s->next;
       if(LQ->rear == s)
              LQ->rear = LQ->front;
       free(s);
       return 1;
}


// 取队头元素
int getHead(LinkQueue LQ,char *e)
{
       QueuePtr s;
       if(LQ.front==LQ.rear)
              return 0;
       s = LQ.front;
       *e = s->data;
       return 1;
}


// 清空队列
void clearQueue(LinkQueue *LQ)
{
       while(LQ->front!=NULL)
       {
              LQ->rear = LQ->front->next;
              free(LQ->front);
              LQ->front = LQ->rear;
       }
}



// 显示队列所有元素
void displayQueue(LinkQueue LQ)
{
       QueuePtr p;
       printf("队列的各个结点：\n");
       p = LQ.front->next;
       while(p)
       {
              printf("%2c ",p->data);
              p = p->next;
       }
}


#endif // LINKQUEUE_H_INCLUDED

结果