I have to implement First In First Out queue in R for my work. Is there any library available or do I have to implement by myself. If I have to implement which data structure would be good array(matrix) or list.
Shane's code is elegant, but it implements a stack and not a queue. Note that enqueue and dequeue are both accessing queue$next.element, which is LIFO behavior.
I've taken his idea and written a FIFO data structure. The main difference is that you have to maintain a reference to the end of the queue. I've also written an "is.empty" check, which I didn't find in any of the queue implementations I found online. (As I've written it, it's basically a linked list where each element keeps track of "next" and "prev" elements. Strictly speaking, you only need to keep track of one of these for a queue, but I thought it would be good to leave both in so that the extension to a double-ended queue/deque would be clear.)
simple test code is provided at the end.
{
new.queue
Check this links:
http://www.r-bloggers.com/implementing-a-queue-as-a-reference-class/
http://www.maths.lancs.ac.uk/~rowlings/R/Queue/
Two ideas:
http://r.789695.n4.nabble.com/queue-implementation-td2529272.html
http://www.r-bloggers.com/simulating-a-queue-in-r/
I would not recommend the approach that Fabian describes unless you plan on only maintaining relatively short queues. If you had to implement a queue in c++ either an array or a list could be used. If you have to build it in R, I would recommend using environments (see below). If the problems you are interested in are relatively small, then Fabian's implementation may be fine in practice. But here's an example where it performs very poorly.
To execute the command
mylist
I am bit confused with this implementation for dequeue. could you please explain?
It is a pretty confusing implementation. This is mostly because R does not provide the user with pointer types. The lack of pointer types makes implementing recursive data structures in R more difficult than it would be in c++ or even Fortran.
The closest thing that R has to a pointer is an environment. Roughly speaking, environments are a pointer to a container in R which can contain any object, including other environments. When we call a function with an environment as an argument, the contents of the environment are passed by reference, but not the environment itself. For example:
If we create a new environment, data.env
data.env
Shane's code is elegant, but it implements a stack and not a queue. Note that enqueue and dequeue are both accessing queue$next.element, which is LIFO behavior.
I've taken his idea and written a FIFO data structure. The main difference is that you have to maintain a reference to the end of the queue. I've also written an "is.empty" check, which I didn't find in any of the queue implementations I found online. (As I've written it, it's basically a linked list where each element keeps track of "next" and "prev" elements. Strictly speaking, you only need to keep track of one of these for a queue, but I thought it would be good to leave both in so that the extension to a double-ended queue/deque would be clear.)
simple test code is provided at the end.
{
new.queue
Hope these help...
http://mcu.edu.tw/~hyu/Queue-534.xls
http://www.csun.edu/~aa2035/CourseBase/WaitingLine/Excel/QueueMacros.xls
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Statistical Software
- R Statistical Package