In yesterday's article ("C# OOP: Creating a List using Composition") we used classes to create a List data structure. Today we're going to create a queue and a stack using the same principle.
The above diagram shows what a queue looks like in theory. (When I first drew this diagram, I made the mistake of putting the orange labels at the bottom. If you think about it for a minute, you'll realise why it's a horribly wrong thing to do.) There are a number of people in the queue, and they all get served one by one by the dude at the desk. Unless you're in Malta, the guy at the back typically doesn't get served before the guy at the front.
A queue is pretty much a special kind of list. It has the internal structure of a list, but supports two operations: Enqueue and Dequeue. Enqueue means adding an item to the end of the queue, while Dequeue means removing the item at the front of the queue and doing something with it.
We can start off with yesterday's code for the List:
class ListItem
{
public ListItem Next;
public String Data;
public ListItem(String data)
{
this.Next = null;
this.Data = data;
}
}
class List
{
public ListItem Head;
public ListItem Tail;
public List()
{
this.Head = null;
this.Tail = null;
}
public void Add(String data)
{
ListItem item = new ListItem(data);
if (this.Head == null) // list is empty
{
this.Head = item;
this.Tail = item;
}
else
{
// set (old) tail's Next to new item
this.Tail.Next = item;
// new item is the new tail
this.Tail = item;
}
}
}
Since a queue is so similar to a list, there isn't much point in simply rewriting lots of code to create the queue. As much as possible, we should reuse code. This is called the Don't Repeat Yourself (DRY) principle.
Let's start the queue based on this code:
class Queue : List
{
}
This means that Queue is a List. This is just like saying Dog is a mammal: the dog inherits the characteristics of a mammal (it has fur, doesn't lay eggs, etc) and perhaps adds some particular characteristics of its own (barks, wags tail, drools, etc). In OOP, this actually means that the Queue inherits the data members and methods of the List. So in our Main() method, we can already use the Queue as if it were a List:
public static void Main(string[] args)
{
Console.Title = "C# OOP Inheritance";
Queue queue = new Queue();
queue.Add("Bill Clinton");
Console.WriteLine(queue.Head.Data);
Console.ReadLine();
}
In Queue, we can add the Enqueue() and Dequeue() methods that are queue-specific and don't belong in the List:
class Queue : List
{
public void Enqueue(String data)
{
this.Add(data);
}
public String Dequeue()
{
if (this.Head == null)
{
return null;
}
else
{
// keep reference to the first guy in the queue
String oldHead = this.Head.Data;
// set head to the second guy in the queue
this.Head = this.Head.Next;
// return the guy who was first, for consumption
return oldHead;
}
}
}
For Enqueue(), we use the Add() method inherited from List, since it adds items to the end of the list and is enough to achieve what we need for Enqueue(). In Dequeue(), we return the first item in the queue, and the second item takes its place.
In Main(), we can try this out:
Queue queue = new Queue();
queue.Enqueue("Bill Clinton");
queue.Enqueue("Paris Hilton");
queue.Enqueue("Chuck Norris");
String item = String.Empty;
while (item != null)
{
item = queue.Dequeue();
Console.WriteLine(item);
}
Console.ReadLine();
...and the result is...
That's great, but the extent of reusability of the List doesn't end here. Let's also create a Stack.
A stack is just what the name suggests: a bunch of things on top of each other. Books and Pringles make really good examples of stacks. You add things to the top of the stack, and remove them from the top. You can't remove items from the bottom of a stack without making a mess.
The stack supports two operations: Push (add item to top of stack) and Pop (remove item from top of stack - think Pringles). Again, we can inherit from the List and implement this particular functionality:
class Stack : List
{
public void Push(String data)
{
this.Add(data);
}
public String Pop()
{
String data = null;
if (this.Head == null) // stack is empty
{
data = null;
}
else if (this.Head.Next == null) // stack has just one item
{
data = this.Head.Data;
this.Head = null;
this.Tail = null;
}
else // stack has at least two items
{
ListItem currentItem = this.Head;
while (currentItem.Next != this.Tail)
currentItem = currentItem.Next;
data = this.Tail.Data;
currentItem.Next = null;
this.Tail = currentItem;
}
return data;
}
}
Uhhh... Pop() is a little more complicated than Dequeue() because we need to first navigate to the item before the tail, and we have to do that from the head since the Tail doesn't have any backwards pointers. We could make this more efficient by using a doubly linked list instead, but that's beside the point.
We can now test the Stack:
Stack stack = new Stack();
stack.Add("One");
stack.Add("Two");
stack.Add("Three");
stack.Add("Four");
String item = String.Empty;
while (item != null)
{
item = stack.Pop();
Console.WriteLine(item);
}
Console.ReadLine();
...which results in...
You'll notice that the output is in reverse order compared to how we added the items. That's because a stack is a Last In First Out (LIFO) data structure, while a queue is First In First Out (FIFO).
Fantastic. In this article we used inheritance to reuse functionality in the List and write specialised code for Queues and Stacks without duplicating code. Effectively we ended up with the following inheritance tree:
Queue and Stack are both Lists in the same way that Dogs and Cats are both Mammals. A better way of saying this is that Queue and Stack extend List (in fact Java uses the extends keyword instead of the colon operator used by C# and C++).
It is also important to know that in C#, all classes implicitly extend the Object class, which provides some methods such as ToString() and GetHashCode() to all classes. We'll learn more about these in the coming articles.
That's all for today... come back for the next article! :)
