Menu

Struktura danych stosu w C ++ z ilustracjami

stack data structure c with illustration

automatyzacja kompilacji pomoże w

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Wszystko, co musisz wiedzieć o stosie w C ++.

Stos to podstawowa struktura danych, która służy do przechowywania elementów w sposób liniowy.

Stos następuje LIFO (ostatnie weszło, pierwsze wyszło) kolejność lub podejście, w jakim wykonywane są operacje. Oznacza to, że element, który został dodany jako ostatni do stosu, będzie pierwszym elementem, który zostanie usunięty ze stosu.

=> Odwiedź tutaj, aby zobaczyć całą serię szkoleń C ++ dla wszystkich.

STOS

Czego się nauczysz:

Stos w C ++

Stos jest podobny do stosu rzeczywistego lub stosu rzeczy, które układamy jeden nad drugim.

Poniżej znajduje się obrazowe przedstawienie stosu.

obrazowe przedstawienie stosu

Jak pokazano powyżej, jest stos płyt ułożonych jeden na drugim. Jeśli chcemy dodać do niego kolejny przedmiot, dodajemy go na szczycie stosu, jak pokazano na powyższym rysunku (po lewej stronie). Ta operacja dodawania elementu do stosu nazywa się „ Pchać ”.

Po prawej stronie pokazaliśmy odwrotną operację, czyli usunięcie elementu ze stosu. Odbywa się to również z tego samego końca, tj. Z góry stosu. Ta operacja nazywa się „ Muzyka pop ”.

Jak pokazano na powyższym rysunku, widzimy, że push i pop są wykonywane z tego samego końca. To sprawia, że ​​stos jest zgodny z kolejnością LIFO. Pozycja lub koniec, z którego elementy są wpychane lub wysuwane ze stosu, nazywa się „ Szczyt stosu ”.

Początkowo, gdy w stosie nie ma żadnych elementów, szczyt stosu jest ustawiany na -1. Kiedy dodajemy element do stosu, wierzchołek stosu jest zwiększany o 1, co oznacza, że ​​element został dodany. W przeciwieństwie do tego, szczyt stosu jest zmniejszany o 1, gdy przedmiot jest wyskakiwany ze stosu.

Następnie zobaczymy niektóre z podstawowych operacji struktury danych stosu, których będziemy wymagać podczas implementacji stosu.

Podstawowe operacje

Poniżej przedstawiono podstawowe operacje obsługiwane przez stos.

  • Pchać - Dodaje lub wypycha element do stosu.
  • Muzyka pop - Usuwa lub zdejmuje element ze stosu.
  • podgląd - Pobiera górny element stosu, ale go nie usuwa.
  • jest pełna - Sprawdza, czy stos jest pełny.
  • jest pusty - Sprawdza, czy stos jest pusty.

Ilustracja

Ilustracja stosu

Powyższa ilustracja przedstawia sekwencję operacji wykonywanych na stosie. Początkowo stos jest pusty. W przypadku pustego stosu szczyt stosu jest ustawiony na -1.

Następnie wsuwamy element 10 do stosu. Widzimy, że wierzchołek stosu wskazuje teraz na element 10.

Następnie wykonujemy kolejną operację wypychania z elementem 20, w wyniku której wierzchołek stosu wskazuje teraz na 20. Ten stan jest trzecią liczbą.

Na ostatnim rysunku wykonujemy operację pop (). W wyniku operacji wyskakiwania element wskazany na szczycie stosu jest usuwany ze stosu. Stąd na rysunku widzimy, że element 20 jest usuwany ze stosu. Zatem szczyt stosu wskazuje teraz 10.

W ten sposób możemy łatwo rozpoznać podejście LIFO używane przez stos.

Realizacja

# 1) Korzystanie z tablic

Poniżej przedstawiono implementację stosu w języku C ++ przy użyciu tablic:

#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack[MAX]; //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack[++top] = item; cout<

Wynik:

Wypychanie stosu

dwa

4

6

The Stack Pop:

6

4

dwa

Na wyjściu widzimy, że elementy są wkładane do stosu w jednej kolejności i wyskakują ze stosu w odwrotnej kolejności. To pokazuje podejście LIFO (Last in, First out) dla stosu.

W przypadku powyższej tablicy implementacji stosu możemy wywnioskować, że jest to bardzo łatwe do zaimplementowania, ponieważ nie ma żadnych wskaźników. Ale jednocześnie rozmiar stosu jest statyczny, a stos nie może się dynamicznie zwiększać ani zmniejszać.

Następnie zaimplementujemy stos przy użyciu tablic w języku programowania Java.

class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack[] = new int[MAX]; boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack[++top] = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack[top--]; return item; } } } //Main class code class Main { public static void main(String args[]) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } }

Wynik:

Wypychanie stosu:

1

3

5

Stack Pop:

5

3

1

Logika implementacji jest taka sama jak w implementacji C ++. Dane wyjściowe pokazują technikę LIFO wpychania i wyskakiwania elementów do / ze stosu.

Jak już wspomniano, implementacja stosu przy użyciu tablic jest najprostszą implementacją, ale ma charakter statyczny, ponieważ nie możemy dynamicznie zwiększać ani zmniejszać stosu.

# 2) Korzystanie z połączonej listy

Następnie implementujemy operacje na stosie za pomocą połączonej listy w C ++ i Javie. Najpierw zademonstrujemy implementację C ++.

#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'<

Wynik:

Wypychanie stosu:

100

200

300

Górny element to 300

Stack Pop:

300

200

100

Górny element to -1

Następnie przedstawiamy implementację stosu w języku Java za pomocą połączonej listy.

class LinkedListStack { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } } class Main{ public static void main(String[] args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } }

Wynik:

Wypychanie stosu:

100

200

300

Górny element to 300

Stack Pop:

300

200

100

Stos jest pusty

Górny element to -2147483648

Właśnie widzieliśmy implementacje C ++ i Java dla stosu używającego połączonych list. Reprezentujemy każdy wpis stosu jako węzeł połączonej listy. Najważniejszą zaletą tej implementacji jest to, że jest dynamiczna. Oznacza to, że możemy zwiększyć lub zmniejszyć rozmiar stosu zgodnie z naszymi wymaganiami.

Inaczej jest w przypadku implementacji stosu przy użyciu tablic, w których musimy wcześniej zadeklarować rozmiar i nie możemy go dynamicznie zmieniać.

Wadą tej implementacji jest to, że ponieważ wszędzie używamy wskaźników, zajmuje ona trochę za dużo miejsca w porównaniu z implementacją tablicową.

Zastosowania stosu

Omówmy niektóre zastosowania struktury danych stosu. Struktura danych stosu jest wykorzystywana w wielu aplikacjach w programowaniu, głównie ze względu na prostotę i łatwość implementacji.

Poniżej krótko opiszemy niektóre zastosowania stosu:

# 1) Infix To Postfix Expressions

Dowolne ogólne wyrażenie arytmetyczne ma postać operand 1 operand OP 2 .

Na podstawie pozycji operatora OP mamy następujące typy wyrażeń:

  • Infiks - Ogólna forma wyrażenia wrostek to „ operand 1 operand OP 2 ”. To jest podstawowa forma wyrażenia, której używamy w matematyce przez cały czas.
  • Prefiks - Gdy operator jest umieszczony przed operandami, jest to wyrażenie przedrostkowe. Ogólna forma wyrażenia wrostek to „ OP operand1 operand2 ”.
  • Przyrostek - W wyrażeniach z przyrostkiem operandy są zapisywane jako pierwsze, a po nich operator. Ma postać „operand1 operand2 OP”.

Rozważ wyrażenie „a + b * c ' . Kompilator skanuje wyrażenie od lewej do prawej lub od prawej do lewej. Dbając o pierwszeństwo operatorów i łączność, najpierw przeskanuje wyrażenie, aby ocenić wyrażenie b * c. Następnie ponownie będzie musiał przeskanować wyrażenie, aby dodać wynik b * c do a.

jak zainstalować plik .bin

W miarę jak wyrażenia stają się coraz bardziej złożone, tego rodzaju podejście polegające na wielokrotnym skanowaniu wyrażenia staje się nieefektywne.

Aby przezwyciężyć tę nieefektywność, konwertujemy wyrażenie na przyrostek lub przedrostek, tak aby można je było łatwo ocenić za pomocą struktury danych stosu.

# 2) Analiza / ocena wyrażeń

Korzystając ze stosu, możemy również przeprowadzić rzeczywistą ocenę wyrażenia. W tym przypadku wyrażenie jest skanowane od lewej do prawej, a operandy są umieszczane na stosie.

Za każdym razem, gdy napotkany jest operator, operandy są wyskakujące i wykonywana jest operacja. Wynik operacji jest ponownie wrzucany do stosu. W ten sposób wyrażenie jest oceniane przy użyciu stosu, a ostatecznym wynikiem wyrażenia jest zwykle bieżący szczyt stosu.

# 3) Przechodzenie po drzewie

Po strukturze danych drzewa można przejść, aby odwiedzić każdy węzeł na wiele sposobów iw zależności od tego, kiedy odwiedzany jest węzeł główny, który mamy.

  • Przechodzenie inOrder
  • przedsprzedaż Traversal
  • przechodzenie przez postOrder

Aby efektywnie przejść przez drzewo, używamy struktury danych stosu w celu wypychania węzłów pośrednich na stosie, aby zachować kolejność przemierzania.

# 4) Algorytmy sortowania

Algorytmy sortowania, takie jak quicksort, mogą być bardziej wydajne przy użyciu struktur danych stosu.

# 5) Wieże Hanoi

Jest to klasyczny problem dotyczący liczby n dysków i trzech wież, a problem polega na przenoszeniu dysków z jednej wieży do drugiej, przy czym trzecia wieża jest używana jako pośrednia.

Ten problem można skutecznie rozwiązać za pomocą stosu, gdy popychamy dyski, które mają być przeniesione na stos, ponieważ stos zasadniczo działa jak wieża służąca do przenoszenia dysków.

Wniosek

Stos jest najprostszą strukturą danych i jest łatwiejszy do wdrożenia jako program. Zastosowano podejście LIFO (ostatnie weszło, pierwsze wyszło), co oznacza, że ​​element wprowadzony jako ostatni jest tym, który jest usuwany jako pierwszy. Dzieje się tak, ponieważ stos używa tylko jednego końca do dodawania (wypychania) i usuwania (pop) elementów.

Struktura danych stosu ma wiele zastosowań w programowaniu. Najważniejszą z nich są oceny wyrażeń. Ocena wyrażenia obejmuje również konwersję wyrażenia z wrostka na przyrostek lub przedrostek. Obejmuje również ocenę wyrażenia w celu uzyskania końcowego wyniku.

W tym samouczku widzieliśmy ilustrację i implementację stosu, a także różne jego operacje.

W naszym nadchodzącym samouczku szczegółowo poznamy strukturę danych kolejki.

=> Odwiedź tutaj, aby zapoznać się z pełnym kursem C ++ od ekspertów.

rekomendowane lektury

^