Menu

Skládejte datovou strukturu v C ++ s ilustrací

  • Hlavní
  • Jiný
  • Skládejte datovou strukturu v C ++ s ilustrací

stack data structure c with illustration

software pro kopírování DVD do počítače

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Vše, co potřebujete vědět o zásobníku v C ++.

Stack je základní datová struktura, která se používá k lineárnímu ukládání prvků.

Následuje zásobník LIFO (poslední dovnitř, první ven) pořadí nebo přístup, ve kterém jsou operace prováděny. To znamená, že prvek, který byl do zásobníku přidán jako poslední, bude prvním prvkem, který bude ze zásobníku odebrán.

=> Navštivte zde a prohlédněte si celou sérii školení C ++ pro všechny.

ZÁSOBNÍK

Co se naučíte:

Stack In C ++

Zásobník je podobný zásobníku v reálném životě nebo hromadě věcí, které skládáme jeden nad druhým.

Níže je uvedeno obrázkové znázornění Stacku.

obrazové znázornění zásobníku

Jak je znázorněno výše, existuje hromada desek naskládaných na sebe. Pokud k tomu chceme přidat další položku, přidáme ji na začátek zásobníku, jak je znázorněno na obrázku výše (vlevo). Tato operace přidání položky do zásobníku se nazývá „ Tam “.

Na pravé straně jsme ukázali opačnou operaci, tj. Odstraníme položku ze zásobníku. To se také děje ze stejného konce, tj. Horní části zásobníku. Tato operace se nazývá „ Pop “.

Jak je znázorněno na výše uvedeném obrázku, vidíme, že push a pop jsou prováděny ze stejného konce. Díky tomu může zásobník sledovat pořadí LIFO. Pozice nebo konec, ze kterého jsou položky tlačeny dovnitř nebo vyskakovány do / ze zásobníku, se nazývá „ Horní část zásobníku “.

Zpočátku, když v zásobníku nejsou žádné položky, je horní část zásobníku nastavena na -1. Když přidáme položku do zásobníku, horní část zásobníku se zvýší o 1, což znamená, že je položka přidána. Na rozdíl od toho je horní část zásobníku snížena o 1, když je položka vyskakována ze zásobníku.

Dále uvidíme některé základní operace datové struktury zásobníku, které budeme vyžadovat při implementaci zásobníku.

Základní operace

Následuje základní operace, které zásobník podporuje.

  • tam - Přidá nebo vloží prvek do zásobníku.
  • pop - Odebere nebo vyskočí prvek ze zásobníku.
  • nahlédnout - Získá horní prvek zásobníku, ale neodstraní ho.
  • je plný - Testuje, zda je zásobník plný.
  • je prázdný - Testuje, zda je zásobník prázdný.

Ilustrace

Zásobník ilustrace

Výše uvedený obrázek ukazuje posloupnost operací prováděných na zásobníku. Zpočátku je zásobník prázdný. U prázdného zásobníku je horní část zásobníku nastavena na -1.

Dále vtlačíme prvek 10 do stohu. Vidíme, že horní část zásobníku nyní ukazuje na prvek 10.

Dále provedeme další operaci push s prvkem 20, v důsledku čehož horní část zásobníku nyní ukazuje na 20. Tento stav je třetí obrázek.

Nyní na posledním obrázku provedeme operaci pop (). V důsledku operace pop je prvek nasměrovaný na horní část zásobníku odebrán ze zásobníku. Na obrázku tedy vidíme, že prvek 20 je odstraněn ze zásobníku. Horní část zásobníku tedy nyní ukazuje na 10.

Tímto způsobem můžeme snadno rozeznat přístup LIFO používaný zásobníkem.

Implementace

# 1) Používání polí

Následuje implementace C ++ zásobníku pomocí polí:

#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<

Výstup:

The Stack Push

dva

4

6

The Stack Pop:

6

4

dva

Na výstupu vidíme, že prvky jsou vloženy do zásobníku v jednom pořadí a jsou vyskakovány ze zásobníku v opačném pořadí. To ukazuje přístup LIFO (Last in, First out) pro zásobník.

U výše uvedené implementace pole zásobníku můžeme dojít k závěru, že je velmi snadné jej implementovat, protože zde nejsou zahrnuty žádné ukazatele. Zároveň je ale velikost zásobníku statická a zásobník se nemůže dynamicky zvětšovat ani zmenšovat.

Dále budeme implementovat zásobník pomocí polí v programovacím jazyce 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()); } } }

Výstup:

Stack Push:

1

3

5

Stack Pop:

5

3

1

Logika implementace je stejná jako v implementaci C ++. Výstup ukazuje techniku ​​LIFO natlačování a vyskakování prvků do / ze zásobníku.

Jak již bylo uvedeno, implementace zásobníku pomocí polí je nejjednodušší implementací, ale má statickou povahu, protože nemůžeme dynamicky růst nebo zmenšit zásobník.

# 2) Použití propojeného seznamu

Dále implementujeme operace zásobníku pomocí propojeného seznamu v C ++ i Java. Nejprve si ukážeme implementaci 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:'<

Výstup:

Stack Push:

100

200

300

Horní prvek je 300

Stack Pop:

300

200

100

Horní prvek je -1

Dále představíme implementaci zásobníku Java pomocí propojeného seznamu.

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()); } }

Výstup:

Stack Push:

100

200

300

Horní prvek je 300

Stack Pop:

300

200

100

Zásobník je prázdný

Horní prvek je -2147483648

Právě jsme viděli implementace C ++ a Java pro zásobník pomocí propojených seznamů. Každou položku zásobníku představujeme jako uzel propojeného seznamu. Nejdůležitější výhodou této implementace je, že je dynamická. To znamená, že můžeme zvětšit nebo zmenšit velikost zásobníku podle našeho požadavku.

To je na rozdíl od případu implementace zásobníku pomocí polí, ve kterých musíme předem deklarovat velikost a nemůžeme ji dynamicky měnit.

Nevýhodou této implementace je, že když používáme ukazatele všude, ve srovnání s implementací pole zabírá trochu příliš mnoho místa.

Aplikace Stack

Pojďme diskutovat o některých aplikacích datové struktury zásobníku. Struktura dat zásobníku se používá v řadě aplikací v programování softwaru, hlavně kvůli své jednoduchosti a snadné implementaci.

Stručně popíšeme některé aplikace zásobníku níže:

# 1) Infix to Postfix Expressions

Jakýkoli obecný aritmetický výraz má formu operand1 OP operand 2 .

Na základě pozice operátora OP máme následující typy výrazů:

  • Infix - Obecná forma infix výrazu je „ operand1 OP operand 2 “. Toto je základní forma výrazu, kterou v matematice používáme pořád.
  • Předpona - Když je operátor umístěn před operandy, jedná se o předponový výraz. Obecná forma infix výrazu je „ OP operand1 operand2 “.
  • Postfix - Ve výrazech postfixu se nejdříve zapíšou operandy a poté operátor. Má formu „operand1 operand2 OP“.

Zvažte výraz „a + b * c ' . Kompilátor skenuje výraz zleva doprava nebo zprava doleva. Postará se o prioritu operátora a asociativitu, nejprve naskenuje výraz a vyhodnotí výraz b * c. Dále bude muset znovu naskenovat výraz a přidat výsledek b * c do a.

nejlepší způsob čištění registru systému Windows 10

Jak jsou výrazy čím dál složitější, stává se tento druh přístupu k opakovanému skenování výrazu neúčinným.

Abychom překonali tuto neúčinnost, převádíme výraz na postfix nebo prefix tak, aby je bylo možné snadno vyhodnotit pomocí datové struktury zásobníku.

# 2) Analýza / vyhodnocení výrazů

Pomocí zásobníku můžeme také provést vlastní vyhodnocení výrazu. V tomto je výraz skenován zleva doprava a operandy jsou přeneseny do zásobníku.

Kdykoli se setkáte s operátorem, operandy se vyskočí a operace se provede. Výsledek operace je znovu vložen do zásobníku. Tímto způsobem se výraz vyhodnotí pomocí zásobníku a konečným výsledkem výrazu je obvykle aktuální horní část zásobníku.

# 3) Procházení stromů

Stromovou datovou strukturu lze procházet a navštívit každý uzel mnoha způsoby a podle toho, kdy je navštíven kořenový uzel, který máme.

  • procházení objednávky
  • předobjednat Traversal
  • přechod po objednávce

Abychom strom mohli efektivně procházet, využíváme datovou strukturu zásobníku, abychom poslali mezilehlé uzly na zásobníku, abychom udrželi pořadí procházení.

# 4) Třídění algoritmů

Algoritmy řazení jako quicksort lze zefektivnit pomocí datových struktur zásobníku.

# 5) Věže z Hanoje

Jedná se o klasický problém zahrnující n počet disků a tři věže a problém zahrnuje přesun disků z jedné věže do druhé, přičemž třetí věž byla použita jako mezilehlá.

Tento problém lze efektivně řešit pomocí stohu, když tlačíme disky, které mají být přesunuty, do stohu, protože stoh v podstatě funguje jako věž používaná k pohybu disků.

Závěr

Zásobník je nejjednodušší datovou strukturou a je snadněji implementovatelný jako program. Použil přístup LIFO (poslední dovnitř, první ven), což znamená, že naposledy zadaný prvek je ten, který je odstraněn jako první. Je to proto, že zásobník používá pouze jeden konec k přidání (push) a odebrání (pop) prvků.

Struktura dat zásobníku má mnoho využití v programování softwaru. Mezi nejvýznamnější patří hodnocení výrazů. Vyhodnocení výrazu zahrnuje také převod výrazu z infixu na postfix nebo prefix. Zahrnuje také vyhodnocení výrazu za účelem získání konečného výsledku.

V tomto kurzu jsme viděli ilustraci a implementaci zásobníku i jeho různé operace.

V našem připravovaném výukovém programu se podrobně seznámíme se strukturou dat fronty.

=> Navštivte zde kompletní kurz C ++ od odborníků.

Doporučené čtení

^