The Use of Queues in C#

• Download sample 1 - 4.49 Kb
• Download sample 2 - 4.93 Kb

Introduction

I consider queues, stacks, dequeues, and linked lists as the basic sets of programming tools that we have at our disposal. In reviewing the available queue examples, most, if not all, dealt with simple objects such as strings and integers. These two queue examples have a little more detail to them.

Background

Firstly, a queue is a programmatic structure that simulates the lines that we know from real life. Standing in line to buy a ticket, waiting for your turn in a bank, or boarding a train. The order of service is determined by the time that you arrived and got in line. These are also described as first in first out (FIFO) structures.

In .NET, we get access to a built in queue through the addition of the collection class to your list of included references at the start of the program:

using System.Collections

This will give you access to the Queue, Stack, Arraylist and other classes. I will discuss these structures in other articles that follow.

The example that I will use for the queue is that of customers arriving at a bank. Just before opening, customers arrive prepared to do business at the bank, and they get in line. The tellers come to their station, and begin to service these customers one at a time.

There is a large field of study that involves the arrival of customers: when a queue is too large and the customer abandons the task, and the efficiency of multiple servers for a queue. We may discuss that in the later articles.

First Example

The first thing I did was to create a simple data structure that represents a customer and his transaction. You can see, we are just looking for sufficient detail to make the example have substance. I kept the data types simple to allow the program to focus on the queue.

struct BankCustomer
{
    internal string name;
    internal string bankingActivity;
    internal int accountNumber;
    internal float amount;
}

I then added a small enumeration to describe the allowable banking transactions that were available for the customer:

enum BankingActivity
{ deposit, withdrawl, transferFunds }

The use of a struct was driven by not needing to really interact with the customer, and each customer was independent of each other. The original program that I used for this was a queue of complex commands that would be passed to another program to execute in the order that they arrived, so a structure was a perfect design element for that problem.

The next thing to do is to create a queue, which is done with the following line of code:

Queue localBankQueue = new Queue();

What can we do with the queue? Well, like most things, we will use the 80:20 rule. That is that, 80% of the work can be done with 20% of the methods available. The methods that this program primarily uses are:

• Enqueue(), which means get into the line.
• Dequeue(), which means take the first object from the queue.

The other important element is the count property which will tell how many items are in the queue.

We make a bank customer that takes advantage of the struct that we have built for him.

private BankCustomer localBankCustomer;

The first customer shows up with the information needed to do business:

// first customer
localBankCustomer.name = "J P Morgan";
localBankCustomer.bankingActivity = BankingActivity.deposit.ToString();
localBankCustomer.accountNumber = 335445;
localBankCustomer.amount = 5600.00F;

and gets in line:

localBankQueue.Enqueue(localBankCustomer);

This is very nice because we now have an object with several properties in the queue, not a simple string or integer. A few more customers come in and get in line, and we have a small line.

// second customer
localBankCustomer.name = "Butch Cassidy";
localBankCustomer.bankingActivity = 
     BankingActivity.transferFunds.ToString();
localBankCustomer.accountNumber = 555445;
localBankCustomer.amount = 3500.00F;

localBankQueue.Enqueue(localBankCustomer); 

// third customer
localBankCustomer.name = "John Dillinger";
localBankCustomer.bankingActivity = 
     BankingActivity.withdrawl.ToString();
localBankCustomer.accountNumber = 12345;
localBankCustomer.amount =  2000.00F;

localBankQueue.Enqueue(localBankCustomer);

Before we do any processing, we will look and see how long the line is.

This can be done with the property, count.

Console.WriteLine("Count of Items in the Queue:" + 
                  localBankQueue.Count);

The next thing is to remove the first item from the queue, i.e., begin to serve the customers. Remember, this will be the first customer that arrived, a queue being a first in first out (FIFO) structure. We do this by using the Dequeue(), pronounced DQ, method. Because we are using a struct rather than another object, we have to assign what comes off to the struct.

localBankCustomer = (BankCustomer)localBankQueue.Dequeue();

The important thing to observe is the cast, (BankCustomer), of what is being dequeued to a localBankCustomer prior to its assignment. If you don't do this, you will get the message: “Error 1 Cannot implicitly convert type 'object' to ' QueueDemoClass.BankCustomer'. An explicit conversion exists (are you missing a cast?)” with a line number directing you to the line that needs the cast.

Now, you have the localBankCustomer filled with the struct of the first customer in the queue, and you can examine it and work with it.

Console.WriteLine("Name: " + localBankCustomer.name);
Console.WriteLine("Activity: " + localBankCustomer.bankingActivity);
Console.WriteLine("Account Number: " + localBankCustomer.accountNumber);
Console.WriteLine("Amount: " + localBankCustomer.amount.ToString());
Console.WriteLine("Count of Items in the Queue after first Dequeue:" + 
                  localBankQueue.Count);s<BR>

This produces the following output:

Name:  J P Morgan
Activity:  deposit
Account Number:335445  
Amount:  5600.00

You are now at the point where you could process the information about the customer if you desired. To get to the other customers in the queue, the most straightforward approach is to iterate through the queue, using a while loop, until the queue is empty.

do
{
    localBankCustomer = (BankCustomer)localBankQueue.Dequeue();
    // process the customers request 
} while (localBankQueue.Count != 0);

There you have it. An example that is a little more real worldly than a queue of integers. Here are the basic ideas again:

• A queue is a FIFO, first in first out data structure.
• A queue can hold any object.
• You add items using the .Enqueue(obj) method.
• You remove items using the .Dequeue() method.
• You must cast the object type when you remove an item from the queue.
• You can keep track of the number of items in the queue using the count() method.

The output looks like the following:

Count of Items in the Queue at the start :3
 
Name: J P Morgan
Activity: deposit
Account Number: 335445
Amount: 5600
Count of Items in the Queue after first Dequeue:2
------------------------------------------------------
 
Name: Butch Cassidy
Activity: transferFunds
Account Number: 555445
Amount: 3500
Count of Items in the Queue after Dequeue: 1
-------------------------------------------------------
 
Name: John Dillinger
Activity: withdrawl
Account Number: 12345
Amount: 2000
Count of Items in the Queue after Dequeue: 0
--------------------------------------------------------

Second Example

Extending the example we have just done, but instead of using a struct to model the bank customer, we will make a BankCustomer class and add a Bank class to represent the bank. To make it a little more instructive, I have added a small amount of processing at the bank so that when a customer arrives at the teller's station, the teller will have to process his request.

public class BankCustomer
{
  
    private string customerName;
    private string customerActivity;
    private int customerNumber;
    private int customerAmount;

    public  BankCustomer() { }
    public  BankCustomer(string name, 
            string bankingActivity, 
            int accountNumber, int amount)
    {
        customerName    = name;
        customerActivity = bankingActivity ;
        customerNumber =accountNumber  ;
        customerAmount = amount;
    }
    public string name
    {  get { return customerName; }
        set { customerName = value; }
    }
    public string bankingActivity
    {  get { return customerActivity; }
        set { customerActivity = value; }
    }
    public int accountNumber
    {   get { return customerNumber; }
        set { customerNumber = value; }
    }
    public int amount
    {  get { return customerAmount; }
        set { customerAmount = value; }
    }
}

You can see I have encapsulated the customer's properties and added a constructor to populate them.

The Bank class in part:

public class Bank
{
    public Queue TellerLine = new Queue();
    public int AmountOnDeposit = 10000;
    public enum BankingActivity
    { deposit, withdrawl, transferFunds };
}

I have added the BankingActivity enum to the bank and, as would be appropriate, the Queue, called TellerLine, belongs to the bank. In order to do some simple processing, I have added the variable AmountOnDeposit, which represents the cash in the vault. In the Main method, we:

{
   // create a Bank
   Bank ThomastonBankandTrust = new Bank();
    // create a customer
   BankCustomer JP = new BankCustomer("J P Morgan", 
      Bank.BankingActivity.deposit.ToString(), 335445 , 30000);  
   // add the customer to the TellerLine
   ThomastonBankandTrust.TellerLine.Enqueue(JP);

This is the same thing we did before, but rather than “enquing” a struct, we enqueued the BankCustomer object that we created, JP. We now have several customers coming in:

BankCustomer Butch = new BankCustomer("Butch Cassidy", 
                         Bank.BankingActivity.transferFunds.ToString(), 
                         555445, 3500);
BankCustomer Sundance = new BankCustomer("Sundance Kid", 
                        Bank.BankingActivity.withdrawl.ToString(), 
                        555444, 3500);
BankCustomer John = new BankCustomer("John Dillinger", 
                        Bank.BankingActivity.withdrawl.ToString(), 
                        12345, 2000);

and join the queue.

ThomastonBankandTrust.TellerLine.Enqueue(Sundance);
ThomastonBankandTrust.TellerLine.Enqueue(Butch);
ThomastonBankandTrust.TellerLine.Enqueue(John);

As you can see, now that we have made each customer its own object, we can add them in after all of them are created.

Sidebar

There may be occasions that you would want to examine the members of the queue without removing anyone from the queue. We have several options that we will explore: Peek(). Peek allows us to look at the next object that will be removed from the queue without removing it. However, because we have an object in the queue, if we do:

Console.WriteLine("Peek: " + ThomastonBankandTrust.TellerLine.Peek());

we will get QueueDemoClass.BankCustomer which tells us what is in line but not who is in line. To see who was next in line, I created a simple method.

public void QueuePeek(Queue localQeue)
{
    BankCustomer tempCustomer = new BankCustomer();
    tempCustomer = (BankCustomer)localQeue.Peek();
    Console.WriteLine("The next Customer in line: " + 
                      tempCustomer.name);
}

We create a temporary customer, use the Peek method, casting it to a BankCustomer, and then look at the customer's name.

Let us suppose we want to examine the entire contents of the queue prior to doing any processing. In that case, the bank may want to have security examine the line for known bank robbers, John Dillinger, for example, and be prepared to arrest him when he arrives at the teller's station. I created two methods, one that makes a copy of the queue and iterates through that copy, and another that uses the queue's enumerator to move through the queue. Neither methods disturb the queue, and both methods give us a list of who is in the queue.

public void QueueContentsCopy(Queue localQueue)
{
    BankCustomer tempCustomer = new BankCustomer();
    Queue copyoflocalQueue = new Queue();
    // make the copy 
    copyoflocalQueue = (Queue)localQueue.Clone();
    Console.WriteLine(" ");
    Console.WriteLine("View the queue using a copy");
    do
    {
        tempCustomer = (BankCustomer)copyoflocalQueue.Dequeue();
        Console.WriteLine("Name: " + tempCustomer.name + ",  
                          Activity: " + tempCustomer.bankingActivity + 
                          ",  Account no: " + 
                          tempCustomer.accountNumber.ToString() + 
                          ", Amount $" + 
                          tempCustomer.amount.ToString());
    } while (copyoflocalQueue.Count != 0);
}

public void QueueContentsEnum(Queue localQueue)
{
    BankCustomer tempCustomer = new BankCustomer();
    // get the built in enumerator
    System.Collections.IEnumerator en = localQueue.GetEnumerator();
    Console.WriteLine(" ");
    Console.WriteLine("View the queue using an enumerator");
    while (en.MoveNext())
    {
        tempCustomer = (BankCustomer)en.Current;
        Console.WriteLine("Name: " + tempCustomer.name + 
                          ",  Activity: " + 
                          tempCustomer.bankingActivity + 
                          ",  Account no: " + 
                          tempCustomer.accountNumber.ToString() + 
                          ", Amount $" + tempCustomer.amount.ToString());
    }
}

At this point, we are ready to receive customers and process their requests: deposit, withdraw, and transfer their money. We have the variable AmountOnDeposit to serve as the vault for the deposits and withdrawals:

public void ProcessCustomerRequest(BankCustomer customer)
{
    Console.WriteLine("Customer: " + customer.name);
    Console.WriteLine("Activity: " + customer.bankingActivity);
    if ((customer.bankingActivity == "deposit") | 
         customer.bankingActivity == "transferFunds")
    {
        AmountOnDeposit += customer.amount;
        Console.WriteLine("Amount on Deposit: " + AmountOnDeposit);
    }
    if (customer.bankingActivity == "withdrawl" && 
       (customer.name != "John Dillinger"))
    {
        AmountOnDeposit -= customer.amount;
        Console.WriteLine("Amount on Deposit: " + AmountOnDeposit);
    }
    if ((customer.bankingActivity == "withdrawl")&& 
        (customer.name == "John Dillinger"))
    {
        AmountOnDeposit  = 0;
        Console.WriteLine("Big Bank Robery !!!    Amount on Deposit: " + 
                          AmountOnDeposit);
    }
    Console.WriteLine("------------------------------------------------");
}

The processing produces this as an output:

Peek: QueueDemoClass.BankCustomer
The next Customer in line: J P Morgan
 
View the queue using a copy
Name: J P Morgan,  Activity: deposit,  
      Account no: 335445, Amount $30000
Name: Sundance Kid,  Activity: withdrawl,  
      Account no: 555444, Amount $3500
Name: Butch Cassidy,  Activity: transferFunds,  
      Account no: 555445, Amount $3500
Name: John Dillinger,  Activity: withdrawl,  
      Account no: 12345, Amount $2000
 
View the queue using an enumerator
Name: J P Morgan,  Activity: deposit,  
      Account no: 335445, Amount $30000
Name: Sundance Kid,  Activity: withdrawl,  
      Account no: 555444, Amount $3500
Name: Butch Cassidy,  Activity: transferFunds,  
      Account no: 555445, Amount $3500
Name: John Dillinger,  Activity: withdrawl,  
      Account no: 12345, Amount $2000

Count of items in queue after copy & enum :4

Customer: J P Morgan
Activity: deposit
Amount on Deposit: 40000
------------------------------------------------
Customer: Sundance Kid
Activity: withdrawl
Amount on Deposit: 36500
------------------------------------------------
Customer: Butch Cassidy
Activity: transferFunds
Amount on Deposit: 40000
------------------------------------------------
Customer: John Dillinger
Activity: withdrawl
Big Bank Robery !!!    Amount on Deposit: 0
------------------------------------------------

Points of Interest

The important part of going through this was the realization that the object that is in the queue needs to be cast back into an instance of its own type before it can be used. The other point is that queues are dynamic structures, and their size does not need to be declared at design time nor does it have to be resized at run time.

History

No changes to date.