数据结构（顺序队列/链队列//循环队列）

顺序队列#include<iostream>#include<malloc.h>using namespace std;typedef int ElemType;const int MaxSize=200;typedef struct{ElemType data[MaxSize];int rear,front;}SqQueue;void InitQueue(SqQueue

木一叶liuyue

165人浏览 · 2020-11-10 22:07:49

木一叶liuyue · 2020-11-10 22:07:49 发布

顺序队列

#include<iostream>
#include<malloc.h>
using namespace std;
typedef int ElemType;
const int MaxSize=200;
typedef struct
{
    ElemType data[MaxSize];
    int rear,front;

}SqQueue;

void InitQueue(SqQueue *&s)
{
    s=(SqQueue *)malloc(sizeof(SqQueue));
    s->rear=s->front=-1;
}

void Destroy( SqQueue *&s)
{

    free(s);
}

bool enQueue(SqQueue *&s,ElemType e)
{

    if(s->rear==MaxSize-1)
        return false;

    s->rear++;
    s->data[s->rear]=e;
    return true;
}

bool deQueue(SqQueue *&s,ElemType &e)
{
    if(s->front==s->rear)
        return false;
    s->front++;
    e=s->data[s->front];
    return true;
}
bool EmptyQueue(SqQueue *&s)
{
    return s->rear==s->front;
}

int main()
{
    SqQueue *s;
    InitQueue(s);
      ElemType e;

    for(int i=0;i<10;i++)
    {
       cin>>e;
        enQueue(s,e);

    }

    while(!EmptyQueue(s))
    {
        deQueue(s,e);
        cout<<e<<" ";

    }
      Destroy(s);
}

链队列

#include<iostream>
#include<malloc.h>
using namespace std;
typedef int ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
}DataNode;

typedef struct
{
    DataNode *front;
    DataNode *rear;
}LinkQueue;

void InitQueue(LinkQueue *&q)
{
    q=new LinkQueue;
    q->front=q->rear=NULL;
}

void Destroy(LinkQueue *&q)
{
    DataNode *p=q->front,*r;
    if(p!=NULL)
    {

        r=p->next;
        while(r!=NULL)
        {

            free(p);
            p=r;
            r=p->next;
        }
        free(p);
        free(q);
    }
}

bool EmptyQueue(LinkQueue *q)
{

    return q->rear==NULL;
}

bool enQueue(LinkQueue *&q,ElemType e)
{
    DataNode *p;
    p=new DataNode;

    p->data=e;
    p->next=NULL;
    if(q->rear==NULL)//空队列
    q->front=q->rear=p;

    else
    {
        q->rear->next=p;
        q->rear=p;
    }
}

bool deQueue(LinkQueue *&q,ElemType &e)
{
 DataNode *p;
 if(q->rear==NULL)//空队列
 return false;

 p=q->front;
 if(q->front==q->rear)//只有一个节点
    q->front=q->rear=NULL;
 else
    q->front=q->front->next;
 e=p->data;
 free(p);
 return true;
}

int main()
{   LinkQueue *q;
    InitQueue(q);
    ElemType e;
    for(int i=0;i<10;i++)
    {
        cin>>e;
        enQueue(q,e);

    }

    while(!EmptyQueue(q))
        {
            deQueue(q,e);
            cout<<e<<" ";
        }

        Destroy(q);
       
}

循环队列

#include<iostream>
#include<malloc.h>
using namespace std;
typedef int ElemType;
const int MaxSize=200;

typedef struct
{

    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

void InitQueue(SqQueue *&s)
{
    s=(SqQueue *)malloc(sizeof(SqQueue));
    s->rear=s->front=0;

}

void Destroy( SqQueue *&s)
{

    free(s);
}

bool EmptyQueue(SqQueue *&s)
{
    return s->rear==s->front;
}

bool enQueue(SqQueue *&s,ElemType e)
{

    if((s->rear+1)%MaxSize==s->front)//队满
        return false;

    s->rear++;
    s->data[s->rear%MaxSize]=e;
    //s->rear=(s->rear+1)%MaxSize;
	//s->data[s->rear]=e;
    return true;
}

bool deQueue(SqQueue *&s,ElemType &e)
{
    if(s->front==s->rear)
        return false;
    s->front++;
    e=s->data[s->front%MaxSize];
    return true;
}


int main()
{
    SqQueue *s;
    InitQueue(s);
      ElemType e;

    for(int i=0;i<10;i++)
    {
       cin>>e;
        enQueue(s,e);

    }

    while(!EmptyQueue(s))
    {
        deQueue(s,e);
        cout<<e<<" ";

    }
      Destroy(s);
}