Structura de date a stivei este o structură liniară a datelor care urmează Principiul LIFO (Last In First Out). , deci ultimul element inserat este primul care apare. În acest articol, vom acoperi toate elementele de bază ale Stivei, Operațiunile pe Stivă, implementarea acestuia, avantajele, dezavantajele care vă vor ajuta să rezolvați toate problemele bazate pe Stiva.

Cuprins

• Ce este Stack Data Structure?
• Operații de bază privind structura datelor stivei
• Operație isEmpty în structura de date stiva
• Implementarea structurii de date a stivei folosind Linked List
• Analiza complexității operațiunilor pe structura datelor stivei
• Avantajele structurii de date stive
• Dezavantajele structurii de date stive
• Aplicații ale structurii de date stive

Ce este Stack Data Structure?

Grămadă este o structură liniară a datelor bazat pe Principiul LIFO (Last In First Out). în care inserarea unui element nou și îndepărtarea unui element existent are loc la același capăt reprezentat ca și top a stivei.

Pentru a implementa stiva, este necesar să se mențină indicatorul spre partea de sus a stivei , care este ultimul element care trebuie inserat deoarece putem accesa elementele doar din partea de sus a stivei.

Reprezentarea structurii datelor stivei:

Stack urmează principiul LIFO (Last In First Out), astfel încât elementul care este împins ultimul este scos primul.

Stivă cu dimensiuni fixe : După cum sugerează și numele, o stivă de dimensiune fixă ​​are o dimensiune fixă ​​și nu poate crește sau micșora dinamic. Dacă stiva este plină și se încearcă adăugarea unui element la acesta, apare o eroare de depășire. Dacă stiva este goală și se încearcă eliminarea unui element din ea, apare o eroare de underflow.

Stiva de dimensiuni dinamice : O stivă de dimensiuni dinamice poate crește sau micșora dinamic. Când stiva este plină, își mărește automat dimensiunea pentru a găzdui noul element, iar când stiva este goală, își scade dimensiunea. Acest tip de stivă este implementat folosind o listă legată, deoarece permite redimensionarea ușoară a stivei.

Operații de bază pe stivă Structură de date :

Pentru a face manipulări într-o stivă, există anumite operațiuni care ni se oferă.

alternativa xampp

• Apăsaţi() pentru a introduce un element în stivă
• pop() pentru a elimina un element din stivă
• top() Returnează elementul superior al stivei.
• este gol() returnează true dacă stiva este goală, altfel false.
• e plin() returnează true dacă stiva este plină, altfel false.

Algoritm pentru operația Push:

• Înainte de a împinge elementul spre stivă, verificăm dacă stiva este deplin .
• Dacă stiva este plină (sus == capacitate-1) , apoi Debordări de stivă și nu putem introduce elementul în stivă.
• În caz contrar, creștem valoarea topului cu 1 (sus = sus + 1) iar noua valoare este inserată la poziție de vârf .
• Elementele pot fi împinse în stivă până ajungem la capacitate a stivei.

Algoritm pentru operarea pop:

• Înainte de a scoate elementul din stivă, verificăm dacă stiva este gol .
• Dacă stiva este goală (sus == -1), atunci Stivă Underflows și nu putem elimina niciun element din stivă.
• În caz contrar, stocăm valoarea în partea de sus, decrementăm valoarea topului cu 1 (sus = sus – 1) și returnează valoarea maximă stocată.

Algoritm pentru operarea de top:

• Înainte de a returna elementul de sus din stivă, verificăm dacă stiva este goală.
• Dacă stiva este goală (sus == -1), pur și simplu tipărim Stack is empty.
• În caz contrar, returnăm elementul stocat la index = top .

Algoritm pentru operația isEmpty :

• Verificați valoarea de top în stivă.
• Dacă (sus == -1) , atunci stiva este gol deci întoarce-te Adevărat .
• În caz contrar, stiva nu este goală, așa că întoarce-te fals .

Algoritm pentru isFull Operation:

dimensiunea textului din latex

• Verificați valoarea de top în stivă.
• Dacă (sus == capacitate-1), atunci stiva este deplin deci întoarce-te Adevărat .
• În caz contrar, stiva nu este plină, așa că întoarceți-vă fals .

Implementarea Stivei Structură de date :

Operațiunile de bază care pot fi efectuate pe o stivă includ push, pop și peek. Există două moduri de a implementa o stivă -

• Folosind Array
• Utilizarea listei conectate

Într-o implementare bazată pe matrice, operația de push este implementată prin creșterea indexului elementului superior și stocarea noului element la acel index. Operația pop este implementată prin returnarea valorii stocate la indexul de sus și apoi decrementând indexul elementului de sus.

Într-o implementare bazată pe liste legate, operația push este implementată prin crearea unui nou nod cu noul element și setarea următorului pointer al nodului superior curent la noul nod. Operația pop este implementată prin setarea următorului pointer al nodului superior curent la următorul nod și returnând valoarea nodului superior curent.

/* Program C++ pentru implementarea stivei de bază operațiuni */ #include #include folosind spatiu de nume std; #definiți MAX 1000 clasă Grămadă { int top; public: int A[MAX]; // Dimensiunea maximă a stivei Grămadă() { top = -1; } bool Apăsaţi(int X); int pop(); int arunca o privire(); bool este gol(); }; bool Stack::push(int X) { dacă (top >= (MAX - 1)) { cout << 'stiva='' debordare'<='' span=''>; întoarcere fals; } altfel { A[++top] = X; cout << X << ' împins în stivă '; întoarcere Adevărat; } } int Stack::pop() { dacă (top < 0) { cout << „Stive Underflow”; întoarcere 0; } altfel { int X = A[top--]; întoarcere X; } } int Stack::peek() { dacă (top < 0) { cout << „Stiva este goală”; întoarcere 0; } altfel { int X = A[top]; întoarcere X; } } bool Stack::isEmpty() { întoarcere (top < 0); } // Program driver pentru a testa funcțiile de mai sus int principal() { clasă Grămadă s; s.Apăsaţi(10); s.Apăsaţi(douăzeci); s.Apăsaţi(30); cout << s.pop() << ' A ieșit din stivă '; //imprimați elementul superior al stivei după popping cout << „Elementul de sus este:” << s.arunca o privire() << endl; //printează toate elementele din stivă: cout <<„Elemente prezente în stivă :”; in timp ce(!s.este gol()) { // imprimă elementul superior în stivă cout << s.arunca o privire() <<' '; // elimină elementul superior din stivă s.pop(); } întoarcere 0; } //Codul este modificat de Vinay PandeyC

// C program for array implementation of stack #include  #include  #include  // A structure to represent a stack struct Stack {  int top;  unsigned capacity;  int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) {  struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));  stack->capacitate = capacitate;  stivă->top = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  stiva de returnare; } // Stiva este plină când top este egal cu ultimul index int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Stiva este goală când top este egal cu -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funcție pentru a adăuga un articol la stivă. Mărește partea de sus cu 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = element;  printf('%d împins la stivă
', element); } // Funcție pentru a elimina un articol din stivă. Descrește top cu 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stivă->array[stivă->sus--]; } // Funcție de a returna partea de sus din stivă fără a-l elimina int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stivă->array[stivă->sus]; } // Program driver pentru a testa funcțiile de mai sus int main() { struct Stack* stack = createStack(100);  împinge (stiva, 10);  împinge (stiva, 20);  împinge (stiva, 30);  printf('%d a apărut din stivă
', pop(stivă));  întoarce 0; }>>>Java-1;i--){ System.out.print(' '+ a[i]);  } } } // Clasa cod driver Main { public static void main(String args[]) { Stack s = new Stack();  s.împinge(10);  s.împinge(20);  s.împinge(30);  System.out.println(s.pop() + ' Ieșit din stivă');  System.out.println('Elementul de sus este :' + s.peek());  System.out.print('Elementele prezente în stivă :');  sprint();  } } //Acest cod este modificat de Vinay Pandey>

Piton

# Python program for implementation of stack # import maxsize from sys module  # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions  stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>

C#

// C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack {  private int[] ele;  private int top;  private int max;  public Stack(int size)  {  ele = new int[size]; // Maximum size of Stack  top = -1;  max = size;  }  public void push(int item)  {  if (top == max - 1) {  Console.WriteLine('Stack Overflow');  return;  }  else {  ele[++top] = item;  }  }  public int pop()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top--];  }  }  public int peek()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top];  }  }  public void printStack()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return;  }  else {  for (int i = 0; i <= top; i++) {  Console.WriteLine('{0} pushed into stack',  ele[i]);  }  }  } } // Driver program to test above functions class Program {  static void Main()  {  Stack p = new Stack(5);  p.push(10);  p.push(20);  p.push(30);  p.printStack();  p.pop();  } } }>

Javascript

/* javascript program to implement basic stack operations  */  var t = -1;  var MAX = 1000;  var a = Array(MAX).fill(0); // Maximum size of Stack  function isEmpty() {  return (t < 0);  }  function push(x) {  if (t>= (MAX - 1)) { console.log('Stack Overflow');  returnează fals;  } else { t+=1;  a[t] = x;    console.log(x + ' împins în stivă ');  returnează adevărat;  } } funcția pop() { dacă (t< 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  t-=1;  return x;  }  }  function peek() {  if (t < 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  return x;  }  }  function print() {  for (i = t; i>-1; i--) { console.log(' ' + a[i]);  } } push(10);  împinge(20);  împinge(30);  console.log(pop() + ' Ieșit din stivă');  console.log(' Elementul de sus este :' + peek());  console.log(' Elemente prezente în stiva : ');  imprimare(); // Acest cod este contribuit de Rajput-Ji>>>  
  Ieșire      Avantajele implementării matricei:    
 
Ușor de implementat.
Memoria este salvată deoarece pointerii nu sunt implicați.
    Dezavantajele implementării matricei:    
 
Nu este dinamic, adică nu crește și nu se micșorează în funcție de nevoi în timpul execuției. [Dar în cazul matricelor de dimensiuni dinamice, cum ar fi vector în C++, listă în Python, ArrayList în Java, stivele pot crește și micșora și cu implementarea matricei].
Mărimea totală a stivei trebuie definită în prealabil.

// Program C++ pentru implementarea listelor legate de stiva #include folosind spatiu de nume std; // O structură pentru a reprezenta o stivă clasă StackNode { public: int date; StackNode* Următorul; }; StackNode* newNode(int date) { StackNode* stackNode = nou StackNode(); stackNode->date = date; stackNode->Următorul = NUL; întoarcere stackNode; } int este gol(StackNode* rădăcină) { întoarcere !rădăcină; } gol Apăsaţi(StackNode** rădăcină, int date) { StackNode* stackNode = newNode(date); stackNode->Următorul = *rădăcină; *rădăcină = stackNode; cout << date << 'pused='' to='' stack<='' span=''> '; } int pop(StackNode** rădăcină) { dacă (este gol(*rădăcină)) întoarcere INT_MIN; StackNode* temp = *rădăcină; *rădăcină = (*rădăcină)->Următorul; int a izbucnit = temp->date; gratuit(temp); întoarcere a izbucnit; } int arunca o privire(StackNode* rădăcină) { dacă (este gol(rădăcină)) întoarcere INT_MIN; întoarcere rădăcină->date; } // Codul șoferului int principal() { StackNode* rădăcină = NUL; Apăsaţi(&rădăcină, 10); Apăsaţi(&rădăcină, douăzeci); Apăsaţi(&rădăcină, 30); cout << pop(&rădăcină) << ' a ieșit din stivă '; cout << „Elementul de sus este” << arunca o privire(rădăcină) << endl; cout <<„Elemente prezente în stivă :”; //printează toate elementele din stivă: in timp ce(!este gol(rădăcină)) { // imprimă elementul superior în stivă cout << arunca o privire(rădăcină) <<' '; // elimină elementul superior din stivă pop(&rădăcină); } întoarcere 0; } // Acesta este codul contribuit de rathbhupendraC

// C program for linked list implementation of stack #include  #include  #include  // A structure to represent a stack struct StackNode {  int data;  struct StackNode* next; }; struct StackNode* newNode(int data) {  struct StackNode* stackNode =   (struct StackNode*)  malloc(sizeof(struct StackNode));  stackNode->date = date;  stackNode->next = NULL;  returnează stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int date) { struct StackNode* stackNode = newNode(date);  stackNode->next = *rădăcină;  *rădăcină = stackNode;  printf('%d împins în stivă
', date); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *rădăcină;  *rădăcină = (*rădăcină)->next;  int popped = temp->data;  liber(temp);  revenirea a apărut; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  returnează rădăcină->date; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d a apărut din stivă
', pop(&root));  printf('Elementul de sus este %d
', peek(root));  întoarce 0; }>>>Java

Piton

# Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>

C#

// C# Code for Linked List Implementation using System; public class StackAsLinkedList {  StackNode root;  public class StackNode {  public int data;  public StackNode next;  public StackNode(int data) { this.data = data; }  }  public bool isEmpty()  {  if (root == null) {  return true;  }  else  return false;  }  public void push(int data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  Console.WriteLine(data + ' pushed to stack');  }  public int pop()  {  int popped = int.MinValue;  if (root == null) {  Console.WriteLine('Stack is Empty');  }  else {  popped = root.data;  root = root.next;  }  return popped;  }  public int peek()  {  if (root == null) {  Console.WriteLine('Stack is empty');  return int.MinValue;  }  else {  return root.data;  }  }  // Driver code  public static void Main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  Console.WriteLine(sll.pop() + ' popped from stack');  Console.WriteLine('Top element is ' + sll.peek());  } } /* This code contributed by PrinciRaj1992 */>

Javascript

>>>  
  Ieșire      Avantajele implementării listei conectate:    
 
Implementarea listelor legate a unei stive poate crește și micșora în funcție de nevoile din timpul execuției.
Este folosit în multe mașini virtuale precum JVM.
    Dezavantajele implementării listei conectate:    
 
Necesită memorie suplimentară datorită implicării indicatorilor.
Accesarea aleatorie nu este posibilă în stivă.

Analiza complexității operațiunilor pe structura datelor stivei:

Avantajele Stivei Structură de date :

• Simplitate: Stivele sunt o structură de date simplă și ușor de înțeles, ceea ce le face potrivite pentru o gamă largă de aplicații.
• Eficienţă: Operațiile de împingere și pop pe o stivă pot fi efectuate în timp constant (O(1)) , oferind acces eficient la date.
• Ultimul intrat, primul ieşit (LIFO): Stivele urmează principiul LIFO, asigurându-se că ultimul element adăugat în stivă este primul eliminat. Acest comportament este util în multe scenarii, cum ar fi apelurile de funcții și evaluarea expresiilor.
• Utilizare limitată a memoriei: Stivele trebuie doar să stocheze elementele care au fost împinse pe ele, făcându-le eficiente din punct de vedere al memoriei în comparație cu alte structuri de date.

Dezavantajele Stivei Structură de date :

• Acces limitat: Elementele dintr-o stivă pot fi accesate doar din partea de sus, ceea ce face dificilă recuperarea sau modificarea elementelor din mijlocul stivei.
• Potențial de depășire: Dacă sunt introduse într-o stivă mai multe elemente decât poate reține, va apărea o eroare de depășire, care va duce la pierderea datelor.
• Nu este potrivit pentru acces aleatoriu: Grămadă s nu permit accesul aleatoriu la elemente, ceea ce le face nepotrivite pentru aplicațiile în care elementele trebuie accesate într-o anumită ordine.
• Capacitate limitata: Stivele au o capacitate fixă, ceea ce poate fi o limitare dacă numărul de elemente care trebuie stocate este necunoscut sau foarte variabil.

Aplicații ale structurii de date stive:

• Infix la Postfix /Conversie prefix
• Funcții de refacere-anulare în multe locuri, cum ar fi editori, Photoshop.
• Funcții înainte și înapoi în browserele web
• În gestionarea memoriei, orice computer modern folosește o stivă ca management principal pentru un scop de rulare. Fiecare program care rulează într-un sistem informatic are propriile alocări de memorie.
• Stack ajută, de asemenea, la implementarea apelului de funcție în computere. Ultima funcție apelată este întotdeauna finalizată prima.

Articole similare: