Data structures in C# – Part 3 – Queues

by ⋅ Leave a Comment

Posts in this Series:
Linked Lists
Stacks
Queues (this post)
Trees

In the last post, I’ve talked about stacks, a LIFO (Last In – First out) data structure. In this post, I will talk about queues, a FIFO (First in – First out) data structure. A queue is like any box office queue, where the first in line are served first.

The queue has these operations:

  • Enqueue – adds an item to the end of the queue
  • Dequeue – Removes an item from the start of the queue

Like the stack, you can’t add or remove items from the middle of the queue. The node structure is the same as the nodes used in the linked list and in the stack. The Enqueue method is like this:

[sourcecode language=”csharp” padlinenumbers=”true”]
public void Enqueue(T obj)
{
NodeList<T> node = new NodeList<T>() { Data = obj };
_count++;
if (_last == null)
{
_last = _top = node;
return;
}
_last.Next = node;
_last = node;
}
[/sourcecode]

Note that there is a subtle change from the stack code: we are using an extra pointer for the last node, so we can get fast inserts and deletes in the queue.

The Dequeue method is:

[sourcecode language=”csharp”]
public T Dequeue()
{
if (_top != null)
{
NodeList<T> result = _top;
_top = _top.Next;
_count–;
return result.Data;
}
throw (new InvalidOperationException("The queue is empty"));
}

[/sourcecode]

We remove the top node from the queue. With these two operations, the queue is ready. We can also do the same way as the stack and use a linked list to implement it:

[sourcecode language=”csharp”]
public class QueueAsList<T>
{
private readonly LinkedList<T>_linkedList = new LinkedList<T>();

public void Enqueue(T obj)
{
_linkedList.Insert(obj);
}

public T Dequeue()
{
if (_linkedList.Count == 0)
throw (new InvalidOperationException("The queue is empty"));
var result = _linkedList[0];
_linkedList.Remove(result);
return result;
}

public int Count => _linkedList.Count;

public void Clear()
{
_linkedList.Clear();
}
}
[/sourcecode]

Now we have our implementations of the queue and we can move to the next article, the Tree.

image

The source code for this series of articles is in https://github.com/bsonnino/DataStructures

Data structures in C# – Part 2 – Stacks

by ⋅ Leave a Comment

Posts in this Series:
Linked Lists
Stacks (this post)
Queues
Trees

In the last post I’ve talked about one of the most basic data structures, the linked list. In this post we will start talking about stacks.

A stack is a LIFO (Last In –First out) data structure, it’s like a pile of plates: you start stacking them and, when you need one, you remove the top of the pile, the last you’ve put.

Its structure is very similar to the linked list, but you have these operations on it:

  • Push – add a new item to the stack
  • Pop – remove the top item from the stack
  • Peek – take a look at the top of the stack but don’t remove the item

As you can see, you can only operate on the top of the stack, you cannot add or remove an item in the middle of the stack. As we’ve seen in the last article, creating a generic stack is pretty much the same as creating a non generic one, so we will only develop a generic one in this article.

The Push method will add a new item in the top of the stack, thus setting the _top field to point to the newly created node:

[sourcecode language=”csharp” padlinenumbers=”true”]
private NodeList<T> _top;
private int _count;

public void Push(T obj)
{
var node = new NodeList<T>;
{
Data = obj,
Next = _top
};
_top = node;
_count++;
}
[/sourcecode]

The Pop method checks the top of the stack. If it’s null (empty stack), it throws an InvalidOperationException. If the stack isn’t empty, the top and count are updated and the old top is returned:

[sourcecode language=”csharp”]
public T Pop()
{
if (_top == null)
throw (new InvalidOperationException("The stack is empty"));
var result = _top;
_top = _top.Next;
_count–;
return result.Data;
}
[/sourcecode]

Peek is very simple, it only checks if there is any data in the top of the stack and returns its data:

[sourcecode language=”csharp”]
public T Peek()
{
if (_top != null)
return _top.Data;
throw (new InvalidOperationException("The stack is empty"));
}
[/sourcecode]

Our stack is ready. If you take a closer look, you will see that the stack can be implemented with a Linked List: Push will insert an item at the top (with Insert), Pop will get the top item, remove it and return it. Peek will get the top item and return it:

[sourcecode language=”csharp”]
public class StackAsList<T>;
{

private readonly LinkedList<T> _linkedList = new LinkedList<T>();

public void Push(T obj)
{
_linkedList.Insert(obj);
}

public T Peek()
{
if (_linkedList.Count == 0)
throw (new InvalidOperationException("The stack is empty"));
return _linkedList[_linkedList.Count-1];
}

public T Pop()
{
if (_linkedList.Count == 0)
throw (new InvalidOperationException("The stack is empty"));
var result = _linkedList[_linkedList.Count – 1];
_linkedList.Remove(result);
return result;
}

public int Count => _linkedList.Count;

public void Clear()
{
_linkedList.Clear();
}

}
[/sourcecode]

Pretty simple, no? Now we have two implementations of the stack, in the next article we will see the Queue.

image

The source code for this series of articles is in https://github.com/bsonnino/DataStructures