Stapelimplementierung in C

Stapelimplementierung in C

Wir können die Datenstruktur über die C -Sprache implementieren. Es stehen verschiedene Arten von Datenstruktur zur Verfügung, um die Daten auf effiziente Weise zu speichern und zuzugreifen. Stack ist einer von ihnen.

Ein Stack ist eine modifizierte Version von Array. Wir können ein Element am einen Ende des Stapels hinzufügen oder entfernen. Dieses Ende ist am Spitze des Stapels.

Stack ist eine spezielle Möglichkeit, um auf die Daten zu handhaben, zu speichern, einzusetzen, zu löschen, auf die Daten zuzugreifen. Es ist in der Natur abstrakt.

Array und Stapel

  1. Es gibt ein wenig Unterschied zwischen dem Array und dem Stapel in Bezug auf ihre Zugänglichkeit. Wir können auf ein beliebiges Element aus dem Array in jedem Zustand zugreifen. Dieses Ende heißt Top. In Bezug auf die Zugänglichkeit ist das Array schneller als der Stapel.
  2. Stack hat zwei Hauptfunktion namens Push and Pop.
  3. Die Push -Funktion wird verwendet, um in einen Stapel einzulegen, und mit der POP -Funktion wird ein Element aus dem Stapel entfernt.

Darstellung

Wir können nur auf das letzte in Stack eingefügte Element zugreifen. Dies ist die Spitze des Stacks. Wir können entweder einfügen oder von oben entfernt werden.

Dies ist als Last in Fast Out (LIFO) und Fast in Last Out (Filo) bekannt.

Implementierung

Stack kann wie folgt implementiert werden:

-> Array -> Dynamisches Array -> Linkliste

Betrieb

-> Push -> Pop

Algorithmus Druck: Push (Stack, Top, Maxstk, Artikel)

1. [Stack ist voll]

Wenn Top == Maxstk

Zeige Nachricht: Überlauf und Rückkehr

2. Setzen Sie Top = Top + 1
3. Setzen Sie Stack [Top] = Artikel
4. Zurückkehren

Algorithmus Pop: Pop (Stack, Top, Artikel)

1. [Element vom Stapel entfernt]

Wenn top == -1

Zeige Nachricht: Unterströmung und Rückkehr

2. Setzen Sie Item = Stack [Top]
3. Oben: Top -1
4. Zurückkehren

Stapel mit Array

Struct ArrayStack

int top;
nicht signierte Kapazität;
int *Array;

Hier definieren wir einen benutzerdefinierten Datentyp namens ArrayStack. Es verfügt über drei Datenmitglieder mit dem Namen Top, Kapazität und einen Zeiger namens *Array.

Polnische Notation

Polnische Notation schreibt Operatoren eines Ausdrucks entweder vor oder nach ihrem Operanden.

Schreibweisen:

Infix 2. Präfix 3. Postfix

Infix

Die Betreiber werden zwischen den beiden Operanden gehalten.

Beispiel: a + b

Präfix

Die Betreiber werden vor ihren Operanden aufbewahrt.

Beispiel: + a b

Postfix

Die Betreiber werden nach ihren Operanden aufbewahrt.

Beispiel: a b +

Konvertieren

1.

Infix:
(A + b) * c
Präfix:
* + A b c
Postfix:
A b + c *

2.

Infix:
A + (b * c)
Präfix:
+ A * b c
Postfix:
A b c * +

3.

Infix :( a + b) / (c - d)
Präfix:/ + a b - c d
Postfix: a b + c d - /

All diese Umwandlung kann mit Stack durchgeführt werden. Jetzt möchten wir zeigen, wie ein Stapel erstellt werden kann und wie das Element oder die Daten eingefügt werden. Die Elemente können durch Programmierung aus dem Stapel entfernt werden.

Programmierbeispiel

#enthalten
#enthalten
int item;
struct arrayStack // einen Datentyp definieren;

int top;
int Kapazität;
int *Array;
;
Struct ArrayStack *CreateStack (int Cap) // einen Stapel erstellen;

Struct ArrayStack *Stack;
stack = malloc (sizeof (struct arrayStack));
Stack-> top = - 1;
Stack-> Kapazität = CAP;
stack-> array = malloc (sizeof (int) * stack-> Kapazität);
return (stapel);

int full (struct arrayStack *stapel) // Die Überprüfung des Stapels ist voll oder nicht.

if (stack-> top == Stack-> Kapazität-1)
Rückgabe (1);
anders
return (0);

int leer (Struct ArrayStack *Stack) // Das Überprüfen des Stapels ist leer oder nicht.

if (stack-> top == -1)
Rückgabe (1);
anders
return (0);

void push (struct arrayStack *stapel, int item) // Elemente in den Stapel einfügen;

Wenn ( !voller Stapel ) )

Stack-> Top ++;
Stack-> Array [Stack-> Top] = Item;


int pop (struct ArrayStack *Stack) // Elemente aus dem Stapel entfernen;

Wenn ( !leer (Stapel))

item = stack-> array [stack-> top];
Stack-> Top--;
Artikel zurückgeben ) ;

return (-1);

int main ()

int Wahl;
Struct ArrayStack *Stack;
Stack = CreateStack (4);
während (1)

printf ("\ n 1 . drücken " ) ;
printf ("\ n 2 . Pop ");
printf ("\ n 3 . beenden \ n ");
printf ("Geben Sie Ihre Wahl \ n");
scanf ("%d", & wählte);
Schalter (Auswahl)

Fall 1:
printf ("eine Nummer \ n");
scanf (" %d", & item);
Push (Stack, Artikel);
brechen ;
Fall 2:
item = pop (stapel);
if (item == - 1)
printf ("Stack ist leer");
anders
printf ("Poped Value ist %d", Artikel);
brechen ;
Fall 3:
exit (0);


Rückkehr 0;

Ausgang:

Erläuterung

Wie bereits erwähnt, definieren wir einen benutzerdefinierten Datentyp mit dem Namen ArrayStack. Es verfügt über drei Datenmitglieder mit dem Namen Top, Kapazität und ein Zeigerarray. Dann definieren wir eine Funktion namens CreateStack, bei der wir einen Wert übergeben, den der Gesamtblock des Arrays erstellt wird. Die malloc () -Funktion erstellt dieses Array und gibt die Adresse an den Variablenstapel zurück, der der ArrayStack -Typ ist. Das Stack-> Array enthält die Adresse des Arrays, die von der MALM () -Funktion erstellt wird.

Als nächstes definieren wir eine andere Funktion namens Full (), um zu überprüfen, ob der Stapel voll ist oder nicht.

Erstellen Sie eine andere Funktion mit dem Namen leer, um zu überprüfen, ob der Stapel leer ist.

Dann definieren wir eine andere Funktion namens Push (), bei der wir die Elemente eins nach dem anderen in den Stapel von einem Ende genannt werden. Um das Element in den Stapel einzufügen, überprüfen wir zunächst, ob der Stapel voll ist.

Dann definieren wir eine andere Funktion namens Pop (), in der wir die Elemente einzeln aus dem Stapel von einem Ende namens Top löschen. Um das Element im Stapel zu entfernen, überprüfen wir zunächst, ob der Stapel leer ist.

In der Funktion main () schreiben wir dann den Switch -Fall, um dem Benutzer eine Menüoption zu geben, um seine Wahl auszuwählen, ob das Element im Stapel eingefügt oder gelöscht wird.

Abschluss

Aus der Diskussion über den Stack sind wir zu dieser Schlussfolgerung gekommen, dass Stack eine gut definierte Datenstruktur ist, mit der die Daten auf strukturelle Weise verwaltet werden. Unser täglicher Lebensstapel ist in verschiedenen Bereichen implementiert, um Elemente zu speichern, einzufügen oder zu löschen.