Queue-Based Lists
Queue-Based Lists
Queues Fundamentals
Introduction
A queue is a list in which the first item added to the list will be the first one to be removed. This is referred to as first-in first-out (FIFO). To illustrate it, when people stand in line at one cashier of a supermarket, the first customer in line in front of the cashier will be the first to be served (and the first to leave the supermarket).
To create a collection class that supports queues, you have various options such as arrays or lists.
Creating an Array-Based Queue
To create a collection class that performs its operations as a queue, you can use a field that is an array. Here is an example of starting such a class:
public class Queue
{
double[] items;
}
In this case, we are creating a class that can handle only double-precision values. A more professional alternative is to create a generic class, or better, to create generic interface, and then create a class that implements it. Here is an example:
interface IQueue<T> { } public class Queue<T> : IQueue<T> { }
Using a generic class means you can later create collections of any type.
To start the queue, you can create an array in the class. Here is an example:
interface IQueue<T>
{
}
public class Queue<T> : IQueue<T>
{
private T[] items;
}
If you use an array, make sure you initialize it before using it. This can be done as follows:
public class Queue<T> : IQueue<T>
{
private T[] items;
public Queue()
{
items = new T[10];
}
}
To monitor the size of the collection, you should create a property that produces an integral number to that effect. Here is an example:
interface IQueue<T>
{
int Count { get; }
}
public class Queue<T> : IQueue<T>
{
private int size;
private T[] items;
public Queue()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
}
On the other hand, you can create a read-only method that checks whether the queue is currently empty or contains at least one item. If the number of items is 0, the list is empty. If the size is greater than 0, the list is not empty. Here is an example of the property:
using System.Web.Mvc;
namespace NumericComputation.Controllers
{
interface IQueue<T>
{
int Count { get; }
bool IsEmpty { get; }
}
public class Queue<T> : IQueue<T>
{
private int size;
private T[] items;
public Queue()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
return (size == 0);
}
}
}
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Numbers()
{
Queue<double> que = new Queue<double>();
bool empty = que.IsEmpty;
ViewBag.Empty = empty;
return View();
}
}
}
--------------------------------------------
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
<p>The list is empty: @ViewBag.Empty</p>
This would produce:
Enqueing a Queue
When an item joins a queue, it is said to be added to the end of the queue. This is referred to as enqueing a list. In an array, to enqueue an item, simply assign it to the size of the array. This size would represent the last index of the list. After adding the new item, if you are numbering the items in the collection, make sure you increment the count before exiting the method. Here is an example:
using System.Web.Mvc;
namespace Exercise1.Controllers
{
interface IQueue<T>
{
int Count { get; }
bool IsEmpty { get; }
}
public class Queue<T> : IQueue<T>
{
private int size;
private T[] items;
public Queue()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
return (size == 0);
}
}
public void Enqueue(T item)
{
items[size] = item;
size++;
}
}
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Numbers()
{
Queue<double> que = new Queue<double>();
que.Enqueue(424.06);
que.Enqueue(12500.58);
que.Enqueue(28.0746);
que.Enqueue(1046.88);
return View();
}
}
}
Peeking an Item of a Queue
Getting an item from a queue is referred to as peeking the item. This is done on the item that starts the list, which is the item that was added last. Based on this, to peek an item, create a method that simply returns the item at index 0. If the list is empty, you should return the default value of the type of items that make up the list. Here is an example:
using System.Web.Mvc;
namespace QueueBasedLists.Controllers
{
public class NumbersController : Controller
{
public ActionResult Alignment()
{
return View();
}
}
interface IQueue<T>
{
int Count { get; }
bool IsEmpty { get; }
void Enqueue(T item);
T Peek();
}
public class Queue<T> : IQueue<T>
{
private int size;
private T[] items;
public Queue()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
return (size == 0);
}
}
public void Enqueue(T item)
{
items[size] = item;
size++;
}
public T Peek()
{
if (size == 0)
return default(T);
return items[0];
}
}
}
After doing this, when calling the Peek() method, if the queue is empty, the method would return the default value of its type. If the queue contains one item, the method would return it. If the list contains more than one item, the method would return the first item that was added to the list. Here is an example:
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
@{
QueueBasedLists.Controllers.Queue<double> que = new QueueBasedLists.Controllers.Queue<double>();
que.Enqueue(12500.58);
que.Enqueue(28.0746);
que.Enqueue(1046.88);
que.Enqueue(385.992);
}
<p>Number: @que.Peek()</p>
This would produce:
Dequeuing an Item
As mentioned already, when items are on a queue, the first to be enqueued will be the first to be removed. This operation is referred to as dequeueing. To dequeue (pronounce dek) an item, create a method and define it as follows:
Here is an example of creating and using a peeking method:
using System.Web.Mvc;
namespace QueueBasedLists.Controllers
{
public class NumbersController : Controller
{
// GET: Numbers
public ActionResult Index() => View();
public ActionResult Alignment() => View();
}
interface IQueue<T>
{
int Count { get; }
bool IsEmpty { get; }
void Enqueue(T item);
T Peek();
}
public class Queue<T> : IQueue<T>
{
private T[] items;
public Queue()
{
Count = 0;
items = new T[10];
}
public int Count { get; private set; }
public bool IsEmpty => (Count == 0);
public void Enqueue(T item)
{
items[Count] = item;
Count++;
}
public T Peek()
{
if (Count == 0)
return default(T);
return items[0];
}
public T Dequeue()
{
T first = items[0];
for (int i = 0; i < Count; i++)
items[i] = items[i + 1];
Count--;
return first;
}
}
}
Here are examples of calling the method:
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
@{
QueueBasedLists.Controllers.Queue<double> que = new QueueBasedLists.Controllers.Queue<double>();
que.Enqueue(12500.58);
que.Enqueue(28.0746);
que.Enqueue(1046.88);
que.Enqueue(385.992);
}
@{
// Getting a reference to the item removed from the queue...
double number = que.Dequeue();
// ... and displaying it
}
<p>Number: @number</p>
<!-- Removeing an item from the list and displaying it -->
<p>Number: @que.Dequeue()</p>
<!-- Removeing an item from the list and displaying it -->
<p>Number: @que.Dequeue()</p>
<!-- Removeing an item from the list and displaying it -->
<p>Number: @que.Dequeue()</p>
This would produce:
Clearing a Queue
To remove all items of a queue, you have various options. As one option:
using System.Web.Mvc;
namespace QueueBasedLists.Controllers
{
public class NumbersController : Controller
{
// GET: Numbers
public ActionResult Index() => View();
public ActionResult Alignment() => View();
}
interface IQueue<T>
{
int Count { get; }
bool IsEmpty { get; }
void Enqueue(T item);
T Peek();
}
public class Queue<T> : IQueue<T>
{
private T[] items;
public Queue()
{
Count = 0;
items = new T[10];
}
public int Count { get; private set; }
public bool IsEmpty => (Count == 0);
public void Enqueue(T item)
{
items[Count] = item;
Count++;
}
public T Peek()
{
if (Count == 0)
return default(T);
return items[0];
}
public T Dequeue()
{
T first = items[0];
for (int i = 0; i < Count; i++)
items[i] = items[i + 1];
Count--;
return first;
}
public void Clear()
{
// Navigate to each item of the list from beginning to end
for (int i = 0; i <= Count; i++)
{
// When you get to an item, remove it
Dequeue();
}
// Because the last item still may exist, set its value to the default of its type,
items[0] = default(T);
// If you want, reset the number of itsm to 0
// Count = 0;
}
}
}
Here is an example of calling the method:
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
@{
QueueBasedLists.Controllers.Queue<double> que = new QueueBasedLists.Controllers.Queue<double>();
que.Enqueue(12500.58);
que.Enqueue(28.0746);
que.Enqueue(1046.88);
que.Enqueue(385.992);
que.Clear();
}
<p>Number: @que.Peek()</p>
<p>Number: @que.Dequeue()</p>
This would produce:
Enumerating a Queue
By default, if you have created a queue class, it doesn't allow you to use a foreach loop. If you need this feature, create a GetEnumerator() method that returns IEnumerator. In the method, start from the beginning of the list, use a while loop to yield return the current item and increment the count each time. Here is an example:
using System.Web.Mvc;
using System.Collections.Generic;
namespace QueueBasedLists.Controllers
{
public class NumbersController : Controller
{
// GET: Numbers
public ActionResult Index() => View();
public ActionResult Alignment() => View();
}
interface IQueue<T>
{
int Count { get; }
bool IsEmpty { get; }
void Enqueue(T item);
T Peek();
}
public class Queue<T> : IQueue<T>
{
private T[] items;
public Queue()
{
Count = 0;
items = new T[10];
}
public int Count { get; private set; }
public bool IsEmpty => (Count == 0);
public void Enqueue(T item)
{
items[Count] = item;
Count++;
}
public T Peek()
{
if (Count == 0)
return default(T);
return items[0];
}
public T Dequeue()
{
T first = items[0];
for (int i = 0; i < Count; i++)
items[i] = items[i + 1];
Count--;
return first;
}
public void Clear()
{
for (int i = 0; i <= Count; i++)
{
Dequeue();
}
items[0] = default(T);
}
public IEnumerator<T> GetEnumerator()
{
int counter = 0;
while (counter < Count)
{
yield return items[counter];
counter++;
}
}
}
}
Here is an example of visiting each item of a queue:
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
@{
QueueBasedLists.Controllers.Queue<double> que = new QueueBasedLists.Controllers.Queue<double>();
que.Enqueue(12500.58);
que.Enqueue(28.0746);
que.Enqueue(1046.88);
que.Enqueue(385.992);
que.Enqueue(2748.42);
que.Enqueue(115.842);
que.Enqueue(42408.02);
que.Enqueue(2048.42);
}
<ul>
@foreach(double nbr in que)
{
<li>Number: @nbr</li>
}
</ul>
This would produce:
Checking the Presence of an Item
Once a queue is established, you may want to find out whether it contains a certain value. To do this, you can create a method named Contains that looks for an item passed as argument. If the item exists in the collection, the method returns true. Otherwise it returns false. Here is an example:
using System;
using System.Linq;
using System.Web;
using System.Web.Mvc;
using System.Collections.Generic;
namespace QueueBasedLists.Controllers
{
public class NumbersController : Controller
{
// GET: Numbers
public ActionResult Index() => View();
public ActionResult Alignment() => View();
}
interface IQueue
{
int Count { get; }
bool IsEmpty { get; }
void Enqueue(T item);
T Peek();
}
public class Queue : IQueue
{
private T[] items;
public Queue()
{
Count = 0;
items = new T[10];
}
public int Count { get; private set; }
public bool IsEmpty => (Count == 0);
public void Enqueue(T item)
{
items[Count] = item;
Count++;
}
public T Peek()
{
if (Count == 0)
return default(T);
return items[0];
}
public T Dequeue()
{
T first = items[0];
for (int i = 0; i < Count; i++)
items[i] = items[i + 1];
Count--;
return first;
}
public void Clear()
{
for (int i = 0; i <= Count; i++)
{
Dequeue();
}
items[0] = default(T);
}
public IEnumerator GetEnumerator()
{
int counter = 0;
while (counter < Count)
{
yield return items[counter];
counter++;
}
}
public bool Contains(T item)
{
foreach (T value in items)
if (value.Equals(item))
return true;
return false;
}
}
}
Here are examples of calling the method:
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
@{
QueueBasedLists.Controllers.Queue<double> que = new QueueBasedLists.Controllers.Queue<double>();
que.Enqueue(12500.58);
que.Enqueue(28.0746);
que.Enqueue(1046.88);
que.Enqueue(385.992);
que.Enqueue(2748.42);
que.Enqueue(115.842);
que.Enqueue(42408.02);
que.Enqueue(2048.42);
}
<ul>
@foreach (double nbr in que)
{
<li>Number: @nbr</li>
}
</ul>
@if (que.Contains(115.842) == true)
{
<p>The list doesn't have 115.842</p>
}
@if (que.Contains(1195.842))
{
<p>The list contains 1195.842</p>
}
else
{
<p>The list doesn't have 1195.842</p>
}
This would produce:
The .NET Framework Built-In Queue Collection Class
Introduction
To support queues, the .NET Framework provides a serialized class named Queue and that is defined in the System.Collections namespace. To let you create a queue-based list of any type, the .NET Framework provides a generic class named Queue and defined in the System.Collections.Generic.
Creating a Queue
To create a queue, you can declare a Queue or a Queue<> variable using one of its constructors. The default constructor allows you to start a list without primarily adding an item to it. If you are declaring the variable for the non-generic class in a webpage, make sure you qualify the name of the class. Here are examples:
System.Collections.Generic<!DOCTYPE html>
<html>
<head>
<title>Exercise</title>
</head>
<body>
@{
System.Collections.Queue que = new System.Collections.Queue();
// A collection from a generic class
Queue<string> names = new Queue<string>();
}
</body>
</html>
After this declaration, the compiler reserves some default memory space for the variable. If you want to specify how much space should be primarily allocated for the variable, you can use the following constructor for the non-generic class:
public Queue(int capacity);
Building a Queue
The action that consists of adding an item to the queue is called "enqueue". To perform this operation, you can call the System.Collections.Generic.Queue<>.Enqueue() or the System.Collections.Queue.Enqueue() method whose syntax is:
public virtual void Enqueue(object obj);
This method takes as argument the object you want to add to the queue and places it as the first candidate to be removed. Here are examples of calling the method:
using System; using System.Web.Mvc; using System.Collections.Generic; namespace QueueBasedLists.Controllers { public enum Majors { English, Nursing, Accounting, ComputerSciences, BusinessManagement, MathematicalSciences, HumanResourceDevelopment } public class Student { public string FullName; public DateTime DateOfBirth; public Majors Major; } public class NumbersController : Controller { // GET: Numbers public ActionResult Index() => View(); public ActionResult Alignment() { Student std = null; Queue<Student> que = new Queue<Student>(); std = new Student(); std.FullName = "Donald Palau"; std.DateOfBirth = new DateTime(1988, 5, 12); std.Major = Majors.ComputerSciences; que.Enqueue(std); std = new Student { FullName = "Arlene Kafka", DateOfBirth = new DateTime(1992, 8, 4), Major = Majors.BusinessManagement }; que.Enqueue(std); que.Enqueue(new Student { FullName = "Hortense Moons", DateOfBirth = new DateTime(1994, 10, 7), Major = Majors.MathematicalSciences }); return View(); } } }
If you already have a list created from a class that implements the ICollection interface, you can create a queue based on that list. To do this, you would use the following constructor of the Queue class:
public Queue(ICollection col);
This constructor accepts an ICollection implementer as argument. Here is an example:
using System;
public enum Majors
{
English,
Nursing,
Accounting,
ComputerSciences,
BusinessManagement,
MathematicalSciences,
HumanResourceDevelopment
}
public class Student
{
public string FullName;
public DateTime DateOfBirth;
public Majors Major;
}
public class Program
{
public void Create()
{
Student std = null;
ArrayList lstStudents = new ArrayList();
std = new Student();
std.FullName = "Hermine Justice";
std.DateOfBirth = new DateTime(1990, 3, 24);
std.Major = Majors.English;
lstStudents.Add(std);
std = new Student();
std.FullName = "Patricia Palermo";
std.DateOfBirth = new DateTime(1989, 12, 20);
std.Major = Majors.BusinessManagement;
lstStudents.Add(std);
Queue que = new Queue(lstStudents);
}
}
Primary Operations on a Queue
Peeking an Item From a Queue
Remember that the first item added to a queue stays in front of all others that would be added. To get (only) the first item of a queue, the Queue classes are equipped with a method named Peek(). The syntax of the non-generic class is:
public virtual object Peek();
This method returns an Object object that represents the first item of the queue (remember to cast it to your particular object if necessary). Here is an example of calling it:
using System;
using System.Web.Mvc;
namespace University.Controllers
{
public enum Majors
{
English,
Nursing,
Accounting,
ComputerSciences,
BusinessManagement,
MathematicalSciences,
HumanResourceDevelopment
}
public class Student
{
public string FullName;
public DateTime DateOfBirth;
public Majors Major;
}
public class NumbersController : Controller
{
// GET: Numbers
public ActionResult Index() => View();
public ActionResult Admission() => View();
}
}
Web Page: Admission.cshtml
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
@{
QueueBasedLists.Controllers.Student std = null;
Queue<QueueBasedLists.Controllers.Student> que = new Queue<QueueBasedLists.Controllers.Student>();
std = new QueueBasedLists.Controllers.Student();
std.FullName = "Donald Palau";
std.DateOfBirth = new DateTime(1988, 5, 12);
std.Major = QueueBasedLists.Controllers.Majors.ComputerSciences;
que.Enqueue(std);
std = new QueueBasedLists.Controllers.Student
{
FullName = "Arlene Kafka",
DateOfBirth = new DateTime(1992, 8, 4),
Major = QueueBasedLists.Controllers.Majors.BusinessManagement
};
que.Enqueue(std);
que.Enqueue(new QueueBasedLists.Controllers.Student
{
FullName = "Hortense Moons",
DateOfBirth = new DateTime(1994, 10, 7),
Major = QueueBasedLists.Controllers.Majors.MathematicalSciences
});
QueueBasedLists.Controllers.Student s1 = (QueueBasedLists.Controllers.Student)que.Peek();
}
<p>The current first item of the queue is:</p>
<h3>== Student Information ==</h3>
<ul>
<li>Full Name: @s1.FullName</li>
<li>Date of Birth: @s1.DateOfBirth.ToString("d")</li>
@switch (s1.Major)
{
case QueueBasedLists.Controllers.Majors.English:
<li>Major: English</li>
break;
case QueueBasedLists.Controllers.Majors.Nursing:
<li>Major: Nursing</li>
break;
case QueueBasedLists.Controllers.Majors.Accounting:
<li>Major: Accounting</li>
break;
case QueueBasedLists.Controllers.Majors.ComputerSciences:
<li>Major: Computer Science</li>
break;
case QueueBasedLists.Controllers.Majors.BusinessManagement:
<li>Major: Business Management</li>
break;
case QueueBasedLists.Controllers.Majors.MathematicalSciences:
<li>Major: Mathematical Sciences</li>
break;
case QueueBasedLists.Controllers.Majors.HumanResourceDevelopment:
<li>Major: Human Resource Development</li>
break;
}
</ul>
This would produce:
For Each Item of a Queue
To give you access to the items of a queue, the Queue classes override the GetEnumerator() method of the IEnumerable class that it implements. This allows you to use the foreach loop to continuously enumerate the members of a queue. Here is an example:
@{
ViewBag.Title = "Queue-Based List";
QueueBasedLists.Controllers.Student std = null;
Queue<QueueBasedLists.Controllers.Student> que = new Queue<QueueBasedLists.Controllers.Student>();
std = new QueueBasedLists.Controllers.Student();
std.FullName = "Donald Palau";
std.DateOfBirth = new DateTime(1988, 5, 12);
std.Major = QueueBasedLists.Controllers.Majors.ComputerSciences;
que.Enqueue(std);
std = new QueueBasedLists.Controllers.Student
{
FullName = "Arlene Kafka",
DateOfBirth = new DateTime(1992, 8, 4),
Major = QueueBasedLists.Controllers.Majors.BusinessManagement
};
que.Enqueue(std);
que.Enqueue(new QueueBasedLists.Controllers.Student
{
FullName = "Hortense Moons",
DateOfBirth = new DateTime(1994, 10, 7),
Major = QueueBasedLists.Controllers.Majors.MathematicalSciences
});
}
<h2>Students Information</h2>
<table class="table table-striped">
<tr>
<td style="font-weight: 600">Full Name</td>
<td style="font-weight: 600">Date of Birth</td>
<td style="font-weight: 600">Major</td>
</tr>
@foreach (QueueBasedLists.Controllers.Student student in que)
{
<tr>
<td>@student.FullName</td>
<td>@student.DateOfBirth.ToString("d")</td>
@switch (student.Major)
{
case QueueBasedLists.Controllers.Majors.English:
<td>English</td>
break;
case QueueBasedLists.Controllers.Majors.Nursing:
<td>Nursing</td>
break;
case QueueBasedLists.Controllers.Majors.Accounting:
<td>Accounting</td>
break;
case QueueBasedLists.Controllers.Majors.ComputerSciences:
<td>Computer Science</td>
break;
case QueueBasedLists.Controllers.Majors.BusinessManagement:
<td>Business Management</td>
break;
case QueueBasedLists.Controllers.Majors.MathematicalSciences:
<td>Mathematical Sciences</td>
break;
case QueueBasedLists.Controllers.Majors.HumanResourceDevelopment:
<td>Human Resource Development</td>
break;
}
</tr>
}
</table>
This would produce:
Removing Items From a Queue
Dequeing an Item
The process of removing an item from a queue is called "dequeue". To assist you with performing this operation, the Queue classes are equipped with a method named Dequeue. The syntax of the non-generic class is:
public virtual object Dequeue();
The primary purpose of this method is to delete the first item of the Queue list. If you are interested to know what item was deleted, this method returns it.
Clearing a Queue
To remove all items from the queue, you can call the Clear() method of the class. Its syntax is:
public virtual void Clear();
|
|
||
| Previous | Copyright © 2004-2019, FunctionX | Next |
|
|
||