c语言实现队列的先进先出操作

队列的特点是先进先出，有一个队列头和一个队列尾。如下图示：整个队列含有一个队列头指针front和一个队列尾指针rear，并且队列中每个节点中包含一个数据域和一个指向下一个节点的指针域。

定义一个节点：

typedef struct _node{
	int data;
	struct _node *next;
}node;

定义队列结构体：

typedef struct {
	node *front;
	node *rear;
}queue;

---

1.创建一个队列

queue *create_queue(void)
{
	queue * myqueue = (queue *)malloc(sizeof(queue));
	myqueue->front = NULL;
	myqueue->rear = NULL;

	return myqueue;
}

2.入队

申请一个队列的节点--节点成员赋值--如果空队列--队列的头尾都指向新的节点--不为空--队列的尾下一个节点指针指向新队列--更新队列的队尾指针也就是将队尾指向新的节点。 

queue *insert_queue(queue *myqueue, int data)
{
	if (NULL == myqueue){
		printf("myqueue is NULL\n");
		return NULL;
	}
	node *new_node = NULL;
	new_node = (node *)malloc(sizeof(node));//create a new node
	new_node->data = data;
	new_node->next = NULL;

	if (myqueue->rear == NULL){//if the queue is empty
		myqueue->front = myqueue->rear = new_node;
	}
	else{
		myqueue->rear->next = new_node;
		myqueue->rear = new_node;//move queue rear pointer to new_node
	}

	return myqueue;
}

 

3.出队

申请一个节点指针并指向队列头--移动队列头指针到队列放入下一个节点--判断队列头是否为空--释放需要删除的节点。 

queue *delete_queue(queue *myqueue)
{
	node *p_node = NULL;
	p_node = myqueue->front;
	if (NULL == p_node){
		printf("this is empty queue\n");
		return NULL;
	}
	else{
		myqueue->front = myqueue->front->next;
		if (myqueue->front == NULL){
			myqueue->rear = NULL;
		}
		free(p_node);
	}

	return myqueue;
}

 

4.获得队列的长度和打印一个队列

int get_queue_length(queue *myqueue)
{
	node *p_node = NULL;
	int len = 0;

	p_node = myqueue->front;
	if (NULL != p_node){
		len = 1;
	}
	while (p_node != myqueue->rear)
	{
		p_node = p_node->next;
		len++;
	}

	return len;
}

void queue_print(queue *myqueue)
{
	node *p_node = NULL;
	p_node = myqueue->front;

	if (NULL == p_node){
		printf("this is empty queue\n");
		return;
	}
	printf("The queue is :");
	while (p_node != myqueue->rear)
	{
		printf("%2d", p_node->data);
		p_node = p_node->next;
	}
	printf("%2d\n", p_node->data);
}

 

5.完整的测试代码

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//

// test.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
#include <string>

using namespace std;

typedef struct _node{
	int data;
	struct _node *next;
}node;

typedef struct {
	node *front;
	node *rear;
}queue;

queue *create_queue(void)
{
	queue * myqueue = (queue *)malloc(sizeof(queue));
	myqueue->front = NULL;
	myqueue->rear = NULL;

	return myqueue;
}

//insert queue
queue *insert_queue(queue *myqueue, int data)
{
	if (NULL == myqueue){
		printf("myqueue is NULL\n");
		return NULL;
	}
	node *new_node = NULL;
	new_node = (node *)malloc(sizeof(node));//create a new node
	new_node->data = data;
	new_node->next = NULL;

	if (myqueue->rear == NULL){//if the queue is empty
		myqueue->front = myqueue->rear = new_node;
	}
	else{
		myqueue->rear->next = new_node;
		myqueue->rear = new_node;//move queue rear pointer to new_node
	}

	return myqueue;
}

queue *delete_queue(queue *myqueue)
{
	node *p_node = NULL;
	p_node = myqueue->front;
	if (NULL == p_node){
		printf("this is empty queue\n");
		return NULL;
	}
	else{
		myqueue->front = myqueue->front->next;
		if (myqueue->front == NULL){
			myqueue->rear = NULL;
		}
		free(p_node);
	}

	return myqueue;
}

int get_queue_length(queue *myqueue)
{
	node *p_node = NULL;
	int len = 0;

	p_node = myqueue->front;
	if (NULL != p_node){
		len = 1;
	}
	while (p_node != myqueue->rear)
	{
		p_node = p_node->next;
		len++;
	}

	return len;
}

void queue_print(queue *myqueue)
{
	node *p_node = NULL;
	p_node = myqueue->front;

	if (NULL == p_node){
		printf("this is empty queue\n");
		return;
	}
	printf("The queue is :");
	while (p_node != myqueue->rear)
	{
		printf("%2d", p_node->data);
		p_node = p_node->next;
	}
	printf("%2d\n", p_node->data);
}

int main()
{
	queue * myqueue = create_queue();
	insert_queue(myqueue, 2);
	insert_queue(myqueue, 1);
	insert_queue(myqueue, 3);
	insert_queue(myqueue, 9);
	insert_queue(myqueue, 5);
	insert_queue(myqueue, 6);
	int len = get_queue_length(myqueue);
	printf("The queue length is :%d\n", len);
	queue_print(myqueue);

	delete_queue(myqueue);
	len = get_queue_length(myqueue);
	printf("The queue length is :%d\n", len);
	queue_print(myqueue);

	delete_queue(myqueue);
	len = get_queue_length(myqueue);
	printf("The queue length is :%d\n", len);
	queue_print(myqueue);
}