December 17, 2013

C# Collections Part 2 : Stack and Queue

Stacks and queues are like arrays or ArrayList. But they are different when it comes to the order of accessing the items. They operate on a different paradigm; namely push-on and pop-off.

Stack: Stack is an abstract data type. The idea of stack is basically in harmony with that we see at restaurants. The plates are piled on to each other. When you need a plate, you just take the one on the top, you do not pull out one from the middle. Again, when the pile is empty, the first plate to be on the pile is the one located at the bottom. The latest plate on the pile is the one situated at the top. So the basic notion associated with Stack operation is Last in First out or LIFO. The earliest element is at the bottom, while the newer elements take position near the top.

Let's jump over to code snippet and analyze a stack operation.

using System;
using System.Collections;

namespace Spells
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack myStack = new Stack();
            myStack.Push("string 1");  // pushing a string type
            myStack.Push(13);    // pushing an integer
            myStack.Push('A');    // pushing a character type

            Console.WriteLine("Current number of items {0}", myStack.Count);

            object obj = myStack.Pop();   // pops of the top item
            Console.WriteLine("The top item was {0}", obj);

            Console.WriteLine("Current number of items {0}", myStack.Count);

            obj = myStack.Peek();   // returns the top item without replacing it
            Console.WriteLine("The top item was {0}", obj);

            Console.WriteLine("Current number of items {0}", myStack.Count);
            
            myStack.Clear();     // deletes all the existing element
            Console.WriteLine("Current number of items {0}", myStack.Count);
            Console.Read(); //keeps the console alive
        }
    }
}
In this particular example, you can see some very basic stack operations like pushing an item in the stack, popping the item, observing the top item of the stack without replacing it and obviously counting the total number of elements on the stack.
  1. Consider line 2. Like ArrayList, the Stack class belongs to Collections class under System namespace.
  2. Line 10 creates a stack object. Since it's an object, we have some classy .NET methods to explore. 
  3. The Push method adds object items in the stack. Take a good note that the added items are object type, so you can add any types of object inside the same stack. This is what we are doing from line 11 to 13.
When we push items inside the stack, the last item remains at the top.
Stack items after line 13
 Line 15 and onwards are interesting. Here is a visual output of the above program.
Stack operation output
The first console output belongs to line 15. As you can see, the current number of items is 3. On line 17, we Pop an item. Keep in mind that a popped item is no more a part of the stack. The popped item is saved in an object instance since all the items are basically objects of different data types. Saving the item in an object instance is an intelligent solution because its generic and you never know what is currently the topmost item. Line 18 prints that item and as you can see, the item was the character 'A'. Line 20 gives the current count of the items and you have rightly guessed that, there are 2 items left.

Line 22 tries to grab the topmost item without deleting it. This method is called Peek. You can see that line 25 shows an unchanged count of items. Finally on line 27, you clear all the current items. So the item count is 0.

Stacks are useful in many different algorithms. Its a beautiful data structure and often helpful in searching algorithms.

Queue: Queues are similar to stack, but the ordering is different. You can think of queues as the line in front of a bank counter; where the person standing at the front gets the service first. New entries take position from the end of the line. So the queues follow the notion First in First out or FIFO. Let's jump in to the code.

using System;
using System.Collections;

namespace Spells
{
    class Program
    {
        static void Main(string[] args)
        {
            Queue qq = new Queue();
            qq.Enqueue("string 1");  // inserts a string object
            qq.Enqueue(5);      // inserts an integer object
            qq.Enqueue('M');     // inserts a character object

            Console.WriteLine("Current number of items {0}", qq.Count);
            
            object obj = qq.Peek();
            Console.WriteLine("Top of the queue item '{0}' ",obj);

            obj = qq.Dequeue();
            Console.WriteLine("Current number of items {0} and the dequeued item was '{1}' ", qq.Count, obj);

            obj = qq.Peek();
            Console.WriteLine("Top of the queue item '{0}' ", obj);
            Console.Read(); //keeps the console alive
        }
    }
}
Things are pretty similar to Stacks. You create a Queue object using the Queue class that .NET provides for you. Like stacks, queues also take items as objects.
  1. From line 11 to 13, the Enqueue method inserts items as objects inside the queue. You can understand the flexibility that C# offers because you are able to insert many different data types.
  2. The Count property returns the number of items currently inside the queue object.
  3. The Peek method on line 17 ensures that you are able to see the top/front of the queue, without destroying the object.
  4. The Dequeue method on line 20 actually destroys the object at the front. C++ doesn't allow you to see the destroyed object, while in C# you can do that comfortably. Consider line 21 where you will see a change of item count.
Here is my console window output.
Queue operation output

Queues are also helpful in searching algorithms. You may also need queues when you program a real life Queue Management software for some organizations.

Go ahead and play with these codes. Who knows, you could find gems in them!

No comments:

Post a Comment