C利用语言实现数据结构之队列

1
2
3
4
5
6
7
8
9
10
11
12
//定义节点结构
typedef struct QNode
{
    QElemType   data;   /*数据域*/
    struct QNode   * next;   /*指针域*/
 }QNode, *QueuePtr;
//定义队列结构
 typedef struct
 {
    QueuePtr front;
    QueuePtr rear;
 }LinkQueue;

1
2
3
4
5
6
7
Status initQueue(LinkQueue *Q)
{ 
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

1
2
3
4
5
6
7
8
9
10
Status destroyQueue(LinkQueue *Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
   return OK;
}

1
2
3
4
5
6
7
8
9
10
11
12
Status enQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    //插入数据
    p->data = e;
    p->next = NULL;
    //Q.rear一直指向队尾
    Q.rear->next = p;
    Q.rear = p;
    return OK;
 }

1
2
3
4
5
6
7
8
9
10
11
Status deQueue(LinkQueue *Q, QElemType e)
{
    if(Q.front == Q.rear) return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;   //队头元素p出队
    if(Q.rear == p)   //如果队中只有一个元素p, 则p出队后成为空队
    Q.rear = Q.front;     //给队尾指针赋值
    free(p);   //释放存储空间
    return OK;
}

1
2
3
4
5
6
7
#define MAXQSIZE  100
typedef struct
{
    QElemType *base;
    int  front;   //头指针指示器 
    int  rear;  //尾指针指示器
} SqQueue;

1
2
3
4
5
6
7
Status initQueue (SqQueue *Q)
{
    Q.base=(QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

1
2
3
4
int queueLength(SqQueue *Q)
{
    return (Q.rear - Q.front+MAXQSIZE) % MAXQSIZE;
}

1
2
3
4
5
6
7
Status enQueue (SqQueue *Q, QElemType e)
{
    if((Q.rear+1)%MAXQSIZE == Q.front)  return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1) % MAXQSIZE;
    return OK;
}

1
2
3
4
5
6
7
8
Status deQueue (SqQueue *Q, QElemType e)
{
    if(Q.front == Q.rear)
    return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAXQSIZE;
    return OK;
}