Glengamoi (Forum) · AspHeute · .NET Heute (RSS-Suche) · AspxFiles (Wiki) · .NET Blogs

Collections einmal anders: Stacks und Queues

Geschrieben von: Christoph Wille
Kategorie: ASP.NET

This printed page brought to you by AlphaSierraPapa

Unter ASP wurden wir mit Collections ziemlich kurz gehalten - es gab nur das Scripting.Dictionary. Die Zeiten haben sich allerdings geändert, und ASP.NET bietet uns Implementationen für first in, first out Collections als auch first in, last out Collections: Queues (FIFO) und Stacks.

Voraussetzung um den Sourcecode dieses Artikels verwenden zu können ist eine Installation des Microsoft .NET Framework SDK's auf einem Webserver. Weiters setze ich voraus, daß der Leser die Programmiersprache C# zu einem gewissen Grad beherrscht - es finden sich etliche Artikel auf diesem Server, um das notwendige Wissen zu erlernen

Die Stack Klasse

Der Stack sollte allen eingefleischten Assembler Programmierern bekannt sein - für alle anderen, in Kürze, was ist ein Stack: ein Stack ist ein Stapel, auf den ich Elemente legen kann ("push"), und dann in der umgekehrten Reihenfolge wieder auslesen kann ("pop"). Um es in einem angreifbaren Bild zu bringen: ich habe ein Stapel von Hemden, auf den ich ein weiteres lege - und dieses ist dann auch wieder das Erste, das ich herunternehme.

Befüllen eines Stacks

Die erste Aufgabe ist es natürlich, den Stack mit Elementen zu befüllen. Dazu bedient man sich der Push Methode, die ein object als Parameter annimmt. Das habe ich natürlich im folgenden Beispiel entsprechend ausgenutzt (stack.aspx).

<% @Page Language="C#" %>
<% @Import Namespace="System.Collections" %>
<%
Stack myStack = new Stack();
myStack.Push("Christoph");
myStack.Push(Request.ServerVariables.Get("SCRIPT_NAME"));
myStack.Push(new DateTime(2000,7,29));
myStack.Push(Math.PI);
myStack.Push(2000.0 / 10.5);

Response.Write(myStack.Count.ToString());
%>

Im gezeigten Beispiel lege ich zuerst ein Stack Objekt an, und fülle dann Strings, DateTime Werte und Zahlen ein. Als Beweis gebe ich dann die Anzahl der Elemente aus, die man vom Stack wieder herunternehmen könnte.

Auslesen eines Stacks

Interessanter wird da schon das Auslesen - weil es führen viele Wege nach Rom. Der erste ist das Auslesen mittels eines foreach Statements (stack_show.aspx).

<% @Page Language="C#" %>
<% @Import Namespace="System.Collections" %>
<%
Stack myStack = new Stack(5);
myStack.Push("Christoph");
myStack.Push(Request.ServerVariables.Get("SCRIPT_NAME"));
myStack.Push(new DateTime(2000,7,29));
myStack.Push(Math.PI);
myStack.Push(2000.0 / 10.5);

foreach (object objElement in myStack)
{
  Response.Write(objElement.ToString() + "<br>\r\n");
}
%>

Da die Stack Klasse die GetEnumerator Methode unterstützt (liefert das IEnumerator Interface), kann ich die foreach Schleife einsetzen. Bei Verwendung dieses Loops werden keine Elemente vom Stack heruntergenommen.

Anders sieht es aus, wenn man sich der Pop Methode des Stacks bedient - das Element wird heruntergenommen und vom Stack gelöscht. Deshalb kann man sich mit Peek eine kleine "Vorschau" auf das nächste Element holen, ohne es aber vom Stack herunterzunehmen (stack_read.aspx).

<% @Page Language="C#" %>
<% @Import Namespace="System.Collections" %>
<%
Stack myStack = new Stack(5);
myStack.Push("Christoph");
myStack.Push(Request.ServerVariables.Get("SCRIPT_NAME"));
myStack.Push(new DateTime(2000,7,29));
myStack.Push(Math.PI);
myStack.Push(2000.0 / 10.5);

// peek at the first element
object objHead = myStack.Peek();
Response.Write("Peeked at " + objHead.ToString() + "<br>\r\n");

int nCount = myStack.Count;
for (int i = 0; i < nCount; i++)
{
   object objCurrent = myStack.Pop();
   Response.Write("Popped " + objCurrent.ToString() + "<br>\r\n");
}
%>

Ich habe behauptet, daß Peek das Element nicht löscht - der folgende Screenshot beweist es, weil das Element zweimal in der Liste aufscheint.

Die Queue Klasse

Im Gegensatz zum Stack wird in einer Queue das zuerst eingefügte Element auch als erstes wieder ausgelesen. Die Anwendung wird daher eine normale "Arbeitsqueue" sein, bei der ich auf der einen Seite Elemente einfüge, und am anderen Ende wieder herausnehme.

Befüllen einer Queue

Auch für die Queue Klasse werden wir uns zuerst ansehen, wie man Elemente einfügt (queue.aspx).

<% @Page Language="C#" %>
<% @Import Namespace="System.Collections" %>
<%
Queue myQueue = new Queue(5);
myQueue.Enqueue("Christoph");
myQueue.Enqueue(Request.ServerVariables.Get("SCRIPT_NAME"));
myQueue.Enqueue(new DateTime(2000,7,29));
myQueue.Enqueue(Math.PI);
myQueue.Enqueue(2000.0 / 10.5);

Response.Write(myQueue.Count.ToString());
%>

Der einzige Unterschied zum Stack ist der, daß die Methode jetzt Enqueue heißt. Sonst hat sich nichts geändert, was ja für das Erlernen nur von Vorteil ist.

Zum Konstruktor möchte ich noch ein Wort loswerden: dort steht in den Klammern der Wert fünf. Dies gibt die anfängliche Größe an. Weitere Overloads des Konstruktors lassen auch zu, den Wachstumsfaktor für die Queue zu definieren. Der Vorteil: die Speicherallokierung für die Elemente geht deutlich effizienter von statten, was sich speziell bei einer größeren Anzahl von Elementen deutlich auswirkt.

Auslesen einer Queue

Das Auslesen einer Queue funktioniert ebenfalls mit GetEnumerator und foreach. Deshalb möchte ich einen anderen Weg demonstrieren, der auch das gewünschte Ergebnis liefert (queue_show.aspx).

<% @Page Language="C#" %>
<% @Import Namespace="System.Collections" %>
<%
Queue myQueue = new Queue(5);
myQueue.Enqueue("Christoph");
myQueue.Enqueue(Request.ServerVariables.Get("SCRIPT_NAME"));
myQueue.Enqueue(new DateTime(2000,7,29));
myQueue.Enqueue(Math.PI);
myQueue.Enqueue(2000.0 / 10.5);

object[] arrElements = myQueue.ToArray();
foreach (object objElement in arrElements)
{
  Response.Write(objElement.ToString() + "<br>\r\n");
}
%>

In diesem Beispiel habe ich die ToArray Methode verwendet, um die Daten der Queue in ein Array zu kopieren. Dieses enumiere ich dann mit foreach. Apropos: dieser Ansatz funktioniert 1:1 auch für einen Stack.

Um nun ein Element zu lesen und gleichzeitig aus der Queue zu entfernen, sollte man die Dequeue Methode verwenden. Will man nur das erste Element lesen ohne es zu entfernen, dann bietet sich wieder die Peek Methode an (queue_read.aspx).

<% @Page Language="C#" %>
<% @Import Namespace="System.Collections" %>
<%
Queue myQueue = new Queue(5);
myQueue.Enqueue("Christoph");
myQueue.Enqueue(Request.ServerVariables.Get("SCRIPT_NAME"));
myQueue.Enqueue(new DateTime(2000,7,29));
myQueue.Enqueue(Math.PI);
myQueue.Enqueue(2000.0 / 10.5);

// peek at the first element
object objHead = myQueue.Peek();
Response.Write("Peeked at " + objHead.ToString() + "<br>\r\n");

int nCount = myQueue.Count;
for (int i = 0; i < nCount; i++)
{
   object objCurrent = myQueue.Dequeue();
   Response.Write("Dequeud " + objCurrent.ToString() + "<br>\r\n");
}
%>

Schlußbemerkung

Heute haben wir zwei weitere Collections aus dem System.Collections Namespace kennengelernt, nämlich Queue und Stack. Die Verwendung einer Queue bietet sich dann an, wenn man Elemente in der Reihenfolge des Befüllens abarbeiten möchte. Der Stack hingegen kommt dann zum Einsatz, wenn Elemente nach dem last in, first out Prinzip bearbeitet werden sollen.