.NET 1.1

The Stack Collection

The forty-first part of the C# Fundamentals tutorial examines the Stack class. This collection includes the functionality required in a 'Last In, First Out' (LIFO) stacking structure. Stacks allow items to be held for later extraction and processing.

What is a Stack?

Stacks are similar in structure to queue collections. However, where a queue ensures that the items are extracted from the collection in the order they were added, stacks allow the most recently added items to be retrieved first. This is known as Last In, First Out or LIFO.

Operating systems and high-level development languages use stacks frequently. One key use of the stack structure is when storing the return points for program calls. Each time a subroutine is called, the address of the calling function is added, or pushed, onto the stack. When the subroutine processing is complete, the last address can be retrieved, or popped, from the stack and the normal program flow can continue from the previous position. The earlier C# Exception Handling article includes an example of this use of a stack when reading the StackTrace property.

The Stack Collection

The .NET framework includes the Stack collection class. This provides all of the functionality required to operate LIFO stacks with no additional programming. The Stack class provides a very simple type of collection that can contain any type of object, including duplicate items and null values.

Implemented Collection Interfaces

The Stack collection implements the properties and methods of the ICollection interface. This behaviour is described in the earlier Collection Interfaces article. The rest of this article describes only the additional functionality provided by Stack.

Declaring a Stack

Constructors

The Stack class provides three constructors. The first constructor is the most basic, as it requires no parameters. The new, empty stack is generated with the capacity to store up to ten items. Should an eleventh item be added, the capacity of the stack is doubled automatically. It doubles again each time the capacity of the stack is exceeded.

The Stack class is found in the System.Collections namespace so to execute the examples, add using System.Collections; to the source code.

If the maximum number of items that will be stored in a Stack is known before the collection is created, it is more efficient to declare the required capacity during construction. If the size is underestimated and the stated capacity is exceeded, the size of the stack will still be doubled to accommodate extra items. To declare the initial size of a Stack, the capacity is passed as an integer parameter.

The third constructor permits the creation of a pre-populated stack. If you already have a collection of items in a class that implements the ICollection interface, this can be used as the source data for the new stack. Each item in the collection is added to the stack in the order that the collection would normally be enumerated.

ArrayList myList = new ArrayList();
myList.Add("String 1");
myList.Add("String 2");

Stack myLifo = new Stack(myList);               // Copies myList into the stack

Using Stack Functions

Push Method

The purpose of a stack is to allow new items to be added to the top of the stack and for these items to be extracted in the reverse order to their addition. To add a new item to the top of the stack, the Push method is called. This method accepts one parameter, being the object to be added to the stack. The object may be of any data type. For simplicity in the following examples, strings will be used.

Stack breadcrumbs = new Stack();

breadcrumbs.Push("Home Page");
breadcrumbs.Push("Articles");
breadcrumbs.Push("C#");

Console.WriteLine("Count: {0}", breadcrumbs.Count);     // Outputs "Count: 3"

Pop Method

To retrieve items from a stack, the Pop method is used. Pop returns the item that appears at the top of the stack, boxed within an object. To extract the item into a variable, the object can be cast to the correct type. In the following example, the ToString method is used to perform the conversion as three items are added to and then retrieved from a stack. Not that the order of extraction is the reverse of the order in which the items were pushed onto the stack.

Stack breadcrumbs = new Stack();

breadcrumbs.Push("Home Page");
breadcrumbs.Push("Articles");
breadcrumbs.Push("C#");

while (breadcrumbs.Count != 0)
{
    string next = breadcrumbs.Pop().ToString();
    Console.WriteLine(next);
}

/* OUTPUT

C#
Articles
Home Page

*/

Peek Method

Often it is useful to know the contents of the item at the top of a stack without affecting the contents of the collection. The Peek method is used in the same manner as Pop but when the top item is retrieved, it is also left in position in the stack.

Stack breadcrumbs = new Stack();

breadcrumbs.Push("Home Page");
breadcrumbs.Push("Articles");
breadcrumbs.Push("C#");

string next = breadcrumbs.Peek().ToString();
Console.WriteLine(next);                                // Outputs "C#"
Console.WriteLine("Count: {0}", breadcrumbs.Count);     // Outputs "Count: 3"

Other Stack Processing Methods

In addition to the LIFO processing methods, the Stack class provides some other functionality for modifying and reading the collection. These enhance the data structure with behaviours similar to those found in some other collection and list types.

Clear

The Clear method is used to empty the contents of a stack. The method requires no parameters.

Stack breadcrumbs = new Stack();

breadcrumbs.Push("Home Page");
breadcrumbs.Push("Articles");
breadcrumbs.Push("C#");

Console.WriteLine("Count: {0}", breadcrumbs.Count);     // Outputs "Count: 3"
breadcrumbs.Clear();
Console.WriteLine("Count: {0}", breadcrumbs.Count);     // Outputs "Count: 0"

Contains

Often you will need to determine if an item exists within a stack but you will not want to pop every item from the stack in order to find it. The Contains method permits this by returning a Boolean value indicating if the object is already held in the collection. The method is similar to the Contains method provided by the IList interface.

Stack breadcrumbs = new Stack();

breadcrumbs.Push("Home Page");
breadcrumbs.Push("Articles");
breadcrumbs.Push("C#");

Console.WriteLine(breadcrumbs.Contains("Articles"));    // Outputs "True"
Console.WriteLine(breadcrumbs.Contains("SQL Server"));  // Outputs "False"

ToArray

A further method exists that permits a stack's contents to be read without disturbing the order of the items. In a similar manner to with an ArrayList, the objects in the stack can be extracted into an array. The resultant array has each item boxed in an object that can be cast back to the original type. The stack itself is unaffected.

Stack breadcrumbs = new Stack();

breadcrumbs.Push("Home Page");
breadcrumbs.Push("Articles");
breadcrumbs.Push("C#");

// Copy items
object[] array = breadcrumbs.ToArray();

// List array items
foreach (object o in array)
    Console.WriteLine(o.ToString());

/* OUTPUT

C#
Articles
Home Page

*/

Creating a Thread-Safe Stack Wrapper

In the earlier article discussing collection interfaces, the concept of a thread-safe synchronised collection was described. In order to create a thread-safe Stack, a synchronised wrapper collection is generated using the static Synchronized method.

Stack myCollection = new Stack();

Stack myThreadSafe = Stack.Synchronized(myCollection);

Console.WriteLine(myThreadSafe.IsSynchronized);	            // Outputs "True"