Struttura dei dati dello stack è un struttura dati lineare quello segue Principio LIFO (Last In First Out). , quindi l'ultimo elemento inserito è il primo ad essere estratto. In questo articolo tratteremo tutte le nozioni di base sullo Stack, le Operazioni sullo Stack, la sua implementazione, i vantaggi, gli svantaggi che ti aiuteranno a risolvere tutti i problemi basati sullo Stack.

Tabella dei contenuti

• Cos'è la struttura dei dati dello stack?
• Operazioni di base sulla struttura dei dati dello stack
• isEmpty Operazione nella struttura dei dati dello stack
• Implementazione della struttura dei dati dello stack utilizzando l'elenco collegato
• Analisi della complessità delle operazioni sulla struttura dei dati dello stack
• Vantaggi della struttura dei dati dello stack
• Svantaggi della struttura dei dati dello stack
• Applicazioni della struttura dei dati dello stack

Cos'è la struttura dei dati dello stack?

Pila è un struttura dati lineare basato su Principio LIFO (Last In First Out). in cui l'inserimento di un nuovo elemento e la rimozione di un elemento esistente avviene alla stessa estremità rappresentata come superiore della pila.

Per implementare lo stack, è necessario mantenere il file puntatore alla cima dello stack , che è l'ultimo elemento da inserire perché possiamo accedere agli elementi solo in cima allo stack.

Rappresentazione della struttura dei dati dello stack:

Lo stack segue il principio LIFO (Last In First Out), quindi l'elemento che viene spinto per ultimo viene estratto per primo.

Pila di dimensioni fisse : Come suggerisce il nome, uno stack a dimensione fissa ha una dimensione fissa e non può crescere o ridursi dinamicamente. Se lo stack è pieno e si tenta di aggiungervi un elemento, si verifica un errore di overflow. Se lo stack è vuoto e si tenta di rimuovere un elemento da esso, si verifica un errore di underflow.

Stack di dimensioni dinamiche : uno stack di dimensioni dinamiche può aumentare o ridursi in modo dinamico. Quando la pila è piena, aumenta automaticamente le sue dimensioni per accogliere il nuovo elemento e quando la pila è vuota, diminuisce le sue dimensioni. Questo tipo di stack viene implementato utilizzando un elenco collegato, poiché consente un facile ridimensionamento dello stack.

Operazioni di base sullo stack Struttura dati :

Per effettuare manipolazioni nello stack, ci vengono fornite alcune operazioni.

aggiunta di stringhe

• spingere() per inserire un elemento nello stack
• pop() per rimuovere un elemento dallo stack
• superiore() Restituisce l'elemento superiore dello stack.
• è vuoto() restituisce vero se lo stack è vuoto altrimenti falso.
• è pieno() restituisce vero se lo stack è pieno altrimenti falso.

Algoritmo per l'operazione Push:

• Prima di spingere l'elemento nello stack, controlliamo se lo stack lo è pieno .
• Se lo stack è pieno (in alto == capacità-1) , Poi Overflow dello stack e non possiamo inserire l'elemento nello stack.
• Altrimenti incrementiamo il valore di top di 1 (in alto = in alto + 1) e il nuovo valore viene inserito in posizione superiore .
• Gli elementi possono essere spinti nella pila fino a raggiungere il file capacità della pila.

Condizione di sottoflusso.

Algoritmo per il funzionamento Pop:

• Prima di estrarre l'elemento dallo stack, controlliamo se lo stack lo è vuoto .
• Se lo stack è vuoto (in alto == -1), allora Stack Underflow e non possiamo rimuovere alcun elemento dallo stack.
• Altrimenti, memorizziamo il valore in top, decrementiamo il valore di top di 1 (in alto = in alto – 1) e restituire il valore massimo memorizzato.

Algoritmo per il funzionamento dall'alto:

• Prima di restituire l'elemento in cima allo stack, controlliamo se lo stack è vuoto.
• Se lo stack è vuoto (in alto == -1), stampiamo semplicemente Stack is vuoto.
• Altrimenti, restituiamo l'elemento memorizzato in indice = superiore .

Algoritmo per l'operazione isEmpty :

• Controlla il valore di superiore in pila.
• Se (in alto == -1) , allora lo stack è vuoto quindi ritorna VERO .
• Altrimenti, lo stack non è vuoto, quindi ritorna falso .

Algoritmo per l'operazione isFull:

• Controlla il valore di superiore in pila.
• Se (in alto == capacità-1), allora lo stack è pieno quindi ritorna VERO .
• Altrimenti, lo stack non è pieno, quindi ritorna falso .

Implementazione dello Stack Struttura dati :

Le operazioni di base che possono essere eseguite su uno stack includono push, pop e peek. Esistono due modi per implementare uno stack:

• Utilizzando Array
• Utilizzo dell'elenco collegato

In un'implementazione basata su array, l'operazione push viene implementata incrementando l'indice dell'elemento superiore e memorizzando il nuovo elemento in quell'indice. L'operazione pop viene implementata restituendo il valore memorizzato nell'indice superiore e quindi decrementando l'indice dell'elemento superiore.

maledetto sonno

In un'implementazione basata su elenchi collegati, l'operazione push viene implementata creando un nuovo nodo con il nuovo elemento e impostando il puntatore successivo del nodo superiore corrente sul nuovo nodo. L'operazione pop viene implementata impostando il puntatore successivo del nodo superiore corrente sul nodo successivo e restituendo il valore del nodo superiore corrente.

/* Programma C++ per implementare lo stack di base operazioni */ #includere #includere utilizzando spazio dei nomi standard; #definisci MAX 1000 classe Pila { int superiore; pubblico: int UN[MASSIMO]; // Dimensione massima dello stack Pila() { superiore = -1; } bool spingere(int X); int pop(); int sbirciare(); bool è vuoto(); }; bool Impila::spingi(int X) { Se (superiore >= (MASSIMO - 1)) { cout << 'pila=''overflow'<='' span=''>; ritorno falso; } altro { UN[++superiore] = X; cout << X << ' inserito nello stackN'; ritorno VERO; } } int Pila::pop() { Se (superiore < 0) { cout << 'Stack Underflow'; ritorno 0; } altro { int X = UN[superiore--]; ritorno X; } } int Pila::sbirciatina() { Se (superiore < 0) { cout << 'La pila è vuota'; ritorno 0; } altro { int X = UN[superiore]; ritorno X; } } bool Pila::èVuoto() { ritorno (superiore < 0); } // Programma driver per testare le funzioni di cui sopra int principale() { classe Pila S; S.spingere(10); S.spingere(venti); S.spingere(30); cout << S.pop() << ' Spuntato dallo stackN'; //stampa l'elemento superiore dello stack dopo averlo spuntato cout << 'L'elemento superiore è: ' << S.sbirciare() << fine; //stampa tutti gli elementi nello stack: cout <<'Elementi presenti nello stack: '; Mentre(!S.è vuoto()) { // stampa l'elemento in cima allo stack cout << S.sbirciare() <<' '; // rimuove l'elemento in cima allo stack S.pop(); } ritorno 0; } //Il codice è stato modificato da 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->capacità = capacità;  pila->in alto = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  pila di restituzione; } // Lo stack è pieno quando top è uguale all'ultimo indice int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Lo stack è vuoto quando top è uguale a -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funzione per aggiungere un elemento allo stack. Aumenta top di 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = oggetto;  printf('%d inserito nello stack
', elemento); } // Funzione per rimuovere un elemento dallo stack. Diminuisce top di 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // Funzione per restituire la parte superiore dello stack senza rimuoverla int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top]; } // Programma driver per testare le funzioni di cui sopra int main() { struct Stack* stack = createStack(100);  spingere(pila, 10);  spingere(pila, 20);  spingere(pila, 30);  printf('%d estratto dallo stack
', pop(stack));  restituire 0; }>

Giava

/* Java program to implement basic stack operations */ class Stack {  static final int MAX = 1000;  int top;  int a[] = new int[MAX]; // Maximum size of Stack  boolean isEmpty()  {  return (top < 0);  }  Stack()  {  top = -1;  }  boolean push(int x)  {  if (top>= (MAX - 1)) { System.out.println('Stack Overflow');  restituire falso;  } else { a[++top] = x;  System.out.println(x + ' inserito nello stack');  restituisce vero;  } } int pop() { if (top< 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top--];  return x;  }  }  int peek()  {  if (top < 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top];  return x;  }  }    void print(){  for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]);  } } } // Codice driver class Main { public static void main(String args[]) { Stack s = new Stack();  s.push(10);  s.push(20);  s.push(30);  System.out.println(s.pop() + ' Estratto dallo stack');  System.out.println('L'elemento superiore è :' + s.peek());  System.out.print('Elementi presenti nello stack:');  sprint();  } } //Questo codice è stato modificato da Vinay Pandey>

Pitone

# 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');  restituire falso;  } altrimenti { t+=1;  a[t] = x;    console.log(x + ' inserito nello stack ');  restituisce vero;  } } funzione pop() { if (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]);  } } spingi(10);  spingere(20);  spingere(30);  console.log(pop() + ' Estratto dallo stack');  console.log(' L'elemento principale è :' + peek());  console.log(' Elementi presenti nello stack: ');  stampa(); // Questo codice è un contributo di Rajput-Ji>

Produzione

10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10>

Vantaggi dell'implementazione dell'array:

• Facile da implementare.
• La memoria viene salvata poiché i puntatori non sono coinvolti.

Svantaggi dell'implementazione dell'array:

• Non è dinamico, ovvero non cresce e non si riduce a seconda delle esigenze in fase di esecuzione. [Ma in caso di array di dimensioni dinamiche come vettore in C++, elenco in Python, ArrayList in Java, gli stack possono crescere e ridursi anche con l'implementazione dell'array].
• La dimensione totale dello stack deve essere definita in anticipo.

// Programma C++ per l'implementazione dell'elenco collegato dello stack #includere utilizzando spazio dei nomi standard; // Una struttura per rappresentare uno stack classe StackNode { pubblico: int dati; StackNode* Prossimo; }; StackNode* newNode(int dati) { StackNode* stackNode = nuovo StackNode(); stackNode->dati = dati; stackNode->Prossimo = NULLO; ritorno stackNode; } int è vuoto(StackNode* radice) { ritorno !radice; } vuoto spingere(StackNode** radice, int dati) { StackNode* stackNode = newNode(dati); stackNode->Prossimo = *radice; *radice = stackNode; cout << dati << ' spinto='' a='' pila<='' span=''>N'; } int pop(StackNode** radice) { Se (è vuoto(*radice)) ritorno INT_MIN; StackNode* temp = *radice; *radice = (*radice)->Prossimo; int spuntato = temp->dati; gratuito(temp); ritorno spuntato; } int sbirciare(StackNode* radice) { Se (è vuoto(radice)) ritorno INT_MIN; ritorno radice->dati; } // Codice conducente int principale() { StackNode* radice = NULLO; spingere(&radice, 10); spingere(&radice, venti); spingere(&radice, 30); cout << pop(&radice) << ' spuntato dallo stackN'; cout << 'L'elemento superiore è' << sbirciare(radice) << fine; cout <<'Elementi presenti nello stack: '; //stampa tutti gli elementi nello stack: Mentre(!è vuoto(radice)) { // stampa l'elemento in cima allo stack cout << sbirciare(radice) <<' '; // rimuove l'elemento in cima allo stack pop(&radice); } ritorno 0; } // Questo codice è fornito da 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->dati = dati;  stackNode->successivo = NULL;  restituisce stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *root = stackNode;  printf('%d inserito nello stack
', dati); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *root = (*root)->successivo;  int spuntato = temp->data;  libero(temp);  il ritorno è spuntato; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  restituisce root->dati; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d estratto dallo stack
', pop(&root));  printf('L'elemento superiore è %d
', peek(root));  restituire 0; }>

Giava

// Java Code for Linked List Implementation public class StackAsLinkedList {  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 data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  System.out.println(data + ' pushed to stack');  }  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;  }  }  // Driver code  public static void main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());    sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());  } }>

Pitone

# 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

>

Produzione

10 pushed to stack 20 pushed to stack 30 pushed to stack 30 popped from stack Top element is 20 Elements present in stack : 20 10>

Vantaggi dell'implementazione della lista collegata:

• L'implementazione dell'elenco collegato di uno stack può crescere e ridursi in base alle esigenze in fase di esecuzione.
• È utilizzato in molte macchine virtuali come JVM.

Svantaggi dell'implementazione della lista collegata:

• Richiede memoria aggiuntiva a causa del coinvolgimento dei puntatori.
• L'accesso casuale non è possibile nello stack.

Analisi della complessità delle operazioni sulla struttura dei dati dello stack:

Vantaggi dello stack Struttura dati :

• Semplicità: Gli stack sono una struttura dati semplice e di facile comprensione, che li rende adatti a un'ampia gamma di applicazioni.
• Efficienza: Le operazioni push e pop su uno stack possono essere eseguite in tempo costante (O(1)) , fornendo un accesso efficiente ai dati.
• Ultimo entrato, primo uscito (LIFO): Gli stack seguono il principio LIFO, garantendo che l'ultimo elemento aggiunto allo stack sia il primo rimosso. Questo comportamento è utile in molti scenari, ad esempio chiamate di funzioni e valutazione di espressioni.
• Utilizzo della memoria limitato: Gli stack devono solo memorizzare gli elementi che sono stati inseriti su di essi, rendendoli efficienti in termini di memoria rispetto ad altre strutture dati.

Svantaggi dello Stack Struttura dati :

• Accesso limitato: È possibile accedere agli elementi di uno stack solo dall'alto, rendendo difficile il recupero o la modifica degli elementi al centro dello stack.
• Potenziale di overflow: Se in uno stack vengono inseriti più elementi di quanti ne possa contenere, si verificherà un errore di overflow, con conseguente perdita di dati.
• Non adatto per l'accesso casuale: Pila I messaggi non consentono l'accesso casuale agli elementi, rendendoli inadatti per applicazioni in cui è necessario accedere agli elementi in un ordine specifico.
• Capacità limitata: Le pile hanno una capacità fissa, il che può rappresentare un limite se il numero di elementi da immagazzinare è sconosciuto o molto variabile.

Applicazioni della struttura dei dati dello stack:

• Da infisso a suffisso /Conversione del prefisso
• Funzionalità di ripristino in molti posti come editor, Photoshop.
• Funzionalità avanti e indietro nei browser web
• Nella gestione della memoria, qualsiasi computer moderno utilizza uno stack come gestione primaria per uno scopo di esecuzione. Ogni programma in esecuzione in un sistema informatico ha le proprie allocazioni di memoria.
• Stack aiuta anche a implementare la chiamata di funzione nei computer. L'ultima funzione chiamata viene sempre completata per prima.

Articoli Correlati:

• Implementa uno stack utilizzando un elenco collegato singolarmente
• Operazioni di base nella struttura dei dati dello stack con implementazioni
• I 50 principali problemi sulla struttura dei dati dello stack richiesti nelle interviste SDE
• Applicazioni, vantaggi e svantaggi dello Stack
  
• Stack per la programmazione competitiva