Att bygga en Stack i C#
Förord
Den här artikeln handlar om att, så som rubriken antyder, bygga en stack i C# 2.0. Så, vad är en stack? En stack är en speciell typ utav lista där man endast kan lägga till och ta bort element i en ände, kallad Top(). Stacken ingår i en samling datatyper som går under namnet ADT (Abstract Data Types) och den baseras på principen LIFO (Last In First Out), så det element som tas bort är det som senast lades till. För en mer detaljerad beskrivning om vad en stack är rekomenderar jag ett besök hos: WikipediaInnehåll
»»
Relaterade artiklar
» Att bygga en stack i C#, forts.
Push, Pop & Top!
En stack utför i huvudsak tre operationer:
Push, lägger till ett element till stacken.
Pop, tar bort samt returnerar det element ligger högst upp på stacken.
Top, hämtar det element som ligger högst upp på stacken.
Stacken!
Om du inte redan gjort det så rekommenderar jag att du skapar ett nytt projekt i Visual Studio.
File->New Project->Console Application och döp projektet till Stack.
Nu är det dags att skapa en klass för stacken. Detta kan göras på två sätt, antingen via Project->Add Class eller genom att öppna Solution Explorer och sedan högerklicka på projektets namn t ex. Stack->Add->Class.
Döp klassen till Stack.cs och klicka sedan på ok.
Vi börjar med att skriva funktionen Push() för att kunna lägga till saker i listan:
namespace Stack
{
using System;
using System.Text;
// Krvs fr att kunna anvnda en ArrayList…
using System.Collections;
class Stack
{
// Skapar en instans av en ArrayList...
private ArrayList aList = new ArrayList();
// iCurrentIndex är -1 eftersom en Arraylist alltid börjar räkna från 0…
private int iCurrentIndex = -1;
public void Push(object e)
{
// Ökar värdet på iCurrentIndex med 1…
iCurrentIndex++;
// Lägger till värdet som skickas in i metoden i array listan...
aList.Add(e);
}
}
}
Koden ovan borde inte vara så svår att förstå.
Vi börjar med att skapa en instans av klassen ArrayList som är inkluderad i .Net Framework 2.0 och kan användas genom att använda "using System.Collections;".
Sedan fortsätter vi med att skapa en integer som håller reda på var i array listan vi befinner oss för tillfället.
Metoden Push() används för att lägga till ett värde i listan och tar en inparameter, object e.
Att jag använder object är för att då kan vi skicka in vilken datatyp vi vill i Stacken oavsett om det är en integer, string, float osv.
Nackdelen är att det inte går att avgöra vilka datatyper som finns i listan.
Det finns olika sätt att lösa det problemet men för att hålla artikeln enkel så tänker jag hålla mig till datypen object.
Nästa steg är att skapa en funktion Print(), för att skriva ut värdena vi har lagt till och det gör vi på följande sätt:
namespace Stack
{
// Kod bortagen för att spara utrymme…
class Stack
{
// Kod bortagen för att spara utrymme…
public void Print()
{
// Ger en exeption om listan är tom…
if (IsEmpty())
throw new IndexOutOfRangeException("Stacken är tom!");
// Iterera genom listan och skriv ut värdena till skärmen…
for (int i; i <= iCurrentIndex; i++)
Console.WriteLine(aList[i]);
}
}
}
Även denna kod snutt borde vara tämligen lätt att förstå.
Vi börjar med att kolla ifall listan är tom, är den det så kastar vi en exeption. Annars så itererar vi oss igenom listan och skriver ut varje element till och med det sista.
Tänk på att Print() egentligen inte är en naturlig del utav stacken utan är mest mest för att vi ska kunna kolla så att allt fungerar ordentligt.
Nu är det dags att skriva metoden för att tabort element Pop();
namespace Stack
{
class Stack
{
// Kod bortagen för att spara utrymme…
public object Pop()
{
// Ger en exeption om listan är tom…
if (IsEmpty())
throw new IndexOutOfRangeException("Stacken är tom!");
// Sparar det "översta" värdet i en temporär variabel…
object element = aList[iCurrentIndex];
// Tar bort det "översta" värdet ur listan…
aList[iCurrentIndex] = null;
iCurrentIndex--;
// Returnerar elementet som sparats i den temporära variabeln…
return element;
}
}
}
Den observante läsaren undrar nu säkert varför i hela fridens namn vi först sparade värdet i en variabel innan vi tog bort det, anledningen till detta är att Pop() inte bara ska ta bort värdet utan även returnera det borttagna värdet.
De följande två raderna är nog inte så svåra att förstå sig på, först sätter vi det aktuella värdet till null i array listan vilket frigör den platsen och sedan räknar vi bakåt ett steg i våran "plats variabel" iCurrentIndex.
Nu är det hög tid för den sista funktionen i Stack klassen, nämligen Top():
namespace Stack
{
class Stack
{
// Kod bortagen för att spara utrymme…
public void Top()
{
// Ger en exeption om listan är tom…
if (IsEmpty())
throw new IndexOutOfRangeException("Stacken är tom!");
// Returnera det "översta" värdet…
return aList[iCurrentIndex];
}
}
}
Allt den här kod snutten gör är att returnera det senast inlagda värdet i array listan.
Nu, sist men inte minst, är det dags att sätta våran stack på prov så öppna Program.cs.
namespace Stack
{
using System;
using System.Text;
class Program
{
public static void Main(String[] args)
{
// Skapa en instans av objektet Stack();
Stack stack = new Stack();
// Lägg till några godtyckliga värden
stack.Push("Test1");
stack.Push(2);
stack.Push(3.45f);
stack.Push(4.59);
// Skriv ut värdena
stack.Print();
// Skriv ut det "översta" värdet, kräver WriteLine + ToString()…
Console.WriteLine("\nTop:");
Console.WriteLine(stack.Top().ToString());
// Tabort det "översta" värdet från listan…
Console.WriteLine("\nPop:");
Console.WriteLine(stack.Pop().ToString());
// Skriv ut den "nya" listan
Console.WriteLine("\nHela listan efter Pop()");
stack.Print();
// Vänta på att användaren trycker på någon tangent för att avsluta...
Console.ReadLine();
}
}
}
Vi börjar med att skapa en instans av klassen Stack() som vi kallar stack sedan använder vi stack.Push() för att lägga till ett värde i listan. Som ni ser använde jag mig av ett par olika datatyper för att visa att det inte spelar någon roll då vi använder oss av object.
Sedan skriver vi ut hela listan för att försäkra oss om att allt har gått rätt till. Sedan skriver vi ut det översta värdet, men för att göra det måste vi använda oss av Console.WriteLine(stack.Top.ToString()).
Console.WriteLine(stack.Pop().ToString()) tar bort det översta värdet i listan och skriver ut det till skärmen, sedan skriver vi återigen ut listan med stack.Print() för att försäkra oss om att värdet verkligen blev raderat.
Om du nu skulle kompilera och köra programmet så borde du se något i stil med:
Detta är min första Artikel/Tutorial någonsin så det finns förmodligen mycket som kan förbättras och jag skulle uppskatta kommentarer från er som läser den, så att jag kan förbättra mig inför framtida artiklar.
Ni är även välkomna att höra av er ifall ni hittar fel eller buggar eller om ni bara vill skänka lite beröm ;)
Jag hoppas att någon kommer att ha nytta av denna artikel.
//PMH
Magnus Flisberg
Enkel och bra beskrivning av att skapa en Stack. Defenitivt läsvärd!
Simon Dahlbacka
- finns syntaxfel i koden du visar - att sätta massa olika datatyper är i praktiken inte önskvärt, sen när du nu engång använder .NET 2.0 borde du IMO gjort en Stack istället..
men förutom det helt läsvärd nog. bra att folk skriver artiklar :)
Patrik Hedman
Tack för kommentarerna, jag har försökt att rätta till syntax felen nu. Om det finns några fler så är det bara säga till. Jo jag vet att det hade varit bättre att göra en Stack men jag ville hålla artikeln så enkel som möjligt.
Patrik Hedman
Tack för kommentarerna, jag har försökt att rätta till syntax felen nu. Om det finns några fler så är det bara säga till. Jo jag vet att det hade varit bättre att göra en Stack men jag ville hålla artikeln så enkel som möjligt. Om det finns intresse så skulle jag kunnna gå igenom det i en annan artikel.
Pelle Johansson
Tycker du skall fortsätta och visa generics också som en fortsättning..