1，队列的实现
1,用数组实现的队列
队列的特征是：先进先出(fifo)
队列数据结构的操作是：从队列首部出队列，从队列的尾部入队列。
一般是用动态数组实现队列，在创建队列时队列的元素个数已经确定。
/*
* 用数组实现的循环队列
*
* 要注意：队列的头指针和尾指针都在变化
*/
#include "all.h"
#define ERROR -1
#define OK 0
typedef char Elem_type;
struct queue {
Elem_type *base; //队列指针
int front; //队列头指针
int rear; //队列尾指针
int maxlen; //队列长度
int size; //队列长度
};
typedef struct queue QUEUE;
QUEUE *create_queue(int maxlen)
{
QUEUE *q;
q = (QUEUE *)malloc(sizeof(QUEUE));
if (NULL == q)
return NULL;
q->base = (Elem_type *)malloc(sizeof(Elem_type)*maxlen);
if (NULL == q->base)
return NULL;
q->maxlen = maxlen;
q->front = 0;
q->rear = 0;
q->size = 0;
return q;
}
int is_full(QUEUE *q)
{
if (q->rear >= q->maxlen)
return 1;
else
return 0;
}
//入队
int enqueue(QUEUE *q, Elem_type val)
{
/*
* if ((q->rear+1)%q->maxlen == q->front) //队列满，也可以这样判断
*/
if (q->size >= q->maxlen) { //队列满
fprintf(stderr, "error: queue full!\n");
return ERROR;
}
q->base[q->rear] = val;
q->rear = (q->rear+1)%q->maxlen; //若rear是maxlen(队列满)就回绕到0的位置
q->size += 1;
return OK;
}
//出队
int dequeue(QUEUE *q, Elem_type *val)
{
if (q->size <= 0) { //注意边界条件
printf("error: empty queue!\n");
return ERROR;
}
*val = q->base[q->front]; //取头部元素
q->front = (q->front+1)%q->maxlen; //调整头指针,若到了队列尾部，绕回
q->size -= 1; //size-1
return OK;
}
//测试例程
#define MAXLEN 5
int main(void)
{
char a[MAXLEN] = {'\0'};
QUEUE *q;
char *p;
char v;
fgets(a, MAXLEN, stdin);
a[strlen(a)-1] = '\0';
printf("a=[%s]\n", a);
q = create_queue(MAXLEN-3);
if (!q) {
printf("create stack error!\n");
return 1;
}
p = a;
while ('\0' != *p) {
enqueue(q, *p);
p++;
}
printf("\n-----dequeue size=[%d]-----\n", q->size);
while (OK == dequeue(q, &v)) {
printf("%c\n", v);
}
printf("\nend\n");
return 0;
}
2，用链表实现的队列
/*
* 链表实现的队列
*
* 链表实现的队列思想是： 维护两个指针(头、尾指针)来进行出对和入队的操作。
* 入队：从链表尾部插入节点
* 出对：从链表头删除节点，并取得头结点的值。
*
* hover 2011-03-17
*/
#include "all.h"
typedef char Elemtype;
//结点结构
struct node {
struct node *next;
Elemtype data;
};
typedef struct node Node;
//队列管理结构
struct queue {
Node *front;
Node *rear;
int size;
};
typedef struct queue Queue;
//创建队列
Queue *create_queue(int maxlen)
{
Queue *q;
q = (Queue *)malloc(sizeof(Queue));
if (!q) {
fprintf(stderr, "malloc error!\n");
return NULL;
}
q->front = q->rear = NULL; //不带头结点的链表
q->size = 0; //元素个数是0
return q;
}
//入队 :从链表尾部插入结点
int enqueue(Queue *q, Node *node)
{
if (!q || !node)
return ERROR;
node->next = NULL; //入队时需要从尾结点插入
if (is_empty(q)) { //空队列
q->rear = node;
q->front = node;
} else {
q->rear->next = node; //添加结点到尾部
q->rear = node; //移动尾结点
}
q->size += 1;
return OK;
}
//出对：删除头结点
int dequeue(Queue *q, Elemtype *val)
{
Node *pnode;
if (!q)
return ERROR;
//if (q->front == NULL) { //空队列
if (is_empty(q)) { //空队列
fprintf(stderr, "empty queue!\n");
return ERROR;
}
pnode = q->front->next;
*val = q->front->data; //得到头结点的值
free(q->front);
q->front = pnode; //删除后移动头指针
if (NULL == pnode) //若是最后一个节点
q->rear = NULL; //注意：不要忘记更新尾结点
q->size -= 1;
return OK;
}
