[数据结构]队列的基本操作

栈是先进后出，队列则是先进先出.下面贴一下队列的基本操作.

1.队列的顺序表示.

1.1队列的结构体定义

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
#define MAXNUM 20   /*队列中元素的最大个数*/
struct Seqqueue   /*顺序队列类型定义*/
{
    int f,r;
    DataType q[MAXNUM];
};

typedef struct Seqqueue Seqqueue,*PSeqqueue;

/*创建一个空队列*/
PSeqqueue createEmptyqueue(void);
/*判断队列是否为空*/
int isEmptyqueue_seq(PSeqqueue paqu);
/*在队列中插入一个元素*/
void enqueue_seq(PSeqqueue paqu,DataType x);
/*删除队头元素*/
void dequeue_seq(PSeqqueue paqu);
/*对非空队列求队头元素*/
DataType frontqueue_seq(PSeqqueue paqu);

1.2创建队列

PSeqqueue createEmptyqueue(){
    PSeqqueue paqu=(PSeqqueue)malloc(sizeof(struct Seqqueue));
    if (paqu==NULL)
    {
        printf("Out of space.\n");
    }else{
        paqu->r=paqu->f=0;
    }

    return paqu;
}

1.3队列中插入元素

void enqueue_seq(PSeqqueue paqu,DataType x){
    if ((paqu->r+1)%MAXNUM==paqu->f)
    {
        printf("Full queue.\n");
    }else{
        paqu->q[paqu->r]=x;
        paqu->r=(paqu->r+1)%MAXNUM;
    }
}

1.4删除对头元素

void dequeue_seq(PSeqqueue paqu){
    if (isEmptyqueue_seq(paqu))
    {
       printf("Empty queue\n");
    }else{
        paqu->f=(paqu->f+1)%MAXNUM;
    }
}

1.5返回对头元素

DataType frontqueue_seq(PSeqqueue paqu){
   return paqu->q[paqu->f];
}

1.6判断队列是否为空.

int isEmptyqueue_seq(PSeqqueue paqu){
    return paqu->f=paqu->r;
}

1.7测试

int main(){
    PSeqqueue queue=createEmptyqueue();
    enqueue_seq(queue,2);
    enqueue_seq(queue,3);
    enqueue_seq(queue,4);
    printf("%d\n",frontqueue_seq(queue));
    return 0;
}

2.队列的链式表示

2.1结构体定义和函数声明

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

typedef int Datatype;
struct Node;
typedef struct Node *PNode;
struct Node
 {
    Datatype info;
    PNode link;
 }; 

struct LinkQueue
{
    PNode f;
    PNode r;

};

typedef  struct LinkQueue *PLinkQueue;
//创建一个空队列
PLinkQueue createEmptyQueue_link();
//判断队列是否为空
int isEmptyQueue_link(PLinkQueue plqu);
//进队列
void enQueue_link(PLinkQueue plqu,Datatype x);
//出对列
void deQueue_link(PLinkQueue plqu);
//在非空队列中求对头元素
Datatype frontqueue_link(PLinkQueue plqu);

2.2创建队列

PLinkQueue createEmptyQueue_link(){
    PLinkQueue plqu=(PLinkQueue)malloc(sizeof(struct LinkQueue));
    if (plqu==NULL)
    {
        printf("Out of space.\n");
    }else{
        // PNode pnode=(PNode)malloc(sizeof(struct Node));
        plqu->f=plqu->r=NULL;
    }
    return plqu;
}

2.3入队列

void enQueue_link(PLinkQueue plqu,Datatype x){

   PNode pnode=(PNode)malloc(sizeof(struct Node));
   if(pnode==NULL){
     printf("Out of space.\n");
   }else{
     pnode->info=x;
     pnode->link=NULL;
         if (plqu->f==NULL)
         {
            plqu->f=pnode;
         }else{
            plqu->r->link=pnode;

         }
         plqu->r=pnode;
   }

}

2.4删除队尾元素

void deQueue_link(PLinkQueue plqu){
    PNode pnode;
    if (plqu->f==NULL)
    {
        printf("Empty Queue\n");
    }else{
       pnode=plqu->f;
       plqu->f=plqu->f->link;
       free(pnode);
    }
}

2.5返回对头元素

Datatype frontqueue_link(PLinkQueue plqu){
    printf("%d\n",plqu->f->info);
    return(plqu->f->info);
}

2.6队列是否为空

int isEmptyQueue_link(PLinkQueue plqu){
    return (plqu->f==NULL);
}

2.7测试

int main(){
     PLinkQueue p=createEmptyQueue_link();
     enQueue_link(p,5);
     enQueue_link(p,15);
     enQueue_link(p,35);
     frontqueue_link(p);
     deQueue_link(p);
     frontqueue_link(p);
    return 0;
}