"Aus klein mach groß": Teil1 - Stack

CDW

CDW

0
Mitarbeiter
Ich habe mir gedacht, eine Reihe mit kleinen Aufgaben herauszubringen, die sich auch/gerade von Anfängern gut bewältigen lassen (und sich speziell an diese richten ;) ) und auch eine schöne Übung für die "frischerlernte" Programmiersprache darstellen sollten.

Die Aufgaben bauen aufeinander auf und werden am Ende zusammengesetzt, so dass scheinbar aus "Nichtigkeiten" ein doch recht solides Programm entsteht, worauf man dann als Programmieranfänger durchaus stolz sein kann ;).
Das bringt 1) ein bisschen Motivation und 2) verdeutlicht nochtmal das Prinzip von "divide and conquer".
http://de.wikipedia.org/wiki/Teile_und_herrsche

Teilaufgabe1: setze einen Stack um.

Stack ist eine Struktur, die Informationen speichern und ausgeben kann - und zwar nach dem Prinzip "Zuerst rein, zuletzt raus". Bildlich kann man es sich mit einem Stapel Karten vorstellen: man nimmt eine Karte, legt sie auf den Tisch, legt die nächste darauf usw. Um jetzt an eine bestimmte Karte zu kommen, muss man alle vorherigen vom Stapel wegnehmen.
http://de.wikipedia.org/wiki/Stapelspeicher
Es klingt komplizierter als es ist ;)

Vorgabe:
für Freunde der prozeduralen Programmierung (C,Pascal oder wer prozedural mit Java/C++/C# programmiert):

setze folgende Funktionen um (Parameternamen sowie Übergabe nur als Vorschlag):

push(ein_stack,elem) - legt ein übergebenes Element "elem" auf dem Stack "ein_stack" ab.
pop (ein_stack) - gibt das zuletzt auf dem Stack "ein_stack" abgelegte Element zurück. Dabei wird dieses Element vom Stack entfernt
top(ein_stack) - gibt das zuletzt auf dem Stack "ein_stack" abgelegte Element zurück, ohne dieses Element zu entfernen.
isEmpty - gibt zurück, ob der Stack leer ist ;) (z.B als Boolean Wert)

Es sollte also möglich sein, ein Element in einen bestimmten Stack einzufügen und wieder abzufragen/entfernen.
Die Objectorientierten unter euch sollten dann eine Klasse Stack umsetzen, die dieselben Methoden bietet (also Element einfügen, wegnehmen usw.)

Es sollte aufjedenfall möglich sein, mehrere Stacks gleichzeitig im Programm zu benutzen.

Versucht dabei möglichst allgemein zu bleiben, so dass der "Stackinhalt" Datentypunabhängig ist bzw. schnell an einen neuen Typ angepasst werden kann.
Wenn es noch zu schwer ist: Im Stack sollten Ziffern abgelegt werden können.

Eine einfache Möglichkeit wäre es, einen Array zu betrachten:
Code: 
 Anfang          Ende
   |               |
   v               v
  +--+--+--+--+--+---+
  |L |E |E |R |  |   |
  +--+--+--+--+--+---+
Wir können in einem Array Daten ablegen. Wenn wir einen Zähler
haben, können wir z.B mitzählen wie oft etwas eingefügt bzw. wieder entnommen 
wurde und gleichzeitig würde dieser auch auf die Position im Array zeigen, in dem 
das aktuell oberste Element zu finden ist. Also bei jedem Push den Zahler um 1 
erhöhen und bei jedem Pop um 1 erniedrigen. Beim "Top" machen wir nichts mit dem 
Zähler und beim "isEmpty" müssen wir nachschauen, ob der Zähler >0 ist (oder einer 
bestimmten Zahl ;) )

Bsp:
Programmstart:
setzte zaehler=-1;

push(6) -> zaehler=zaehler+1 (also Zaehler=0);
array[zaehler]=6;

  +--+--+--+--+--+---+
  |6 |  |  |  |  |   |
  +--+--+--+--+--+---+
   ^
   | Zähler


Push(8) -> Zaehler=Zaehler+1 (also = 1);
array[zaehler]=8
Push(9)-> Zaehler=Zaehler+1 (also = 2)
array[zaehler]=9
  +--+--+--+--+--+---+
  |6 |8 |9 |  |  |   |
  +--+--+--+--+--+---+
         ^

pop(); ->Zaehler=Zaehler-1 (also wieder 1);
  +--+--+--+--+--+---+
  |6 |8 |9 |  |  |   |
  +--+--+--+--+--+---+
      ^
top() -> rückgabe=array[zaehler] (also array[1]=rückgabe =  8)


Allerdings - hier müsstet ihr noch unbedingt eine Übrprüfung  einbauen, um micht mehr 
Elemente einfügen zu können, als Plätze im Array vorhanden sind.
z.B per isFull() abfragen können oder in der Push() Funktion eine Überprüfung 
durchführen (if (Zaehler<Array_size) zaehler=zaehler+1;

Als Test sollte euere Anwendung eine kleine Zahlenreihe einlesen und dann rückwärts ausgeben können.
Bsp:
1,2,3,4,5 Einlesen
5,4,3,2,1 Ausgeben
 
Hi


Bin mal gespannt was da am Ende heraus kommt. :D =)


push(1,1)
push(1,2)
push(1,3)
push(1,4)
push(1,5)
Print pop(1)
Print pop(1)
Print pop(1)
Print pop(1)
Print pop(1)


Type DerStack
Field Stack_Nummer
Field Dateninhalt$
End Type




Function Push(Ein_Stack,Elem$)
DerStack.DerStack=New DerStack
DerStack\Stack_Nummer=Ein_Stack
DerStack\Dateninhalt$=Elem$
Insert DerStack Before First DerStack
End Function

Function Pop$(Ein_Stack)
For DerStack.DerStack=Each DerStack
If DerStack\Stack_Nummer=Ein_Stack Then
Puffer$=DerStack\Dateninhalt$
Delete DerStack
Return Puffer$
EndIf
Next
End Function

Function Top$(Ein_Stack)
For DerStack.DerStack=Each DerStack
If DerStack\Stack_Nummer=Ein_Stack Then
Return DerStack\Dateninhalt$
EndIf
Next
End Function

Function isEmpty(Ein_Stack)
For DerStack.DerStack=Each DerStack
If DerStack\Stack_Nummer=Ein_Stack Then
Return False
EndIf
Next
Return True
End Function

Public Class AStack
Private StackData(255) As String
Private Position As Byte

Public Function push(ByVal elem As String) As Boolean
Position = Position + 1
StackData(Position) = elem
Return True
End Function

Public Function pop() As String
Dim Buffer As String
Buffer = StackData(Position)
If Position > 0 Then
Position = Position - 1
End If
Return Buffer
End Function

Public Function top() As String
Return StackData(Position)
End Function

Public Function isEmpty() As Boolean
If Position = 0 Then Return True
Return False
End Function

End Class
 
Ich hab mal einfach alles in eine Datei gepackt, wegen leichterem Copy 'n Paste ;)
Zur Speicherung von verschiedenen Datentypen habe ich C++-Templates benutzt.
Code: 
#include <iostream>

using namespace std;

template <typename T>
class Stack
{
    public:
        Stack();
        Stack(int size);
        ~Stack();

        void push(T element);
        T    top();
        T    pop();
        bool isFull() const;
        bool isEmpty() const;

    private:
        T   *stack;
        int  stackSize;
        int  elementOnTop;
};

template <typename T>
Stack<T>::Stack()
{
    Stack(10);
}

template <typename T>
Stack<T>::Stack(int size)
{
    stackSize = size;
    elementOnTop = -1;

    stack = new T[stackSize];
    if (stack == 0)
    {
        throw "Stack could not be created";
    }
}

template <typename T>
Stack<T>::~Stack()
{
    delete[] stack;
}

template <typename T>
void Stack<T>::push(T element)
{
    if (isFull())
    {
        throw "Stack is full";
    }

    elementOnTop++;
    stack[elementOnTop] = element;
}

template <typename T>
T Stack<T>::top()
{
    if (elementOnTop != -1)
    {
        return stack[elementOnTop];
    }
    else
    {
        throw "No element on stack";
    }
}

template <typename T>
T Stack<T>::pop()
{
    if (elementOnTop != -1)
    {
        elementOnTop--;
        return stack[elementOnTop+1];
    }
    else
    {
        throw "No element on stack";
    }
}

template <typename T>
bool Stack<T>::isFull() const
{
    if (elementOnTop + 1 == stackSize)
    {
        return true;
    }
    else
    {
        return false;
    }
}

template <typename T>
bool Stack<T>::isEmpty() const
{
    if (elementOnTop == -1)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
    try
    {
        Stack<int> stack(10);

        // stack füllen
        for (int i = 0; !stack.isFull(); i++)
        {
            stack.push(i);
        }

        // stack leeren
        while (!stack.isEmpty())
        {
            cout << stack.pop() << endl;
        }
    }
    catch (const char *error)
    {
        cerr << "Error: " << error << endl;
        return 1;
    }
}
 
Java Stack

Ich habe das jetzt mal versucht in Java umzusetzen.
Als Speichertyp habe ich mich für Strings entschieden, da allgemein.

Code: 
public class Stack {
    int nummer = -1;
    String inhalt[] = new String[20];
    
    void push(String eingabe) {
        nummer++;
        inhalt[nummer] = eingabe;
    }
    
    String pop() {
        if (nummer >= 0) {
            String ausgabe = inhalt[nummer];
            inhalt[nummer] = "";
            nummer--;
            return ausgabe;
        } else {
            return "Stack ist leer";
        }
    }
    
    String top() {
        return inhalt[nummer];
    }
    
    boolean isEmpty() {
        if (nummer < 0) {
            return true;
        } else {
            return false;
        }
    }
    
    
}

public class Stacktest {

    public static void main(String[] args) {
        Stack neuerStack = new Stack();
        
        neuerStack.push("1");
        neuerStack.push("2");
        neuerStack.push("3");
        neuerStack.push("4");
        neuerStack.push("5");
        
        System.out.println(neuerStack.pop());
        System.out.println(neuerStack.pop());
        System.out.println(neuerStack.pop());
        System.out.println(neuerStack.pop());
        System.out.println(neuerStack.pop());
    }

}
 
Zuletzt bearbeitet:
Ich versuche gerade noch c zu lernen, läuft alles, nur der String wird in der endlosschleife 2 mal ausgegeben :rolleyes:
Code: 
#include <stdio.h>

// Stack mit einer Maximal-Länge von 10
void push(int* stack, int value, int len) {
    int count;
    int help[len];

    for(count=0; count<len; count++)
        help[count] = stack[count-1];

    for(count=0; count<len; count++)
        stack[count] = help[count];

    stack[0] = value;
}

int pop(int* stack, int len) {
    int ret;
    int count;

    ret = stack[0];
    for(count=0; count<len; count++)
        stack[count] = stack[count+1];
    stack[len-1] = 0;

    return ret;
}

int top(int* stack) {
    return stack[0];
}

int isEmpty(int* stack, int len) {
    int count;

    for(count=0; count<len; count++) {
        if(!(stack[count] == 0))
            return 0;
    }

    return 1;
}

void ausgabe(int* stack, int len) {
    int count;

    for(count=0; count<len; count++)
        printf("%d", stack[count]);
    printf("\n");
}

int main() {
    int stack[10] = {0,0,0,0,0,0,0,0,0,0};
    int len = sizeof(stack)/sizeof(int);
    char eingabe;
    int val;
    int end;

    while(!(eingabe == 'e')) {
        printf("a=Ausgabe/u=push/o=pop/t=top/i=isEmpty:");  // 2x Ausgegeben?
        scanf("%c", &eingabe);
        printf("\n");

        end = eingabe == 'c' ? 1:0;

        if(end == 1)
            break;

        switch(eingabe) {
            case 'a':
                ausgabe(stack, len);
                break;
            case 'u':
                printf("Value: ");
                scanf("%d", &val);
                printf("\n");
                push(stack, val, len);
                break;
            case 'o':
                printf("%d", pop(stack, len));
                printf("\n");
                break;
            case 't':
                printf("%d", top(stack));
                printf("\n");
                break;
            case 'i':
                printf("%d", isEmpty(stack, len));
                printf("\n");
                break;
        }
    }
}
 
TheNew3000 hat gesagt.:
spoiler
Zum Vergrößern anklicken....
Code: 
int isEmpty(int* stack, int len) {
    int count;

    for(count=0; count<len; count++) {
        if(!(stack[count] == 0))
            return 0;
    }

    return 1;
}
Hm, was wird zurückgegeben, wenn der böse CDW Benutzer nur eine 0 auf dem Stack ablegt (oder nach mehrfachem POP eine 0 übrig bleibt)? ;)

Code: 
    char eingabe;
    ...
    while(!(eingabe == 'e')) {
Eine mögliche Meldung einiger Benutzer im (virtuellen) Bugtracker:
"Hilfe! Manchmal startet das Programm gar nicht!! :( :( " *
Hint: manchmal nehmen uninitialisierte Variablen auch unerwünschte Werte an ;)
Code: 
        printf("a=Ausgabe/u=push/o=pop/t=top/i=isEmpty:");  // 2x Ausgegeben?
        scanf("%c", &eingabe);
wenn man nur ein Zeichen eingibt und mit Enter bestätigt, landet auch ein "\n" (newline) Zeichen im Eingabepuffer. Das wird vom scanf als nächstes eingelesen und diese "Eingabe" vom Code abgearbeitet.

man scanf hat gesagt.:
c Matches a sequence of width count characters (default 1); the next
pointer must be a pointer to char, and there must be enough room
for all the characters (no terminating NUL is added). The usual
skip of leading white space is suppressed. To skip white space
first, use an explicit space in the format.
Zum Vergrößern anklicken....
d.h. einfach mal ein Leerzeichen davor setzen:
Code: 
scanf(" %c", &eingabe);
sollte Abhilfe schaffen.
 
Nicht das ich jetzt hier die Zeit hätte, das zu machen, finde ich solche kleinen Aufgaben doch interessant.

Nur wo bleiben die restlichen Teile?

Sollten da nicht noch weitere Aufgaben hinzukommen (divide and conquer)
Ich glaub nach 8 Jahren kann man bestimmt den nächsten Teil als Quest hier hinzufügen :D
 
my Stack

Tolle Aufgabe
Hier mein Code in C++

Gruss
liolin

Code: 
#ifndef DATA_H
#define DATA_H

#include "liolin.h"

namespace liolin
{
	template <class T>
	class Data
	{
	public:
		Data()
		{
		}

		Data(T val)
			:tValue(val)
		{}

		~Data(){}

		T getValue() const{ return this->tValue; }
		void setValue(T val) { this->tValue = val; }

		compare_e compare(Data data)
		{
			if (this->tValue > data.tValue)
				return compare_e::bigger;
			else if (this->tValue < data.tValue)
				return compare_e::lower;
			else
				return compare_e::equal;
		}

	private:
		T tValue;
	};
}
#endif /* DATA_H */

Code: 
#ifndef NODE_H
#define NODE_H

#include "liolin.h"
#include "Data.h"

namespace liolin
{
	template <class T>
	class ListNode
	{
	public:
		ListNode()
			:pNext(0)
		{
		}

		virtual ~ListNode()
		{
			delete this->pNext;
			this->pNext = 0;
		}

		ListNode *getNext() const { return this->pNext; }
		void setNext(ListNode *pNext) { this->pNext = pNext; }

		virtual ListNode* insert(Data<T>) = 0;
		virtual Data<T> getData() const = 0;


	private:
		ListNode *pNext;
	};
}

#endif /* NODE_H */

Code: 
#ifndef DATANODE_H
#define DATANODE_H

#include "ListNode.h"
#include "Data.h"

namespace liolin
{
	template <class T>
	class DataNode : public ListNode<T>
	{
	public:
		DataNode() {}

		virtual ~DataNode() {}

		void setData(T tValue) { this->tData.setValue(tValue); }
		void setData(Data<T> tData) { this->tData.setValue(tData.getValue()); }

		virtual ListNode* insert(Data<T> tData)
		{
			switch (this->tData.compare(tData))
			{
			default:
				this->setNext(this->getNext()->insert(tData));
				return  this;
			}
		}
		virtual Data<T> getData() const { return this->tData; }

	private:
		Data<T> tData;
	};
}

#endif /* DATANODE_H */

Code: 
#ifndef HEADNODE_H
#define HEADNODE_H

#include "ListNode.h"

namespace liolin
{
	template <class T>
	class HeadNode : public ListNode<T>
	{
	public:
		HeadNode() {}
		virtual ~HeadNode() {}

		virtual ListNode<T>* insert(Data<T> tData)
		{
			return this->getNext()->insert(tData);
		}

		virtual Data<T> getData() const { return this->getNext()->getData(); }
	};
}

#endif /* HEADNODE_H */

Code: 
#ifndef NODE_H
#define NODE_H

#include "liolin.h"
#include "Data.h"

namespace liolin
{
	template <class T>
	class ListNode
	{
	public:
		ListNode()
			:pNext(0)
		{
		}

		virtual ~ListNode()
		{
			delete this->pNext;
			this->pNext = 0;
		}

		ListNode *getNext() const { return this->pNext; }
		void setNext(ListNode *pNext) { this->pNext = pNext; }

		virtual ListNode* insert(Data<T>) = 0;
		virtual Data<T> getData() const = 0;


	private:
		ListNode *pNext;
	};
}

#endif /* NODE_H */

Code: 
#ifndef STACK_H
#define STACK_H

#include "ListNode.h"
#include "DataNode.h"
#include "HeadNode.h"

namespace liolin
{
	template <class T>
	class Stack
	{
	public:
		Stack()
		{
			this->pHead = new HeadNode<T>();
		}

		Stack(T tVal)
		{
			this->pHead = new HeadNode<T>();
			this->push(tVal);
		}

		~Stack()
		{
			delete this->pHead;
			this->pHead = 0;
		}

		void push(T tValue)
		{
			this->iSize++;
			// Save stat of the pCurrent
			// Pointer
			ListNode<T> *pTmp = this->pHead->getNext();
			//Node<T> *pTmp = this->pCurrent;
			
			// Create new Container / Node
			DataNode<T> *pNew = new DataNode<T>();
			pNew->setData(Data<T>(tValue));

			// Insert the new Pointer
			// before the pTmp
			// and set the pNew als new pCurrent
			pNew->setNext(pTmp);
			this->pHead->setNext(pNew);
			//this->pCurrent = pNew;
			//}
		}

		T pop()
		{
			ListNode<T> *pTmp = 0;
			T value;
			if (!this->isEmpty())
			{
				pTmp = this->pHead->getNext();
				value = pTmp->getData().getValue();
				this->pHead->setNext(pTmp->getNext());
				pTmp->setNext(0);
				delete pTmp;
				this->iSize--;
			}
			return value;
		}

		T top()
		{
			// getData from pHead class the getData from his
			// next node
			T value = this->pHead->getData().getValue();
			return value;
		}

		bool isEmpty()
		{
			if (this->size() == 0)
				return true;
			else
				return false;
		}

		unsigned size()
		{
			return this->iSize;
		}


	private:
		HeadNode<T> *pHead;
		unsigned int iSize;
	};
}
#endif /* STACK_H */
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben