Working with Queues and Stacks

Introduction

Apart from Hashtables, queues and stacks are probably the most common Collection classes. With this article I will explain the ins and outs of queues and stacks.

Again with the Collections?

Yes. After you have seen how versatile the Collections Namespace is, you'll never again cringe with fear when you encounter it, and you will - many times!

What is a Queue?

When you go to a bank or a grocery store you have to stand in a queue for service. The first person in the queue is the first person helped. The last person in the queue is the last person helped. Agreed? Now, the Queue class works the same way. It is what is called a FIFO ( First in, First out ) list.

As this MSDN article mentions: Queues are useful for storing messages in the order they were received for sequential processing. This class implements a queue as a circular array. Objects stored in a Queue are inserted at one end and removed from the other.

What is a Stack?

A Stack is the opposite of a Queue. Where a Queue is a FIFO list, a Stack represents a LIFO (Last in, First out ) list. This analogy is the same as a stack of books. The first book you place on your desk, will remain at the bottom, whereas the last book that you have placed on the stack, will most likely be used / discarded first.

MSDN explains a Stack as: simple last-in-first-out (LIFO) non-generic collection of objects

Sample Programs

If you still find these two classes hard to understand, I have worked out samples for you. These samples are in VB.NET and C#. You are welcome following the next few steps in creating your project in your specific language ( VB.NET or C# ).

Design

Our design is quite simple. It looks like the following picture:

Figure 1 - Our design

Coding

Add the necessary Namespace to your project.

VB.NET :

Imports System.Collections

C# :

using System.Collections;

Next, our class level variables:

VB.NET :

    Private qMyQueue As New Queue 'Our Queue object
    Private sMyStack As New Stack 'Our Stack Object

C# :

        private Queue qMyQueue = new Queue(); //Our Queue object
        private Stack sMyStack = new Stack(); //Our Stack Object

Store values inside the Queue object.

VB.NET :

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

        'Store values inside Queue
        qMyQueue.Enqueue("first")
        qMyQueue.Enqueue("second")
        qMyQueue.Enqueue("third")
    End Sub

C# :

        private void Button1_Click(object sender, EventArgs e)
        {
            //Store values inside Queue
            qMyQueue.Enqueue("first");
            qMyQueue.Enqueue("second");
            qMyQueue.Enqueue("third");
        }

Populate the Stack object:

VB.NET :

    Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click

        'Populate Stack Object
        sMyStack.Push("first")
        sMyStack.Push("second")
        sMyStack.Push("third")
    End Sub

C# :

        private void Button2_Click(object sender, EventArgs e)
        {
            //Populate Stack Object
            sMyStack.Push("first");
            sMyStack.Push("second");
            sMyStack.Push("third");
        }

This is where it gets interesting! Once we have our lists set up, there are numerous ways in which we can access the items inside the lists. With the Queue object we can use its Dequeue method. This will in effect release the first object added to the list, for example.

VB.NET :

Console.WriteLine("(Dequeue) {0}", qMyQueue.Dequeue())

C# :

Console.WriteLine("(Dequeue) {0}", qMyQueue.Dequeue())

Would remove first from the list, next time it is called, second will be removed and so on.

With the Stack object we would need to use the Pop method.

VB.NET :

Console.WriteLine("(Pop){0}", sMyStack.Pop())

C# :

Console.WriteLine("(Pop){0}", sMyStack.Pop());

The above code for the Stack object would remove the last item in the list, so in our example, third, then second, then first.

We could also make use of a loop to iterate through the Queue and Stack completely:

VB.NET :

	'Queue
        While qMyQueue.Count > 0
            Dim obj As Object = qMyQueue.Dequeue
            Console.WriteLine("from Queue: {0}", obj)
        End While

	'Stack
        While sMyStack.Count > 0
            Dim obj As Object = sMyStack.Pop
            Console.WriteLine("from Stack: {0}", obj)
        End While

C# :

	//Queue
	while (qMyQueue.Count > 0) {
		object obj = qMyQueue.Dequeue;
		Console.WriteLine("from Queue: {0}", obj);
	}

	//Stack
	while (sMyStack.Count > 0) {
		object obj = sMyStack.Pop;
		Console.WriteLine("from Stack: {0}", obj);
	}

The IEnumerator Interface

I decided to mention this Interface here as I am trying to teach you how to use the Collection classes properly. The IEnumerator Interface provides a way for us to enumerate, or iterate, or simply, loop through the certain Collection class. It exposes methods such as MoveNext, which moves to the next item in the list, and Current, which shows the current item in the list. We need an IEnumerable Interface object so that it can expose (identify) the enumerator, which supports a simple iteration over a non-generic collection.

MSDN IEnumerator

MSDN IEnumerable

Let us add this functionality. Add the following procedure to your code.

VB.NET :

    Public Sub DisplayValues(ByVal MyQueueCollection As IEnumerable, ByVal MyStackCollection As IEnumerable)

        Dim MyQueueEnumerator As IEnumerator = MyQueueCollection.GetEnumerator() 'Get list(s) to iterate through
        Dim MyStackEnumerator As IEnumerator = MyStackCollection.GetEnumerator()

        While MyQueueEnumerator.MoveNext() 'Move to next item
            ListBox1.Items.Add(MyQueueEnumerator.Current.ToString())

        End While

        While MyStackEnumerator.MoveNext()
            ListBox2.Items.Add(MyStackEnumerator.Current.ToString()) 'Display current item
        End While


    End Sub

C# :

        public void DisplayValues(IEnumerable MyQueueCollection, IEnumerable MyStackCollection)
        {
            IEnumerator MyQueueEnumerator = MyQueueCollection.GetEnumerator(); //Get list(s) to iterate through
            IEnumerator MyStackEnumerator = MyStackCollection.GetEnumerator();

            while (MyQueueEnumerator.MoveNext()) //Move to next item
            {
                ListBox1.Items.Add(MyQueueEnumerator.Current.ToString());

            }

            while (MyStackEnumerator.MoveNext())
            {
                ListBox2.Items.Add(MyStackEnumerator.Current.ToString()); //Display current item
            }

        }

Finally, add the call to this procedure inside Button3's Click event.

VB.NET :

    Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
        DisplayValues(qMyQueue, sMyStack)
    End Sub

C# :

        private void Button3_Click(object sender, EventArgs e)
        {
            DisplayValues(qMyQueue, sMyStack);
        }

When the Show Values button is clicked, it would resemble Figure 2:

Figure 2 - Values of both lists

Not so complicated now is it? Hopefully not. I am attaching working samples of these exercises for you, so play around with them and experiment - that is one of the best ways to learn.

Conclusion

Thanks for reading this article. I hope you have enjoyed it and benefited from it. Do not be scared of Collection anymore, they're quite easy! Until next time, cheers!