Recently, I was working on a project that uses a buffer queue to send data across the network (yes, this would be my Winsock control). I needed to grab the next item in the queue, modify it, and then stick it back on the top of the queue.
As you all know, you can't do this with a
Queue object, though you can do it with a
Stack - but then, you can't preserve the FIFO method of the
Queue. So, I resorted to using a
Collection, and doing it manually.
While streamlining my control, I decided to combine the
Queue together so it would be simple to do (not to mention read, when looking back through the code). I just couldn't seem to find anything on how to do this (quick Google searches).
I decided to combine the names and call it a Quack, but that's when my searches kicked in and I found out it was called a Deque (pronounced "deck"). I decided to check for any .NET implementations, but all I saw were C++ references. I already had mine made, so I decided to share it here.
This is a rather simple implementation of a Deque, and really quite simple to make yourself - however, the point of the article is to allow you to find the information in order to use it - whether you want to make your own implementation or not.
I have it implementing
ICloneable - just like the
Queue objects. Everything is stored in a private, internal, generic
** Update ** I have updated this to a more complete version of a Deque, as well as using a
LinkedList for better performance. The operations now available were taken from the Deque entry at Wikipedia here[^], and include the following:
Let's get on to the implementation and the use of it, shall we?
Stacks use a last-in, first-out (LIFO) procedure. With stacks, you use the
Push method to put an item onto the stack, and the
Pop method to take an item off the stack.
Let's look at an example of this.
Suppose I put the numbers 1, 2, 3, and 4 into a stack - in that order, it might be visualized like this:
The I take one off using
Pop. This would result in the 4 being taken off, and the stack looking like this:
A queue uses a first-in, first-out (FIFO) procedure. Here, you use the methods
Dequeue to put an item into the queue, and take an item out of the queue, respectively.
Let's look at an example using the exact same procedure of adding 1, 2, 3, and 4 to the queue, in the same order. Here is how the queue would look:
Then, after taking an item off using
Dequeue, I retrieve the 1, leaving me with a queue that looks like:
Building the class
As I'm using a
LinkedList to store the items, we can refer to the Front and Back as the First and Last, respectively. The three methods
Peek, all have two implementations, one for the front and one for the back.
Public Sub PushBack(ByVal obj As Object)
Public Function PopBack(Of dataType)() As dataType
Dim objRet As dataType = PeekBack(Of dataType)()
Public Function PeekBack(Of dataType)() As dataType
If llList.Count = 0 Then Return Nothing
Return DirectCast(llList.Last().Value, dataType)
Notice how easy it is to add and remove to the end of the
LinkedList. Adding and removing from the front is just as easy as using the
First methods of the
The biggest difficulty in creating this class was getting it to properly implement the three interfaces:
ICloneable. Fortunately though, the
List was able to provide the abilities of those function. See the source code for more details.
Using the Code
Really, this is as simple to use as the
Queue classes; if you know how to use them, you can use this.
But for those that don't know how to use them, here is a quick example of how to use this class. The state of the
Deque after any given line is shown in the comments, with the top of the list being on the left.
Dim q As New Deque
Dim objRet As Object
q.PushBack(1) q.PushBack(2) q.PushBack(3) q.PushBack(4) objRet = q.PopFront() q.PushFront(-1) q.PushFront(9) objRet = q.PopFront() objRet = q.PopBack() objRet = q.PopFront() objRet = q.PopBack() objRet = q.PopFront()
Points of Interest
The example project "animated" various examples. This was very simply done using the
Sleep method to hold the display for a bit, not to mention sort of fun to build. It graphically shows how a stack/queue/deque works.
I just made this as part of another project, and hope that others can benefit from my playing around with the code.
Have fun with your own coding projects!