数据结构-队列

队列及其应用

 

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;
}