Stack Collections
Stack Collections
Stacks Fundamentals
Introduction
A stack is a technique of creating a list so that the last item added to the list is also the first one that would be removed. It can be illustrated as placing a few cups in a box that can receive only one on top of another (no adjacent cup). When it comes time to get one of those cups, you must first access the top one; that is, the last one that was added. In other words, at one time, the items in the list appear in the reverse order they were added. This technique of building a list is referred to as first-in last-out (FILO).
To create a collection class that supports stack functionality, you have various options between arrays and classic lists.
Introduction to Creating a Stack Using an Array
To perform stack operations using a collection, you can create a class whose main member is an array. Here is an example of starting such a class: public class Stack<T>
{
private double[] numbers;
}
To create a more professional class, you should make it a generic one. Better yet, you can first create a generic interface, then create a class that implements it. Here is an example: interface IStack<T>
{
}
public class Stack<T> : IStack<T>
{
private T[] items;
}
g from an interface but you can omit it if you want.) Here is an example: |
 |
Of course, whenever you use an array, you should (must) make sure you initialize it prior to its being used. You can initialize the array in the body of the class or you can use a constructor. Here is an example:
public class Stack<T> : IStack<T>
{
private T[] items;
public Stack()
{
items = new T[10];
}
}
As always, as a courtesy, you should make sure you keep a count of the items in a collection class. This is usually done by using a read-only property that returns the size of the array. This can be done as follows:
interface IStack<T>
{
int Count { get; }
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
}
Using this mechanism, you can create a property that holds the information about the stack being empty or not. When implementing this method, you can check the value of the size. If it is 0, the list is empty. If the size is greater than 0, the list is not empty. Here is an example of defining this method:
interface IStack<T>
{
int Count { get; }
bool IsEmpty { get; }
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
else
return false;
}
}
}
Pushing an Item to a Stack
To add an item to a stack, if the list is empty, which means its size is 0, you simply position it as the first item. If the stack already contains at leas one item, you must push the existing item down (or in the moving direction) to create an empty space for the new item, then position the new item in the new empty position. For this reason, this operation is referred to as pushing.
If you are using an array, to push the new item, from the end of the list, first move each item one position down to make the 0 index available. Then, assign the new item to that index. If your class is keeping a count of the items in its list, after adding the new item, you should increase the number of items. Here is an example of performing this operation:
using System.Web.Mvc;
namespace Exercise1.Controllers
{
interface IStack<T>
{
int Count { get; }
bool IsEmpty { get; }
void Push(T item);
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
else
return false;
}
}
public void Push(T item)
{
items[size] = item;
size++;
}
}
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Numbers()
{
Stack<double> stk = new Stack<double>();
stk.Push(424.06);
stk.Push(12500.58);
stk.Push(28.0746);
stk.Push(1046.88);
return View();
}
}
}
Peeking an Item of a Stack
The process of getting an item of a stack is referred to as peeking. Remember that, in a stack, you have access to only one item, the last one to be added. Therefore, to peek an item, create a method that simply returns the item in the last index. This would be the item at the size - 1. Here is an example of creating and using a peeking method:
using System.Web.Mvc;
namespace Exercise1.Controllers
{
interface IStack<T>
{
int Count { get; }
bool IsEmpty { get; }
void Push(T item);
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
else
return false;
}
}
public void Push(T item)
{
items[size] = item;
size++;
}
public T Peek()
{
if (size == 0)
return default(T);
return items[size - 1];
}
}
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Numbers()
{
return View();
}
}
}
----------------------------------------------------
@{
ViewBag.Title = "Stack-Based List";
}
<h2>Stack-Based List</h2>
@{
Exercise1.Controllers.Stack<double> stk = new Exercise1.Controllers.Stack<double>();
stk.Push(424.06);
}
<p>Number: @stk.Peek()</p>
@{ stk.Push(12500.58); }
<p>Number: @stk.Peek()</p>
@{ stk.Push(28.0746); }
<p>Number: @stk.Peek()</p>
@{ stk.Push(1046.88); }
<p>Number: @stk.Peek()</p>
This would produce:
Popping an Item From a Stack
The process of removing an item from a stack is referred to as poping it. Once again, remember that you only have access to the top item, which is the last item that was added. If you are using an array, to pop an item, in your method:
Here is an example of creating and using a popping method:
using System.Web.Mvc;
namespace Exercise1.Controllers
{
interface IStack<T>
{
int Count { get; }
bool IsEmpty { get; }
void Push(T item);
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
else
return false;
}
}
public void Push(T item)
{
items[size] = item;
size++;
}
public T Peek()
{
if (size == 0)
return default(T);
return items[size - 1];
}
public T Pop()
{
T Last = items[size - 1];
size--;
return Last;
}
}
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Numbers()
{
return View();
}
}
}
----------------------------------------------
@{
ViewBag.Title = "Queue-Based List";
}
<h2>Queue-Based List</h2>
@{
Exercise1.Controllers.Stack<double> stk = new Exercise1.Controllers.Stack<double>();
stk.Push(424.06);
stk.Push(12500.58);
stk.Push(28.0746);
stk.Push(1046.88);
}
<p>Number of Items: @stk.Count</p>
<p>Number: @stk.Pop()</p>
<p>Number of Items: @stk.Count</p>
<p>Number: @stk.Pop()</p>
<p>Number of Items: @stk.Count</p>
<p>Number: @stk.Pop()</p>
<p>Number of Items: @stk.Count</p>
<p>Number: @stk.Pop()</p>
<p>Number of Items: @stk.Count</p>
This would produce:
Clearing a Stack
Clearing a stack consists of deleting all of its items. To support this operation, create a method that resets the number of items of the list. Here is an example:
interface IStack<T>
{
int Count { get; }
bool IsEmpty { get; }
void Push(T item);
T Peek();
T Pop();
void Clear();
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
else
return false;
}
}
public void Push(T item)
{
items[size] = item;
size++;
}
public T Peek()
{
if (size == 0)
return default(T);
return items[size - 1];
}
public T Pop()
{
T Last = items[size - 1];
size--;
return Last;
}
public void Clear()
{
size = 0;
}
}
Enumerating Each Item of the Stack
If you want, you can provide support foreach item of the collection. To do this, you would create a method named GetEnumerator that returns an IEnumerator object. When implementing this method, start from the end of the list, use a while loop to yield return the current item and decrement the count each time. Here is an example:
using System.Collections.Generic;
namespace Exercise1.Controllers
{
interface IStack<T>
{
int Count { get; }
bool IsEmpty { get; }
void Push(T item);
T Peek();
T Pop();
void Clear();
IEnumerator<T> GetEnumerator();
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
else
return false;
}
}
public void Push(T item)
{
items[size] = item;
size++;
}
public T Peek()
{
if (size == 0)
return default(T);
return items[size - 1];
}
public T Pop()
{
T Last = items[size - 1];
size--;
return Last;
}
public void Clear()
{
size = 0;
}
public IEnumerator<T> GetEnumerator()
{
int counter = size - 1;
while (counter >= 0)
{
yield return items[counter];
counter--;
}
}
}
}
------------------------------------------------------
using System.Web.Mvc;
namespace Exercise1.Controllers
{
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Numbers()
{
return View();
}
}
}
------------------------------------------------
@{
ViewBag.Title = "Stack-Based List";
}
<h2>Stack-Based List</h2>
@{
Exercise1.Models.Stack<double> stk = new Exercise1.Models.Stack<double>();
stk.Push(424.06);
stk.Push(12500.58);
stk.Push(28.0746);
stk.Push(1046.88);
}
<p>Number of Items: @stk.Count</p>
<ul>
@foreach (double d in stk)
{
<li>Number: @d</li>
}
</ul>
This would produce:
Looking for an Item in a Stack
The operations we have implemented so far are typical of a stack. One of the routine operations you can perform consists of checking the availability of an item. To perform this operation, create a method (you can call it Contains) that is passed the item to look for. When implementing the method, you can use a loop to visit each item. If you find an item that matches the argument, return true. If you get to the end of the list and there was no item that matched the argument, let the method return false. Here is an example of how this can be done:
using System;
using System.Collections.Generic;
interface IStack<T>
{
int Count { get; }
bool IsEmpty { get; }
void Push(T item);
T Peek();
bool Contains(T item);
T Pop();
void Clear();
IEnumerator<T> GetEnumerator();
}
public class Stack<T> : IStack<T>
{
private int size;
private T[] items;
public Stack()
{
size = 0;
items = new T[10];
}
public int Count
{
get
{
return size;
}
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
else
return false;
}
}
public void Push(T item)
{
items[size] = item;
size++;
}
public T Peek()
{
if (size == 0)
return default(T);
return items[size - 1];
}
public bool Contains(T item){
foreach (T value in items)
if (value.Equals(item))
return true;
return false;
}
public T Pop()
{
T Last = items[size - 1];
size--;
return Last;
}
public void Clear()
{
size = 0;
}
public IEnumerator<T> GetEnumerator()
{
int counter = size - 1;
while (counter >= 0)
{
yield return items[counter];
counter--;
}
}
}
The Built-In Stack Collection Class
Introduction
To support stack types of collections, the System.Collectionsnamespace provides a class named Stack. in the same way, the System.Collections.Generic namespace provides an equivalent generic class. Both the Stack and the generic Stack<T> classes are serializable classes that implement the ICollection (giving the ability to know the number of items in the list) and the IEnumerable for the Stack class or the System.Collections.Generic.IEnumerable<> interfaces (they give the ability to use foreach).
Creating a Stack
The Stack and the Stack<T> classes are each equipped with three constructors. The default constructor allows you to create a stack without primarily taking any action. If you want to declare a Stack variable in a webpage, you must qualify the name of the class. Here is an example:
<!DOCTYPE html>
<html>
<head>
<title>Exercise</title>
</head>
<body>
<h2>Exercise</h2>
@{
System.Collections.Stack<string> players = new System.Collections.Stack<string>();
}
If you create a stack with this constructor, the list is primarily empty with a default capacity. If you want, before initializing the list, you can specify how much space the compiler should primarily allocate for the number of eventual items of the list. To provide this information, the Stack class is equipped with the following constructor:
public Stack(int initialCapacity);
Adding Items to a Stack
To let you add an item to a stack, the System.Collections.Stack class is equipped with a method named Push. Its syntax is:
public virtual void Push(object obj);
The new item is passed as argument to the method. Here is an example:
using System.Web.Mvc;
using System.Collections;
namespace Exercise1.Controllers
{
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Numbers()
{
Stack sports = new Stack();
sports.Push("Basketball");
return View();
}
}
}
Whenever you add a new item to the stack, the compiler increases the number of items in the list. This number is stored in the Count property of the Stack class.
If you have a series of items that were created using a class that implements the ICollection interface, you can use the following constructor of the Stack class:
public Stack(ICollection col);
When using this constructor, pass a variable of collection class as argument. Here is an example:
using System.Collections;
public class Sport
{
public string Name { get; set; }
public uint PlayersPerTeam { get; set; }
}
public class Program
{
public void Create()
{
Sport spt = new Sport();
ArrayList lstSports = new ArrayList();
spt.Name = "Volleyball";
spt.PlayersPerTeam = 6;
lstSports.Add(spt);
spt = new Sport();
spt.Name = "Tennis Single";
spt.PlayersPerTeam = 1;
lstSports.Add(spt);
spt = new Sport();
spt.Name = "Handball";
spt.PlayersPerTeam = 6;
lstSports.Add(spt);
Stack sports = new Stack(lstSports);
return;
}
}
If you are using the generic class, make sure you pass the type or class as parameter.
Accessing an Item in the Stack
When you have just added one or more items to a stack, you can access the lone item or the last item that was added by simply using the item in the collection. Here is an example:
using System.Web.Mvc;
namespace Exercise1.Controllers
{
public class CollectorController : Controller
{
public ActionResult Index()
{
return View();
}
public ActionResult Catalogue()
{
return View();
}
public ActionResult Numbers()
{
return View();
}
}
public class Course
{
public string CourseCode { get; set; }
public string CourseName { get; set; }
public int Credits { get; set; }
}
}
--------------------------------------------------
@{
ViewBag.Title = "College Catalogue";
}
<h2>College Catalogue</h2>
@{
Exercise1.Controllers.Course course = new Exercise1.Controllers.Course();
Stack<Exercise1.Controllers.Course> courses = new Stack<Exercise1.Controllers.Course>();
course.CourseCode = "MATH-112";
course.CourseName = "Basic Algebra";
course.Credits = 3;
courses.Push(course);
course.CourseCode = "MATH-124";
course.CourseName = "College Algebra";
course.Credits = 3;
courses.Push(course);
course.CourseCode = "MATH-201";
course.CourseName = "Introductory Calculus";
course.Credits = 4;
courses.Push(course);
course.CourseCode = "MATH-310";
course.CourseName = "Linear Algebra";
course.Credits = 4;
courses.Push(course);
}
<p>Course Code: @course.CourseCode<br />
Course Name: @course.CourseName<br />
Credits: @course.Credits</p>
This would produce:
As an alternative, both the System.Collections.Stack and the System.Collections.Generic.Stack<> classes are equipped with a method named Peek . The syntax of the System.Collections.Stack.Peek() method is:
public virtual object Peek();
The syntax of the System.Collections.Generic.Stack<T>.Peek() method is:
public T Peek();
This method produces the last item that was added to the stack. Here is an example of calling it:
@{
ViewBag.Title = "College Catalog";
}
<h2>College Catalog</h2>
@{
Exercise1.Controllers.Course course = new Exercise1.Controllers.Course();
Stack<Exercise1.Controllers.Course> courses = new Stack<Exercise1.Controllers.Course>();
course.CourseCode = "MATH-112";
course.CourseName = "Basic Algebra";
course.Credits = 3;
courses.Push(course);
course.CourseCode = "MATH-124";
course.CourseName = "College Algebra";
course.Credits = 3;
courses.Push(course);
course.CourseCode = "MATH-201";
course.CourseName = "Introductory Calculus";
course.Credits = 4;
courses.Push(course);
course.CourseCode = "MATH-310";
course.CourseName = "Linear Algebra";
course.Credits = 4;
courses.Push(course);
Exercise1.Controllers.Course learning = courses.Peek();
}
<p>Course Code: @learning.CourseCode<br />
Course Name: @learning.CourseName<br />
Credits: @learning.Credits</p>
Popping an Item from a Stack
To let you remove a value or object from a stack, both the System.Collections.Stack and the System.Collections.Generic.Stack<> classes are equipped with a method named Pop. The syntax for the regular version is:
public virtual object Pop();
When called, this method removed the last item in the stack. If you are interested to know what item was removed, this method returns it as an Object value. This method removes the top item from the stack and produices it.
Clearing a Stack
To let you remove all items from the list, both classes are equipped with the Clear() method. Its syntax is:
public virtual void Clear();
Accessing Each Item of a Stack
Both the System.Collections.Stack and the System.Collections.Generic.Stack<> classes override the GetEnumerator() method by implementing the IEnumerable interface. This allows you to access each member of the stack using the foreach loop.
To find out if the list contains a particular item, you can call the Contains() method of the Stack class. Its syntax is:
public virtual bool Contains(object obj);
Removing Items From a Stack
As mentioned earlier, a stack is organized so that the last item that was added to the list is the first one to be removed. To support this operation, the Stack class is equipped with the Pop() method.
|
|
||
| Previous | Copyright © 2004-2019, FunctionX | Next |
|
|
||