.NET Deque

• Download source code and sample - 28.4 KB

Introduction

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 Stack and 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 ICollection, IEnumerable, and ICloneable - just like the Stack and Queue objects. Everything is stored in a private, internal, generic LinkedList(Of Object).

** 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: PushBack, PushFront, PopBack, PopFront, PeekBack, and PeekFront.

Let's get on to the implementation and the use of it, shall we?

Stacks

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:

4
3
2
1

The I take one off using Pop. This would result in the 4 being taken off, and the stack looking like this:

3
2
1

Queues

A queue uses a first-in, first-out (FIFO) procedure. Here, you use the methods Enqueue and 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:

1
2
3
4

Then, after taking an item off using Dequeue, I retrieve the 1, leaving me with a queue that looks like:

2
3
4

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 Push, Pop, and Peek, all have two implementations, one for the front and one for the back.

Public Sub PushBack(ByVal obj As Object)
    llList.AddLast(obj)
End Sub

Public Function PopBack(Of dataType)() As dataType
    Dim objRet As dataType = PeekBack(Of dataType)()
    llList.RemoveLast()
    Return objRet
End Function

Public Function PeekBack(Of dataType)() As dataType
    If llList.Count = 0 Then Return Nothing
    Return DirectCast(llList.Last().Value, dataType)
End Function

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 AddFirst, RemoveFirst, and First methods of the LinkedList.

The biggest difficulty in creating this class was getting it to properly implement the three interfaces: ICollection, IEnumerable, and 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 Stack and 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) ' 1
q.PushBack(2) ' 1, 2
q.PushBack(3) ' 1, 2, 3
q.PushBack(4) ' 1, 2, 3, 4
objRet = q.PopFront() ' 2, 3, 4
q.PushFront(-1) ' -1, 2, 3, 4
q.PushFront(9) ' 9, -1, 2, 3, 4
objRet = q.PopFront() ' -1, 2, 3, 4
objRet = q.PopBack() ' -1, 2, 3
objRet = q.PopFront() ' 2, 3
objRet = q.PopBack() ' 2
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.

Summary

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!