队列，C语言实现

什么是队列？

上一篇文章写了什么是栈，用C语言实现了栈，既然说了栈，不说队列，感觉总是少了点什么，所以就顺手写一个队列，而且最近做项目也用到这个队列的代码。

栈的特点是先进后出，队列的特点是先进先出，从这个特点可以知道，队列是比较友好的，不像栈那样最开始进去排队的人，竟然是最后一个出来的。

新建一个队列

因为我这个例程是使用链表实现队列的，所以新建一个队列，实际上就是开辟一个内存空间，用来存储队列的头部。跟栈一样，我们理解了建立一个队列就是需要建立一个头，开辟的这个空间，代表的是这个队列，就好比，你老爸就可以代表你们家庭，不管你家有多少人，有多少个小孩，你老爸始终都是这个家庭的户主。

/*创建队列，外部释放内存*/
QueueInfo_st *createQueue(void)
{
    QueueInfo_st *queue = (QueueInfo_st *)malloc(sizeof(QueueInfo_st));
    if(NULL == queue)
    {
        printf("malloc failed\n");
        return NULL;
    }
    queue->next = NULL;
    return queue;
}

向队列中插入数据

向队列插入数据，我做的有点麻烦，先是遍历链表，找到这个链表的尾部，然后再在链表的尾部插入数据，看文章的大神，有好的方法可以指出来，我觉得应该有更加优秀的方法的。

/*入队列，0表示成，非0表示出错*/
int queue_push(QueueInfo_st *s,ElementType value)
{
    /*用来保存尾部指针*/
    QueueInfo_st *temp = (QueueInfo_st *)malloc(sizeof(QueueInfo_st));
    if(NULL == temp)
    {
        printf("malloc failed\n");
        return FAILURE;
    }

    /*找到链表的尾部*/
    while(s->next != NULL)
    {
        s = s->next;
    }

    temp->value = value;
    temp->next = s->next;
    s->next = temp;

    return SUCCESS;
}

取出队列的数据

取出队列的数据，也就是把头部指向的下一个链表里面的数据给取出来，取出来要记得释放内存哈，这一步尤其重要。

/*出队列*/
int queue_pop(QueueInfo_st *s,ElementType *value)
{
    /*首先判断队列是否为空*/
    if(queue_is_empty(s))
        return FAILURE;
    /*找出队列顶元素*/
    *value = s->next->value;
    /*保存等下需要free的指针*/
    QueueInfo_st *temp = s->next;
    /*更换队列顶的位置*/
    s->next = s->next->next;

    /*释放队列顶节点内存*/
    if(temp!=NULL)/*先判断指针是否为空*/
        free(temp);
    temp = NULL;

    return SUCCESS;
}

源码例程

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

typedef int32_t ElementType; /*队列元素类型*/
#define SUCCESS 0
#define FAILURE -1

/*定义队列结构*/
typedef struct QueueInfo
{
    ElementType value; /*队列存储的数据*/
    struct QueueInfo *next; /*指向队列的下一个元素*/
}QueueInfo_st;

/*函数声明*/
QueueInfo_st *createQueue(void);
int queue_push(QueueInfo_st *s,ElementType value);
int queue_pop(QueueInfo_st *s,ElementType *value);
int queue_top(QueueInfo_st *s,ElementType *value);
int queue_is_empty(QueueInfo_st *s);

/*创建队列，外部释放内存*/
QueueInfo_st *createQueue(void)
{
    QueueInfo_st *queue = (QueueInfo_st *)malloc(sizeof(QueueInfo_st));
    if(NULL == queue)
    {
        printf("malloc failed\n");
        return NULL;
    }
    queue->next = NULL;
    return queue;
}
/*入队列，0表示成，非0表示出错*/
int queue_push(QueueInfo_st *s,ElementType value)
{
    /*用来保存尾部指针*/
    QueueInfo_st *temp = (QueueInfo_st *)malloc(sizeof(QueueInfo_st));
    if(NULL == temp)
    {
        printf("malloc failed\n");
        return FAILURE;
    }

    /*找到链表的尾部*/
    while(s->next != NULL)
    {
        s = s->next;
    }

    temp->value = value;
    temp->next = s->next;
    s->next = temp;

    return SUCCESS;
}
/*出队列*/
int queue_pop(QueueInfo_st *s,ElementType *value)
{
    /*首先判断队列是否为空*/
    if(queue_is_empty(s))
        return FAILURE;
    /*找出队列顶元素*/
    *value = s->next->value;
    /*保存等下需要free的指针*/
    QueueInfo_st *temp = s->next;
    /*更换队列顶的位置*/
    s->next = s->next->next;

    /*释放队列顶节点内存*/
    if(temp!=NULL)/*先判断指针是否为空*/
        free(temp);
    temp = NULL;

    return SUCCESS;
}
/*访问队列顶元素*/
int queue_top(QueueInfo_st *s,ElementType *value)
{
    /*首先判断队列是否为空*/
    if(queue_is_empty(s))
    {
        return FAILURE;
    }
    *value = s->next->value;
    return SUCCESS;
}
/*判断队列是否为空，空返回1，未空返回0*/
int queue_is_empty(QueueInfo_st *s)
{
    /*队列顶指针为空，则队列为空*/
    if(s->next == NULL)
    {
        printf("队列为空\n");
        return true;
    }

    return false;
}

int main(void)
{
  int i = 0;
  int data = 0;
  QueueInfo_st * queue;
  
  queue = createQueue();
  
  for(i = 0 ;i< 20;i++)
  {
    queue_push(queue,i);
  }
  
  for(i = 0;i<20;i++)
  {
    data = 0;
    queue_pop(queue,&data);
    printf("%d \n",data);
  }
}

总结

队列是基本的数据结构，考试和笔试应该会经常遇到，希望大家在面试的时候，还是能随手就写出一个队列，秒杀其他同学，在实际项目中还需要了解环形队列，也是先进先出的队列，但是环形队列它还体现在环上，我们上面建立的队列是没有大小限制的，但是环形队列是有大小限制的，如果插入的数据大于环形队列的大小，就会把第一个数据给覆盖，或者插入失败，至于是什么逻辑，都是代码实现的，都要去看代码理解其中的原理。

附加题（使用C++实现栈）

关于这个附加题，我想起来我有一个邻居，他女儿现在是小学一年级，班里面的同学读书都非常厉害，如果考试考个90分以下的，基本就是班级里面的倒数了，现在的行业竞争非常激烈，小学也是一样，你们以为考试考100分就是第一名了吗？那么你就是真的想多了，考试考105分都是并列几个第一名的，所以我们这个题目也是一样，使用C++来实现一个栈，这个跟上一次的文章刚好呼应，体现了几个问题，一个是C 和C++的不同，通过面向对象的思想实现栈，代码会少很多，而且封装也很好。对于初学者也可以理解类的思想，构造函数和析构函数等等。

这个代码就无偿奉献给大家，希望这个附加题让大家比其他同学多5分。

#include <iostream>
using namespace std;

class Stack
{
  /*struct 默认数据成员是公有的。*/
  struct Link
  {
    int data_;
    struct Link *next_;
    /*结构体也是类，也可以定义构造函数 */
    Link(int data,Link *next):data_(data),next_(next)
    {
      cout << "Link()"<<endl;
    }
    /*结构体也是类，也可以定义析构函数 */
    ~Link()
    {
      cout << "~Link()"<<endl;
    }
  };
public:
  /*栈成员变成初始化，在构造函数中完成 */
  Stack();
  ~Stack();
  void push(const int data);
  bool empty();
  bool pop(int &data);

private:
  Link * head_;
  int size_; 
};

/*c++ NULL = 0 c:(void *)0 c++:0*/
Stack::Stack():head_(0),size_(0)
{
  cout << "Stack()"<<endl;
}
Stack::~Stack()
{
  cout << "~Stack()"<<endl;
  Link * tmp;
  
  /*循环遍历指针，依次释放内存空间*/
  while(head_)
  {
    tmp = head_;
    head_ = head_->next_;
    delete tmp;
    cout <<"~Stack() delete stack"<<endl; 
  }
}

/*压栈*/
void Stack::push(const int data)
{
  /*把栈的头赋值给 node 的next 指针，相当于node->next_= head_*/
  Link* node = new Link(data,head_);
  /*head 时刻保持自己在栈顶上*/
  head_ = node;
  ++size_; 
}

/*判断栈是否为空*/
bool Stack::empty()
{
  if(size_ == 0)
    return true;
  else
    return false;
}


/*c++ 有引用 ,关于引用和指针的区别可以自行百度，对于每个定义大家最好都要有所了解*/
/*int&    r = i; 这个是声明引用变量 */
/*int *p = &i; 这个是声明指针变量 */
/* 引用是给原来的变量地址取一个新的别名，指针存的是一个变量地址 */
bool Stack::pop(int &data)
{
  if(empty() == true)
  {
    cout << "stack empty"<<endl;
    return false;  
  }
  
  /*把head_指向的data_取出来，这个是栈的头部*/ 
  Link * tmp = head_;
  data = head_->data_;
  head_ = head_->next_;
  
  delete tmp;
  -- size_;
  return true;
}

int main(void)
{
  cout << "Entering main ... "<<endl;
  Stack *stack = new Stack();
  int i;
  int data = 0;
  for(i = 0;i<5;i++)
  {
    stack->push(i);
  }
  
  for(i = 0;i<3;i++)
  {
    stack->pop(data);
    cout<< data << endl;
  }  

  cout << endl;
  delete stack;
  cout << "Exiting main ... "<<endl;
  return 0;
}

猜你喜欢：

C语言代码优化的一些技巧（四）