My implementation of single direction queue by linked list
In computer science, a queue (/ˈkjuː/ kew) is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known asenqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.
Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer.
Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are circular buffers and linked lists.
我的代码实现：
--------------------------------------------------------
说明(2014.09.13补充)：
这里使用的链表实现具有“局限性”
也就是说不完美，我把队列长度固定了
后面会给出数组实现，这里的链表实现的
修正等一段时间....
2014.09.14:
已经把原来的链表实现更新，实现
队列不定长队列的链表实现。
补充了数组实现，定长队列.
2014.11.22
OMG...发现之前的代码有个小bug，入队数据的第一个数据
忘记赋值，导致第一个数据输出的结果总是０。
现在已经修复这个bug : )
2014.11.23
好吧，发现并修复bug，维护自己的代码算是件“功德无量”的事情，
之前链表实现的时候，如果队列被排空的时候，程序会挂掉。
最后一个特殊情况之前没有处理好，这里吸取教训，以后一定要多
考虑边界情况。
bug 已经修复，更新了实现代码.
2015.01.13
添加了Python实现, Python实现版本有不限队列长度的特点
2015.02.09
添加了一个有意思的问题的解, 怎么使用两个栈来实现一个队列.
-------------------------------------------------------------------------------------------------------
Python 实现:
"""
code writer : EOF
code date : 2015.01.13
code file : Queue.py
e-mail : [email protected]
Code description:
Here is a implementation for ADT-Queue in Python.
"""
class queue() :
Q = []
ihead = -1 # head index
itail = -1 # tail index
def __init__(self, arg = [0]) :
if len(arg) == 0 :
arg = [0]
self.Q = arg
self.ihead = 0
self.itail = 0
def enqueue(self, num) :
self.Q += [num]
self.itail = len(self.Q)
def dequeue(self) :
if self.itail == 0 :
print "Waring ! queue is empty NOW"
return
del self.Q[self.ihead]
self.ihead = 0
self.itail -= 1
def show_queue(self) :
print self.Q
#-----------------start to test our ADT below this line-----------------
tmp = queue([1,2,3,4,5])
tmp.show_queue()
print "tmp.enqueue(100) tmp.enqueue(200)"
tmp.enqueue(100)
tmp.enqueue(200)
tmp.show_queue()
for i in range(1,9) :
tmp.dequeue()
tmp.show_queue()
C 语言实现——链表实现：
queue.h
#ifndef _QUEUE_H
#define _QUEUE_H 1
struct node
{
struct node* previous;
struct node* next;
int data;
};
#define QUEUE_SIZE 10
#define ARRAY_SIZE 20
#define SUCCESS 1
#define FAILED 0
#define EMPTY_QUEUE -1
#define UNEMPTY_QUEUE 0
#include "queue_destory.h"
#include "queue_enter.h"
#include "queue_init.h"
#include "queue_out.h"
#include "queue_print.h"
#endif
queue_test.c
/***********************************************************
code writer : EOF
code date : 2014.03.07
e-mail: [email protected]
code purpose:
Just a test source file for queue. I would be
happy, if my code will help you to know what is queue.
We assume that:
Input data ---> tail | | |queue| | | header ---> Output data
If something wrong with my code, please touch me by e-mail.
************************************************************/
#include <stdio.h>
#include "queue.h"
int main()
{
int temp = 0;
int array[ARRAY_SIZE] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
struct node* p_queue_tail;
struct node* p_queue_header;
queue_init(&p_queue_header,&p_queue_tail);
for(temp = 0; temp < ARRAY_SIZE; temp++)
{
if(SUCCESS != queue_enter(&p_queue_header,&p_queue_tail,array[temp]))
{
printf("enter error!\n");
queue_destory(p_queue_tail);
return 0;
}
}
queue_print(p_queue_tail);
for(temp = 0;temp < ARRAY_SIZE;temp++)
{
printf("queue out:%d\n",queue_out(&p_queue_header,&p_queue_tail));
}
queue_print(p_queue_tail);
queue_destory(p_queue_tail);
return 0;
}
queue_init.c
/******************************************************************
code writer : EOF
code date : 2014.09.13
e-mail : [email protected]
Attention:
Just a implementation of function queue_init. I would be
happy, if my code will help you to know what is queue.
we assuem that ...
Input data ---> tail | | |queue| | | header ---> Output data
If something wrong with my code please touch me by e-mail.
*******************************************************************/
#include <stdlib.h>
#include "queue.h"
#include <stdio.h>
int queue_init(struct node** pp_queue_header,struct node** pp_queue_tail)
{
(*pp_queue_header) = NULL;
(*pp_queue_tail) = NULL;
return SUCCESS;
}
queue_enter.c
/****************************************************************
code writer : EOF
code date: 2014.03.07
e-mail: [email protected]
code purpose:
Just a implementation of function queue_enter. I would be
happy, if my code will help you to know what is queue.
****************************************************************/
#include <stdlib.h>
#include "queue.h"
#include <stdio.h>
int queue_enter(struct node** pp_queue_header ,struct node** pp_queue_tail,int number)
{
struct node* p_new_node = NULL;
struct node* p_temp_node = NULL;
p_new_node = (struct node*)malloc(sizeof(struct node));
if(p_new_node == NULL)
{
printf("malloc error!\nqueue enter failed\n");
return FAILED;
}
if(!(*pp_queue_tail))
{
*pp_queue_tail = p_new_node;
*pp_queue_header = p_new_node;
p_new_node->data = number;
p_new_node->previous = NULL;
p_new_node->next = NULL;
}
else
{
p_temp_node = (*pp_queue_tail);
p_new_node->data = number;
p_new_node->next = p_temp_node;
p_new_node->previous = NULL;
p_temp_node->previous = p_new_node;
(*pp_queue_tail) = p_new_node;
}
return SUCCESS;
}
queue_out.c
/***********************************************************************
code writer : EOF
code date : 2014.09.13
e-mail: [email protected]
code purpose:
Just a implementation of function queue_out. I would be
happy, if my code will help you to know what is queue.
If something wrong with my code, please touch me by e-mail.
************************************************************************/
#include "queue.h"
#include <stdlib.h>
#include <stdio.h>
int queue_out(struct node** pp_queue_header,struct node** pp_queue_tail)
{
struct node* p_temp_node = NULL;
int ret = 0;
if( !(*pp_queue_header))
{
/*
** There is no way to check the return value.
** when we use "queue_out()". So, you needn't to do
** that.
*/
printf("ATTENTION! There is nothing in the queue.\n");
return EMPTY_QUEUE;
}
p_temp_node = (*pp_queue_header);
(*pp_queue_header) = (*pp_queue_header)->previous;
if(*pp_queue_header)//If there are not only one element left in the queue
{
(*pp_queue_header)->next = NULL;
}
else
{
*pp_queue_tail = NULL;
*pp_queue_header = NULL;
}
ret = p_temp_node->data;
free(p_temp_node);
p_temp_node = NULL;
return ret;
}
queue_print.c
/******************************************************************************
code writer : EOF
code date : 2014.03.07
e-mail: [email protected]
code purpose:
Just a implementation of function queue_print. I would be
happy, if my code will help you to know what is queue.
If something wrong with my code, please touch me by e-mail.
***********************************************************************************/
#include "queue.h"
#include <stdio.h>
void queue_print(struct node* p_queue_tail)
{
struct node* p_temp_node = NULL;
p_temp_node = p_queue_tail;
printf("queue data at this time:\n");
while(p_temp_node != NULL)
{
printf("%d ",p_temp_node->data);
p_temp_node = p_temp_node->next;
}
printf("\n");
}
queue_destory.c
/*********************************************************************
code writer : EOF
code date : 2014.03.07
e-mail: [email protected]
code purpose:
Just a implementation of function queue_enter. I would be
happy, if my code will help you to know what is queue.
*******************************************************************/
#include "BFS.h"
int queue_destory(struct node* p_queue_tail)
{
if(!p_queue_tail)
{
return SUCCESS;
}
struct node* p_temp_node = NULL;
p_temp_node = p_queue_tail->next;
while(p_temp_node != NULL)
{
p_queue_tail->next = p_temp_node->next;
free(p_temp_node);
p_temp_node = p_queue_tail->next;
}
free(p_queue_tail);
return SUCCESS;
}
几个类似的headerfile不一一贴出来了，都很简单. 如下
#ifndef _QUEUE_PRINT_H
#define _QUEUE_PRINT_H 1
extern void queue_print(struct node* p_queue_tail);
#endif
测试结果：
--------------------------------------------------
我始终坚持开源精神，希望看过代码的人能挑出我代码中的瑕疵，也希望我的代码能帮助不懂队列的初学者理解队列
EOF
2014.03.08
于XTU 凌晨零点30分
update: 2014.09.13
补充了数组实现:
Ｃ语言实现——数组实现：
queue.h
#ifndef _QUEUE_H
#define _QUEUE_H
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 10
#define FULL_QUEUE 1
#define UNFULL_QUEUE 0
#define EMPTY_QUEUE 1
#define UNEMPTY_QUEUE 0
#define FAILED_RET -1
#define SUCCESS_RET 0
struct queue
{
int header;
int tail;
int size;
int capacity;
/*
** Old trick :)
*/
int array[0];
};
int queue_init(struct queue** pp_queue,int size);
void queue_release(struct queue* p_queue);
int is_full(struct queue* p_queue);
int is_empty(struct queue* p_queue);
void enqueue(struct queue* p_queue,int num);
int dequeue(struct queue* p_queue);
#endif
queue_test.c
/*******************************************************
code writer : EOF
code date : 2014.09.13
code file : queue_test.c
e-mail : [email protected]
*******************************************************/
#include "queue.h"
int main()
{
struct queue* my_queue = NULL;
if(queue_init(&my_queue,QUEUE_SIZE) < 0)
{
return 0;
}
enqueue(my_queue,1);
enqueue(my_queue,2);
enqueue(my_queue,3);
printf("dequeue: %d\n",dequeue(my_queue));
printf("dequeue: %d\n",dequeue(my_queue));
printf("dequeue: %d\n",dequeue(my_queue));
/*
** Deliberately, I do the dequeue() more than
** enqueue() one time. :)
*/
printf("dequeue: %d\n",dequeue(my_queue));
queue_release(my_queue);
return 0;
}
is_empty.c
/*******************************************************
code writer : EOF
code date : 2014.09.13
code file : is_empty.c
e-mail : [email protected]
*******************************************************/
#include "queue.h"
int is_empty(struct queue* p_queue)
{
if(!p_queue)
{
printf("%s line:%dCan't init! You passed NULL into this function\n",__FUNCTION__,__LINE__);
return ;
}
if(! p_queue->size)
{
return EMPTY_QUEUE;
}
else
{
return UNEMPTY_QUEUE;
}
}
is_full.c
/*******************************************************
code writer : EOF
code date : 2014.09.13
code file : dequeue.c
e-mail : [email protected]
*******************************************************/
#include "queue.h"
int is_full(struct queue* p_queue)
{
if(!p_queue)
{
printf("%s line:%dCan't init! You passed NULL into this function\n",__FUNCTION__,__LINE__);
return FAILED_RET;
}
if((p_queue->size+1) == p_queue->capacity)
{
return FULL_QUEUE;
}
else
{
return UNFULL_QUEUE;
}
}
queue_init.c
/*******************************************************
code writer : EOF
code date : 2014.09.13
code file : queue_init.c
e-mail : [email protected]
*******************************************************/
/******************************************************************
You MUST call queue_cap_init() before you call queue_init().
*******************************************************************/
#include "queue.h"
int queue_init(struct queue** pp_queue,int capacity)
{
if(!pp_queue)
{
printf("%s line:%dCan't init! You passed NULL into this function\n",__FUNCTION__,__LINE__);
return ;
}
else
{
*pp_queue = (struct queue*)malloc(sizeof(struct queue) + capacity*sizeof(int));
if(! (*pp_queue))
{
printf("%s line:%d malloc failed!\n",__FUNCTION__,__LINE__);
return;
}
}
/**************************************************
-----------------------
Input-> tail | | ... | | header -> Output
-----------------------
Just think about it, if the tail is before
the header, the queue is empty.
For this reason, I initialized
header = 0; tail = 1;
Don't panic! :)
***************************************************/
(*pp_queue)->header = 0;
(*pp_queue)->tail = 1;
(*pp_queue)->size = 0;
(*pp_queue)->capacity = capacity;
return SUCCESS_RET;
}
queue_release.c
/*******************************************************
code writer : EOF
code date : 2014.09.13
code file : queue_release.c
e-mail : [email protected]
*******************************************************/
#include "queue.h"
void queue_release(struct queue* p_queue)
{
if(!p_queue)
{
printf("%s line:%dCan't release! You passed NULL into queue_release()\n",__FUNCTION__,__LINE__);
return ;
}
free(p_queue);
}
dequeue.c
/*******************************************************
code writer : EOF
code date : 2014.09.13
code file : dequeue.c
e-mail : [email protected]
*******************************************************/
#include "queue.h"
int dequeue(struct queue* p_queue)
{
if(!p_queue)
{
printf("%s line:%dCan't init! You passed NULL\
into this function\n",__FUNCTION__,__LINE__);
return ;
}
if(is_empty(p_queue) == EMPTY_QUEUE)
{
printf("ATTENTION! dequeue() failed. \
The queue is EMPTY now.\n");
return FAILED_RET;
}
int ret = p_queue->array[(p_queue->header)];
(p_queue->header)--;
/*
** Circular array
*/
if(p_queue->header < 0)
{
p_queue->header = p_queue->capacity-1;
}
(p_queue->size)--;
return ret;
}
enqueue.c
/*******************************************************
code writer : EOF
code date : 2014.09.13
code file : enqueue.c
e-mail : [email protected]
*******************************************************/
#include "queue.h"
void enqueue(struct queue* p_queue,int num)
{
if(!p_queue)
{
printf("%s line:%dCan't init! You passed NULL into this function\n",__FUNCTION__,__LINE__);
return ;
}
if(is_full(p_queue) == FULL_QUEUE)
{
printf("ATTENTION! enqueue() failed. The queue is FULL now.\n");
return ;
}
(p_queue->tail)--;
/*
** Circular array
*/
if(p_queue->tail < 0)
{
p_queue->tail = p_queue->capacity-1;
}
(p_queue->size)++;
p_queue->array[p_queue->tail] = num;
}
测试结果：
How to use two stacks to implement a queue ?
http://blog.csdn.net/cinmyheart/article/details/43588973