队列Queue

• 队列的顺序存储实现
• 队列的链式存储实现
• 如何用两个堆栈模拟实现一个队列?

队列的顺序存储实现

这里对rear和front位置无要求。

如果空队列开始时front和rear值都是-1，当插入4个元素并删除2个元素后，front和rear值分别是多少？1和3

现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有4个元素。

通用的队列长度计算公式：队列长度=（rear - front + MaxSize) % MaxSize

解释：front、rear方向一致，front指向实际存在的结点的前一个结点，rear指向实际存在的最后一个结点，此时队列中有9、0、1、2四个位置上的元素。

《数据结构》课程给出的队列顺序存储实现方式如下：

typedef int Position;
struct QNode {
    ElementType *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

bool IsFull( Queue Q )
{
    return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}

bool AddQ( Queue Q, ElementType X )
{
    if ( IsFull(Q) ) {
        printf("队列满");
        return false;
    }
    else {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return true;
    }
}

bool IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}

ElementType DeleteQ( Queue Q )
{
    if ( IsEmpty(Q) ) { 
        printf("队列空");
        return ERROR;
    }
    else  {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];
    }
}

测试程序如下：

#include <stdio.h>
#include <stdbool.h>

#define ERROR 0

typedef int ElementType;

typedef struct QNode *Queue;

struct QNode
{
    ElementType *Data;
    int MaxSize;
    int front;
    int rear;
};

Queue CreateQueue(int MaxSize)
{
    Queue q = (Queue)malloc(sizeof(struct QNode));
    q->Data = (ElementType*)malloc(sizeof(ElementType)*MaxSize);
    q->front = 0;
    q->rear = 0;
    q->MaxSize = MaxSize;
    return q;
}

bool IsFullQ(Queue q)
{
    return (((q->rear+1)%q->MaxSize) == q->front);
}


bool AddQ(Queue q,ElementType item)
{
    if(IsFullQ(q))
    {
        printf("队列已满\n");
        return false;
    }
    else
    {
        q->rear = (q->rear+1)%(q->MaxSize);
        q->Data[q->rear] = item;
        return true;
    }
}

bool IsEmptyQ(Queue q)
{
    return (q->rear == q->front);
}

ElementType DeleteQ(Queue q)
{
    if(IsEmptyQ(q))
    {
        printf("队列为空\n");
        return ERROR;
    }
    else
    {
        q->front = (q->front+1)%(q->MaxSize);
        return (q->Data[q->front]);
    }
}

int main()
{
    Queue q = CreateQueue(10);
    int choice;

    while(1)
    {
        printf("输入1添加1个元素，输入2删除1个元素，输入0结束循环\n");
        scanf("%d",&choice);
        if(choice == 1)
        {
            ElementType X;
            scanf("%d",&X);
            AddQ(q,X);
        }
        else if(choice == 2)
        {
            ElementType X = DeleteQ(q);
            printf("%d\n",X);
        }
        else
            return 0;
    }

}

输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
2
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
3
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
1
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
4
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
5
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
6
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
2
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
3
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
1
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
4
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
5
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
6
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
队列为空
0
输入1添加1个元素，输入2删除1个元素，输入0结束循环
0

Process returned 0 (0x0)   execution time : 56.625 s
Press any key to continue.

队列的链式存储实现

队列的front只能设在链表头部。如果front放在链表尾部，删除当前结点后无法找到上一个结点。

在一个链表表示的队列中， f和r分别指向队列的头和尾。r->next=s; r=s;能正确地将s结点插入到队列中。

《数据结构》课程给出的队列链式存储实现方式如下：

typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;

struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

bool IsEmpty( Queue Q )
{
    return ( Q->Front == NULL);
}

ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
    
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                     
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;

        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}

测试程序如下：

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#define ERROR 0

typedef int ElementType;

typedef struct Node *PtrToNode;

struct Node
{
    ElementType Data;
    PtrToNode Next;
};

PtrToNode CreateNode(ElementType Data)
{
    PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
    assert(newNode);
    newNode->Data = Data;
    newNode->Next = NULL;
    return newNode;
}

typedef PtrToNode Position;

typedef struct QNode *Queue;

struct QNode
{
    PtrToNode Front,Rear;
    int curSize;
};

Queue CreateQueue()
{
    Queue q = (Queue)malloc(sizeof(struct QNode));
    assert(q);
    q->curSize = 0;
    q->Front = q->Rear = NULL;
    return q;
}

void AddQ(Queue q,ElementType item)
{
    //PtrToNode s = (PtrToNode)malloc(sizeof(struct Node));
    //s->Data = item;
    //s->Next = NULL;
    PtrToNode s = CreateNode(item);
    if(q->curSize == 0)
        q->Front = s;
    else
        q->Rear->Next = s;
    q->Rear = s;
    q->curSize++;
}
bool IsEmptyQ(Queue q)
{
    return (q->Front == NULL);
}

ElementType DeleteQ(Queue q)
{
    PtrToNode FrontCell;
    ElementType FrontElem;
    if(IsEmptyQ(q))
    {
        printf("队列空!\n");
        return ERROR;
    }
    else
    {
        FrontCell = q->Front;
        if(q->Front == q->Rear)
            q->Front = q->Rear = NULL;
        else
            q->Front = q->Front->Next;
        FrontElem = FrontCell->Data;
        free(FrontCell);
        q->curSize--;
        return FrontElem;
    }

}

int main()
{
    Queue q = CreateQueue();
    int choice;

    while(1)
    {
        printf("输入1添加1个元素，输入2删除1个元素，输入0结束循环\n");
        scanf("%d",&choice);
        if(choice == 1)
        {
            ElementType X;
            scanf("%d",&X);
            AddQ(q,X);
        }
        else if(choice == 2)
        {
            ElementType X = DeleteQ(q);
            printf("%d\n",X);
        }
        else
            return 0;
    }

}

输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
2
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
3
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
4
输入1添加1个元素，输入2删除1个元素，输入0结束循环
1
5
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
2
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
3
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
4
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
5
输入1添加1个元素，输入2删除1个元素，输入0结束循环
2
队列空!
0
输入1添加1个元素，输入2删除1个元素，输入0结束循环
0

Process returned 0 (0x0)   execution time : 22.052 s
Press any key to continue.

如何用两个堆栈模拟实现一个队列?

如何用两个堆栈模拟实现一个队列?  如果这两个堆栈的容量分别是m和n（m>n)，你的方法能保证的队列容量是多少？