Meniu

Stivați structura datelor în C ++ cu ilustrație

  • Principal
  • Alte
  • Stivați structura datelor în C ++ cu ilustrație

stack data structure c with illustration

software de descărcare video YouTube pentru pc

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Tot ce trebuie să știți despre stiva în C ++.

Stiva este o structură fundamentală de date care este utilizată pentru a stoca elemente într-un mod liniar.

Urmează stiva LIFO (ultima intrare, prima ieșire) ordinea sau abordarea în care se efectuează operațiile. Aceasta înseamnă că elementul care a fost adăugat ultimul la stivă va fi primul element care va fi eliminat din stivă.

=> Vizitați aici pentru a vedea întreaga serie de formare C ++ pentru toți.

GRĂMADĂ

Ce veți învăța:

Stivați în C ++

O stivă este similară stivei din viața reală sau cu o grămadă de lucruri pe care le stivuim una peste alta.

Mai jos este prezentată o reprezentare picturală a Stack.

reprezentarea pictorială a stivei

Așa cum se arată mai sus, există o grămadă de plăci stivuite una peste alta. Dacă dorim să adăugăm un alt element la acesta, îl adăugăm în partea de sus a stivei așa cum se arată în figura de mai sus (partea stângă). Această operație de adăugare a unui articol la stivă se numește „ Apăsați ”.

În partea dreaptă, am arătat o operație opusă, adică eliminăm un articol din stivă. Acest lucru se face, de asemenea, de la același capăt, adică partea de sus a stivei. Această operație se numește „ Pop ”.

Așa cum se arată în figura de mai sus, vedem că împingerea și pop-ul sunt efectuate de la același capăt. Acest lucru face ca stiva să urmeze ordinea LIFO. Poziția sau capătul din care obiectele sunt împinse sau ieșite în / din stivă se numește „ Partea de sus a stivei ”.

Inițial, când nu există articole în stivă, partea de sus a stivei este setată la -1. Când adăugăm un element la stivă, partea superioară a stivei este incrementată cu 1 indicând faptul că elementul este adăugat. Spre deosebire de aceasta, partea de sus a stivei este decrementată cu 1 atunci când un articol este scos din stivă.

În continuare, vom vedea câteva dintre operațiunile de bază ale structurii de date a stivei de care vom avea nevoie în timpul implementării stivei.

Operațiuni de bază

Următoarele sunt operațiile de bază care sunt acceptate de stivă.

  • Apăsați - Adaugă sau împinge un element în stivă.
  • pop - Elimină sau scoate un element din stivă.
  • arunca o privire - Obține elementul superior al stivei, dar nu îl elimină.
  • e plin - Testează dacă stiva este plină.
  • este gol - Testează dacă stiva este goală.

Ilustrare

Stivă Ilustrație

Ilustrația de mai sus arată secvența de operații care sunt efectuate pe stivă. Inițial, stiva este goală. Pentru o stivă goală, partea de sus a stivei este setată la -1.

Apoi, împingem elementul 10 în stivă. Vedem că partea de sus a stivei indică acum elementul 10.

Apoi, efectuăm o altă operație de împingere cu elementul 20, ca urmare a căreia partea de sus a stivei indică acum 20. Această stare este a treia figură.

Acum, în ultima figură, efectuăm o operație pop (). Ca urmare a operației pop, elementul îndreptat în partea de sus a stivei este îndepărtat din stivă. Prin urmare, în figură, vedem că elementul 20 este eliminat din stivă. Astfel, partea de sus a stivei indică acum 10.

În acest fel, putem identifica cu ușurință abordarea LIFO utilizată de stack.

Implementare

# 1) Utilizarea matricelor

Urmează implementarea C ++ a stivei utilizând tablouri:

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

Ieșire:

Stack Push

Două

4

6

The Stack Pop:

6

4

Două

În ieșire, putem vedea că elementele sunt împinse în stivă într-o singură ordine și sunt scoase din stivă în ordine inversă. Aceasta prezintă abordarea LIFO (Last in, First out) pentru stivă.

Pentru implementarea matricei de mai sus a stivei, putem concluziona că acest lucru este foarte ușor de implementat, deoarece nu există indicatori implicați. Dar, în același timp, dimensiunea stivei este statică, iar stiva nu poate crește sau micșora dinamic.

Apoi, vom implementa stiva folosind matrici în limbajul de programare 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()); } } }

Ieșire:

Stack Push:

1

3

5

Stack Pop:

5

3

1

Logica de implementare este aceeași ca și în implementarea C ++. Ieșirea arată tehnica LIFO de împingere și ieșire din elemente în / din stivă.

După cum sa menționat deja, implementarea stivei utilizând matrici este cea mai simplă implementare, dar este de natură statică, deoarece nu putem crește sau micșora dinamic stiva.

# 2) Utilizarea unei liste conectate

Apoi, implementăm operațiuni de stivă folosind o listă legată atât în ​​C ++, cât și în Java. În primul rând, vom demonstra implementarea 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:'<

Ieșire:

Stack Push:

100

200

300

Elementul de sus este 300

Stack Pop:

300

200

100

Elementul de sus este -1

Apoi, prezentăm implementarea Java a stivei folosind o listă legată.

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

Ieșire:

Stack Push:

100

200

300

Elementul de sus este 300

Stack Pop:

300

200

100

Stiva este goală

Elementul de sus este -2147483648

Tocmai am văzut implementări C ++ și Java pentru o stivă folosind liste legate. Reprezentăm fiecare intrare de stivă ca un nod al listei legate. Cel mai important avantaj al acestei implementări este că este dinamic. Aceasta înseamnă că putem crește sau micșora dimensiunea stivei conform cerințelor noastre.

Acest lucru este diferit de cazul implementării stivei folosind tablouri în care trebuie să declarăm dimensiunea în prealabil și nu o putem modifica dinamic.

Ideea acestei implementări este că, pe măsură ce folosim indicii peste tot, ocupă puțin prea mult spațiu în comparație cu implementarea matricei.

Aplicațiile Stack

Să discutăm câteva dintre aplicațiile structurii de date a stivei. Structura de date a stivei este utilizată într-o serie de aplicații în programarea software, în principal datorită simplității și ușurinței sale de implementare.

Vom descrie pe scurt câteva dintre aplicațiile stivei de mai jos:

# 1) Infix la expresiile Postfix

Orice expresie generală aritmetică este de formă operand1 OP operand 2 .

Pe baza poziției operatorului OP, avem următoarele tipuri de expresii:

cum se deschid fișiere .7z pe Mac
  • Infix - Forma generală a expresiei infix este „ operand1 OP operand 2 ”. Aceasta este forma de bază a expresiei și o folosim tot timpul în matematică.
  • Prefix - Când un operator este plasat înaintea operanzilor, acesta este o expresie de prefix. Forma generală a expresiei infix este „ OP operand1 operand2 ”.
  • Postfix - În expresiile postfix, se scriu mai întâi operanzii urmate de operator. Are forma „operand1 operand2 OP”.

Luați în considerare expresia „a + b * c ' . Compilatorul scanează expresia fie de la stânga la dreapta, fie de la dreapta la stânga. Având grijă de prioritatea și asociativitatea operatorului, acesta va scana mai întâi expresia pentru a evalua expresia b * c. Apoi, va trebui din nou să scaneze expresia pentru a adăuga rezultatul lui b * c la a.

Pe măsură ce expresiile devin din ce în ce mai complexe, acest tip de abordare a scanării repetate a expresiei devine ineficient.

Pentru a depăși această ineficiență, convertim expresia în postfix sau prefix astfel încât să poată fi ușor evaluate utilizând o structură de date stivă.

# 2) Analizarea / evaluarea expresiei

Folosind stiva, putem efectua, de asemenea, evaluarea expresiei reale. În acest sens, expresia este scanată de la stânga la dreapta, iar operanzii sunt împinși pe stivă.

Ori de câte ori se întâlnește un operator, operanzii sunt evidențiați și operația este efectuată. Rezultatul operației este din nou împins în stivă. Acest mod în care expresia este evaluată folosind stiva și rezultatul final al expresiei este de obicei partea de sus a stivei.

# 3) Traversări în copaci

Structura de date arborescentă poate fi parcursă pentru a vizita fiecare nod în multe moduri și în funcție de momentul în care este vizitat nodul rădăcină pe care îl avem.

  • în traversarea comenzii
  • precomanda Traversal
  • traversarea postOrder

Pentru a traversa în mod eficient arborele, folosim structura de date a stivei pentru a împinge noduri intermediare pe stivă astfel încât să menținem ordinea de traversare.

# 4) Algoritmi de sortare

Algoritmii de sortare precum quicksort pot fi eficientizați folosind structurile de date stive.

# 5) Turnurile din Hanoi

Aceasta este o problemă clasică care implică n număr de discuri și trei turnuri, iar problema implică mutarea discurilor dintr-un turn în altul cu cel de-al treilea turn folosit ca intermediar.

Această problemă poate fi abordată în mod eficient folosind stiva, pe măsură ce împingem discurile pentru a fi mutate pe stivă, deoarece stiva acționează practic ca un turn utilizat pentru a muta discurile.

Concluzie

Stiva este cea mai simplă structură de date și mai ușor de implementat ca program. A folosit abordarea LIFO (ultima intrare, prima ieșire), ceea ce înseamnă că elementul introdus ultima este cel care este eliminat mai întâi. Acest lucru se datorează faptului că stiva folosește un singur capăt pentru a adăuga (împinge) și a elimina (pop) elemente.

Structura de date a stivei are multe utilizări în programarea software-ului. Cea mai importantă dintre acestea este evaluarea expresiei. Evaluarea expresiei include și convertirea expresiei din infix în postfix sau prefix. De asemenea, implică evaluarea expresiei pentru a produce rezultatul final.

În acest tutorial, am văzut ilustrarea și implementarea stivei, precum și diferitele operațiuni ale acesteia.

În viitorul nostru tutorial, vom afla detaliat structura datelor cozii.

=> Vizitați aici pentru cursul complet C ++ de la experți.

Lectură recomandată

^