首页 > 代码库 > 链队列的实现

链队列的实现

2024-07-28 10:56:17   218人阅读

         //------------------------------队列----------------------------------------//
//队列与栈相反，是一种先进先出(FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素
//允许插入的一端叫做队尾(rear)，允许删除的一端叫做队头(front)
//给链队列增加一个头结点，并令头指针指向头结点。空的链队列的判决条件：头指针和尾指针均指向头结点
//链队列的操作即为单链表的插入和删除操作的特殊情况

//-----------------------------------------------------------------------------//

function.h

#define Status int
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int QElemType;
typedef struct QNode
{
        QElemType data;
        struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
       QueuePtr front;
       QueuePtr rear;
}LinkQueue;
void visit_print(QueuePtr p);
Status InitQueue(LinkQueue *Q);   //构造
Status DestroyQueue(LinkQueue *Q);   //销毁
Status ClearQueue(LinkQueue *Q);     //清空
Status QueueEmpty(LinkQueue Q); // 为空返回TRUE，否则返回FALSE
Status QueueLength(LinkQueue Q);//返回队列长度
Status GetHead(LinkQueue Q, QElemType *e);   // 返回队列的头元素
Status EnQueue(LinkQueue *Q, QElemType e);   //插入元素e为新的队尾元素
Status DeQueue(LinkQueue *Q, QElemType *e);//若队列不为空返回队头元素，否则返回ERROR
Status QueueTraverse(LinkQueue Q,  void (*visit)(QueuePtr) );
//从队头到队尾的队列中每个元素调用函数visit(),一旦失败则操作失败

function.c

#include "function.h"
#include <stdio.h>
#include <stdlib.h>
void visit_print(QueuePtr p)
{
        printf("%d   ", p->data);
}
Status QueueEmpty(LinkQueue Q)
{
        if( Q.front == Q.rear)
        {
                printf("the queue is empty!\n");
                return OK;
        }
        else
                 return ERROR;


}
Status InitQueue(LinkQueue *Q)
{
        Q->front = Q->rear = (QueuePtr ) malloc ( sizeof ( QNode ) );//生成一个头结点，数据域为空
        if( !Q->front )          exit(OVERFLOW);  //分配失败
        Q->front->next=NULL;
        return OK;
}
Status EnQueue(LinkQueue *Q, QElemType e)
{
        QueuePtr p;
        p=(QueuePtr ) malloc (sizeof (QNode ));
        p->data = http://www.mamicode.com/e;>
main.c
//------------------------------队列----------------------------------------//
//队列与栈相反，是一种先进先出(FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素
//允许插入的一端叫做队尾(rear)，允许删除的一端叫做队头(front)
//给链队列增加一个头结点，并令头指针指向头结点。空的链队列的判决条件：头指针和尾指针均指向头结点
//链队列的操作即为单链表的插入和删除操作的特殊情况
//-----------------------------------------------------------------------------//
#include <stdio.h>
#include <stdlib.h>
#include "function.h"

int main(void)
{
        LinkQueue Q;
        QElemType e;
        int i;
        InitQueue(&Q);
        QueueEmpty(Q);
       for(i=0;i<5;i++)
        {
                scanf("%d ", &e);
                EnQueue(&Q, e);
        }
        printf("the queue are:");
        QueueTraverse(Q, visit_print);
        printf("the queue's length is %d \n", QueueLength(Q));
        GetHead(Q ,&e);
        printf("the head member of queue is %d\n ", e);
        DeQueue(&Q, &e);
        printf("delete the head member in queue is %d\n", e);
        printf("after delete the head node ,queue are:");
        QueueTraverse(Q, visit_print);
        printf("the queue length is %d\n", QueueLength(Q));

        ClearQueue(&Q);
         QueueEmpty(Q);
        return 0;
}


运行结果：

链队列的实现


联系
我们