Wdrożenie stosu w C

Możemy wdrożyć strukturę danych za pośrednictwem języka C. Istnieje kilka rodzajów struktury danych do przechowywania i dostępu do danych w wydajny sposób. Stos jest jednym z nich.

Stos to zmodyfikowana wersja tablicy. Możemy dodać lub usunąć element na jednym końcu stosu. Ten koniec jest na Szczyt stosu.

Stack to wyspecjalizowany sposób obsługi, przechowywania, wstawienia, usuwania, dostępu do danych. Ma charakter abstrakcyjny.

Tablica i stos

1. Istnieje nieco różnicy między tablicą a stosem pod względem ich dostępności. Możemy uzyskać dostęp do dowolnego elementu z tablicy w dowolnym stanie, ale w przypadku stosu możemy wstawić lub usunąć element z jednego końca jeden po drugim. Ten koniec nazywa się TOP. Pod względem dostępności tablica jest szybsza niż stos.
2. Stack ma dwie główne funkcje o nazwie push i pop.
3. Funkcja push służy do wstawienia do stosu, a funkcja pop jest używana do usuwania elementu ze stosu.

Reprezentacja

Możemy uzyskać dostęp tylko do ostatniego elementu wstawionego do stosu. To jest szczyt stosu. Możemy wstawić lub usunąć z góry.

Jest to znane jako ostatni w Fast Out (LIFO) i szybki w Last Out (Filo).

Realizacja

Stos można wdrożyć w następujący sposób:

-> Tablica -> dynamiczna tablica -> Lista linków

Operacja

-> Push -> pop

Algorytm Push: push (stos, top, maxstk, pozycja)

1. [Stos jest pełny]

Jeśli top == maxstk

Pokaż wiadomość: Przepełnienie i powrót

2. Ustaw top = góra + 1
3. Ustaw stos [u góry] = pozycja
4. Powrót

Algorytm Pop: Pop (stos, góra, pozycja)

1. [Element usunięty ze stosu]

Jeśli top == -1

Pokaż wiadomość: Underflow and Return

2. SET ITUTE = STACK [TOP]
3. TOP: TOP -1
4. Powrót

Ustaw za pomocą tablicy

Struct arraadzie

int top;
pojemność niepodpisana;
int *tablica;

Tutaj definiujemy typ danych zdefiniowany przez użytkownika o nazwie ArraYstack. Ma trzech członków danych o nazwie TOP, pojemność i wskaźnik o nazwie *tablica.

Polska notacja

Polska notacja pisze operatorów wyrażenia przed lub po ich operandzie.

Sposoby pisania:

Infix 2. Prefiks 3. Przyrostek

Infiks

Operatorzy są przechowywani między dwoma operandy.

Przykład: A + B

Prefiks

Operatorzy są przechowywani przed operandami.

Przykład: + A B

Przyrostek

Operatorzy są przechowywani po swoich operantach.

Przykład: A B +

Konwertować

1.

Infiks:
(A + b) * c
Prefiks:
* + A B C
Przyrostek:
A B + C *

2.

Infiks:
A + (B * C)
Prefiks:
+ A * b c
Przyrostek:
A B C * +

3.

Infix :( a + b) / (c - d)
Prefiks:/ + A B - C D
Postfix: A B + C D - /

Cała ta konwersja można wykonać za pomocą stosu. Teraz chcemy pokazać, w jaki sposób można utworzyć stos i jak wstawiono element lub dane. Elementy można usunąć ze stosu przez programowanie.

Przykład programowania

#włączać
#włączać
Int pozycja;
struct arraadzie // Zdefiniuj typ danych;

int top;
pojemność int;
int *tablica;
;
struct arraadzieck *createStack (int cap) // Utwórz stos;

struct arraadzie *stos;
Stack = Malloc (sizeof (struct arraadzie));
Stack-> top = - 1;
Stack-> pojemność = cap;
Stack-> array = Malloc (sizeof (int) * Stack-> pojemność);
powrót (stos);

int pełny (struct arraadzie *stos) // sprawdzanie stosu jest pełne lub nie.

if (Stack-> top == Stack-> pojemność-1)
zwrot (1);
w przeciwnym razie
zwrot (0);

int pusty (struct arraadzie *stos) // sprawdzanie stosu jest puste, czy nie.

if (Stack-> top == -1)
zwrot (1);
w przeciwnym razie
zwrot (0);

void push (struct arraadzie *stos, int item) // wstaw elementy do stosu;

Jeśli ( !Pełny (stos))

Stack-> top ++;
Stack-> tablica [Stack-> top] = item;


int Pop (struct arraadzie *stos) // usuń elementy ze stosu;

Jeśli ( !pusty (stos))

item = Stack-> tablica [Stack-> TOP];
Stack-> TOP-;
Zwróć przedmiot ) ;

zwrot (-1);

int main ()

wybór int;
struct arraadzie *stos;
Stack = CreateStack (4);
While (1)

printf ("\ n 1 . naciskać " ) ;
printf ("\ n 2 . Muzyka pop " ) ;
printf ("\ n 3 . exit \ n ");
printf („Wprowadź swój wybór \ n”);
Scanf („%d” i wybór);
przełącznik (wybór)

przypadek 1:
printf („Wprowadź numer \ n”);
Scanf („ %d” i item);
push (stos, przedmiot);
przerwa ;
Przypadek 2:
item = pop (stos);
if (item == - 1)
printf („stos jest pusty”);
w przeciwnym razie
printf („Wartość wyskakująca to %d”, pozycja);
przerwa ;
Przypadek 3:
wyjście (0);


powrót 0;

Wyjście:

Wyjaśnienie

Jak powiedzieliśmy wcześniej, definiujemy zdefiniowany przez użytkownika typ danych o nazwie ArraYstack. Ma trzech członków danych o nazwie TOP, pojemność i tablica wskaźnika. Następnie definiujemy funkcję o nazwie CreateStack, w której przekazujemy wartość, którą utworzony jest całkowity blok tablicy. Funkcja Malloc () tworzy tę tablicę i zwraca adres do stosu zmiennej, która jest typem ArraYstack. Tablica stosu-> zawiera adres tablicy, która jest tworzona przez funkcję Malloc ().

Następnie definiujemy inną funkcję o nazwie Full (), aby sprawdzić, czy stos jest pełny, czy nie.

Utwórz inną funkcję nazwaną pustą, aby sprawdzić, czy stos jest pusty.

Następnie definiujemy inną funkcję o nazwie push (), w której wkładamy elementy jeden po drugim w stosie z jednego końca o nazwie TOP. Aby wstawić element do stosu, najpierw sprawdzamy, czy stos jest pełny.

Następnie definiujemy inną funkcję o nazwie Pop (), w której usuwamy elementy jeden po drugim ze stosu z jednego końca o nazwie TOP. Aby usunąć element w stosie, najpierw sprawdzamy, czy stos jest pusty.

Następnie, wewnątrz funkcji Main (), piszemy obudowę przełącznika, aby zapewnić użytkownikowi opcję menu, aby wybrać jego wybór, czy element jest wstawiany, czy usuwany do stosu.

Wniosek

Z dyskusji na temat stosu doszliśmy do tego wniosku, że Stack jest dobrze zdefiniowaną strukturą danych, która jest używana do zarządzania danymi w sposób strukturalny. Nasz codzienny stos życia jest wdrażany w różnych dziedzinach do przechowywania, wstawienia lub usuwania elementów.