队列的入队、出队基本操作_队列的入队和出队操作

队列

先进先出的线性表（FIFO）

队尾：队列中指定了用来插入数据的一端
队头：队列中指定了用来删除数据的一端
入队：数据的插入动作
出队：数据的删除动作
1
2
3
4

1.顺序队列

//顺序队列
#define QUEUESIZE 64

typedef struct _sequ
{
    dataType data[QUEUESIZE];
    int front;
    int rear;
}SeQueue,*pSeQueue;
//顺序队列
pSeQueue SeQueueCreat()
{
    pSeQueue p = (pSeQueue)malloc(sizeof(SeQueue));
    if(NULL == p)
    {
        perror("SeQueueCreat malloc");
        return NULL;
    }
    memset(p,0,sizeof(SeQueue));
    p->front = -1;
    p->rear = -1;
    return p;
}
//入队
int SeQueueEnter(pSeQueue Q,dataType data)
{
    Q->rear++;
    if(Q->rear > QUEUESIZE)
        return -1;
    Q->data[Q->rear] = data;
    return 0;
}
//出队
int SeQueueExit(pSeQueue Q,dataType *data)
{
    if(Q->front == Q->rear)
        return -1;
    Q->front++;
    *data = Q->data[Q->front];
    return 0;
}
//释放
int SeQueueFree(pSeQueue Q)
{
    free(Q);
    return 0;
}
//打印队列
int printSeQueue(pSeQueue Q)
{
    int i = 0;
    for(i = Q->front + 1;i <= Q->rear;i++)
    {
        printf("%4d ",Q->data[i]);
    }
    printf("\r\n");
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

2.链式队列

一个链式队列需要两个分别指示队头和队尾的指针（头指针和尾指针），才能唯一确定
当头指针和尾指针均指向头结点则表示为空的链队列
以下是链式队列的创建、入队、出队操作的C语言代码

//链式队列
typedef int QueuedataType;
//typedef BinTree QueuedataType;//在后边二叉树时使用
typedef struct _qlnode
{
    QueuedataType data;
    struct _qlnode * next;
}QueueNode,*pQueueNode;

typedef struct
{
    pQueueNode front;
    pQueueNode rear;
    int count ;
}LinkQueue,*pLinkQueue;

//创建结点
pQueueNode LinkQueueCreatNode(QueuedataType data)
{
    pQueueNode s = (pQueueNode)malloc(sizeof(QueueNode));
    if(NULL == s)
    {
        perror("LinkQueueCreatNode malloc");
        return NULL;
    }
    s->data = data;
    s->next = NULL;
    return s;
}

//创建队列
pLinkQueue LinkQueueCreat()
{
    pLinkQueue q = (pLinkQueue)malloc(sizeof(LinkQueue));//创建队列的队头队尾
    if(NULL == q)
    {
        perror("LinkQueueCreat malloc");
        return NULL;
    }

    pQueueNode s = (pQueueNode)malloc(sizeof(QueueNode));//创建头结点
    if(NULL == s)
    {
        perror("LinkQueueCreatNode malloc");
        free(q);
        return NULL;
    }
    s->next = NULL;
    q->front = q->rear = s;//接入头结点，并把队头队尾指针指向该结点
    q->count = 0;

    return q;
}
//入队
int LinkQueueEnter(pLinkQueue Q,QueuedataType* data)
{
    pQueueNode p = LinkQueueCreatNode(*data);
    if(NULL == p)
    {
        perror("LinkQueueCreatNode");
        return -1;
    }

    Q->rear->next = p;  //当前队尾指针域指向新结点
    Q->rear = p;        //新结点变为队尾
    Q->count++;
}
//出队
int LinkQueueExit(pLinkQueue Q,QueuedataType *data)
{
    if(Q->front == Q->rear)
        return -1;
    pQueueNode p = Q->front->next;  //指向头结点的下一个结点
    *data = p->data;
    Q->front->next = p->next;       //头结点的下一跳指向出队结点的下一个结点
    if(Q->rear == p)                //若队头是队尾，则删除后将rear指向头结点
        Q->rear = Q->front;
    Q->count--;
    free(p);

    return 0;
}
//释放
int LinkQueueFree(pLinkQueue Q)
{
    free(Q);
    return 0;
}
//打印队列
int printLinkQueue(pLinkQueue Q)
{
    int i = 0;
    pQueueNode p = Q->front->next;

    for(i = 0;i < Q->count;i++)
    {
        printf("%4d ",p->data);
        p = p->next;
    }
    printf("\r\n");
    return i;
}
int main()
{
    //顺序队列
    pSeQueue s_Queue = SeQueueCreat();
    int m_data = 0;
    if(NULL == s_Queue)
    {
        perror("SeQueueCreat");
        return -1;
    }
    for(int i = 0;i < 10;i++)
        SeQueueEnter(s_Queue,i + 60);
    printSeQueue(s_Queue);

    SeQueueExit(s_Queue,&m_data);
    printf("data:%d\n",m_data);
    printSeQueue(s_Queue);

    SeQueueFree(s_Queue);
    //链式队列
    pLinkQueue s_lQueue = LinkQueueCreat();
    int m_data = 0;
    if(NULL == s_lQueue)
    {
        perror("SeQueueCreat");
        return -1;
    }
    for(int i = 0;i < 10;i++)
        LinkQueueEnter(s_lQueue, i);
    printLinkQueue(s_lQueue);

    LinkQueueExit(s_lQueue,&m_data);
    printf("data:%d\n",m_data);
    printLinkQueue(s_lQueue);

    LinkQueueFree(s_lQueue);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139