Estructura de dades de pila és un estructura de dades lineal que segueix Principi LIFO (últim en entrar, primer en sortir). , de manera que l'últim element inserit és el primer que apareix. En aquest article, tractarem tots els conceptes bàsics de Stack, Operacions a Stack, la seva implementació, avantatges, inconvenients que us ajudaran a resoldre tots els problemes basats en Stack.

Taula de contingut

• Què és l'estructura de dades de la pila?
• Operacions bàsiques sobre l'estructura de dades de la pila
• Operació isEmpty a l'estructura de dades de la pila
• Implementació de l'estructura de dades de pila mitjançant la llista enllaçada
• Anàlisi de complexitat d'operacions sobre l'estructura de dades de pila
• Avantatges de l'estructura de dades de pila
• Desavantatges de l'estructura de dades de pila
• Aplicacions de Stack Data Structure

Què és l'estructura de dades de la pila?

Pila és un estructura de dades lineal basat en Principi LIFO (últim en entrar, primer en sortir). en què la inserció d'un nou element i l'eliminació d'un element existent té lloc al mateix extrem representat que el superior de la pila.

Per implementar la pila, cal mantenir el punter a la part superior de la pila , que és l'últim element a inserir perquè només podem accedir als elements a la part superior de la pila.







Representació de l'estructura de dades de la pila:

La pila segueix el principi LIFO (Last In First Out) de manera que l'element que s'empènyer darrer apareix primer.

• Pila de mida fixa : Com el seu nom indica, una pila de mida fixa té una mida fixa i no pot créixer ni reduir-se dinàmicament. Si la pila està plena i s'intenta afegir-hi un element, es produeix un error de desbordament. Si la pila està buida i s'intenta eliminar-ne un element, es produeix un error de desbordament.
• Pila de mida dinàmica : una pila de mida dinàmica pot créixer o reduir-se dinàmicament. Quan la pila està plena, augmenta automàticament la seva mida per acomodar el nou element, i quan la pila està buida, disminueix la seva mida. Aquest tipus de pila s'implementa mitjançant una llista enllaçada, ja que permet redimensionar fàcilment la pila.

Operacions bàsiques a la pila Estructura de dades :

Per fer manipulacions en una pila, hi ha determinades operacions que ens proporcionen.

"Quina diferència hi ha entre un lleó i un tigre"

• empènyer () per inserir un element a la pila
• pop() per eliminar un element de la pila
• superior() Retorna l'element superior de la pila.
• està buit() retorna true si la pila està buida, sinó false.
• està ple() retorna true si la pila està plena, sinó false.

Algorisme per a l'operació push:

• Abans d'empènyer l'element a la pila, comprovem si la pila és ple .
• Si la pila està plena (superior == capacitat-1) , doncs Desbordaments de pila i no podem inserir l'element a la pila.
• En cas contrari, incrementem el valor de top en 1 (a dalt = a dalt + 1) i el nou valor s'insereix a posició superior .
• Els elements es poden empènyer a la pila fins que arribem capacitat de la pila.

Condició de baix nivell.

Algorisme per a l'operació pop:

• Abans de treure l'element de la pila, comprovem si la pila és buit .
• Si la pila està buida (superior == -1), aleshores Desbordaments de pila i no podem eliminar cap element de la pila.
• En cas contrari, emmagatzemem el valor a la part superior, disminuïm el valor de la part superior en 1 (a dalt = a dalt – 1) i retorna el valor màxim emmagatzemat.

Algoritme per a l'operació superior:

• Abans de tornar l'element superior de la pila, comprovem si la pila està buida.
• Si la pila està buida (superior == -1), simplement imprimim Stack is empty.
• En cas contrari, retornem l'element emmagatzemat a índex = superior .

Algorisme per a l'operació isEmpty :

• Comproveu el valor de superior en pila.
• Si (superior == -1) , llavors la pila és buit doncs torna veritat .
• En cas contrari, la pila no està buida, així que torna fals .

Algoritme per a isFull Operation:

• Comproveu el valor de superior a la pila.
• Si (superior == capacitat-1), llavors la pila és ple doncs torna veritat .
• En cas contrari, la pila no està plena, així que torna fals .

Implementació de Stack Estructura de dades :

Les operacions bàsiques que es poden realitzar en una pila inclouen push, pop i peek. Hi ha dues maneres d'implementar una pila:

• Utilitzant Array
• Ús de la llista enllaçada

En una implementació basada en matrius, l'operació push s'implementa augmentant l'índex de l'element superior i emmagatzemant el nou element en aquest índex. L'operació pop s'implementa retornant el valor emmagatzemat a l'índex superior i després disminuint l'índex de l'element superior.

En una implementació basada en llistes enllaçades, l'operació push s'implementa creant un nou node amb el nou element i establint el següent punter del node superior actual al nou node. L'operació pop s'implementa posant el punter següent del node superior actual al node següent i retornant el valor del node superior actual.

/* Programa C++ per implementar la pila bàsica operacions */ #incloure #incloure utilitzant espai de noms std; #definir MAX 1000 classe Pila { int superior; públic: int a[MAX]; // Mida màxima de la pila Pila() { superior = -1; } bool empènyer(int x); int pop(); int ullada(); bool està buit(); }; bool Stack:: push(int x) { si (superior >= (MAX - 1)) { cout << 'pila='' desbordament'<='' span=''>; tornar fals; } altra cosa { a[++superior] = x; cout << x << 'empès a la pila '; tornar veritat; } } int Stack::pop() { si (superior < 0) { cout << 'Stack Underflow'; tornar 0; } altra cosa { int x = a[superior--]; tornar x; } } int Stack::peek() { si (superior < 0) { cout << 'La pila està buida'; tornar 0; } altra cosa { int x = a[superior]; tornar x; } } bool Stack::isEmpty() { tornar (superior < 0); } // Programa de controlador per provar les funcions anteriors int principal() { classe Pila s; s.empènyer(10); s.empènyer(20); s.empènyer(30); cout << s.pop() << ' Va sortir de la pila '; //imprimeix l'element superior de la pila després de sortir cout << 'L'element superior és:' << s.ullada() << endl; //imprimeix tots els elements de la pila: cout <<'Elements presents a la pila :'; mentre(!s.està buit()) { // imprimeix l'element superior a la pila cout << s.ullada() <<' '; // elimina l'element superior de la pila s.pop(); } tornar 0; } //El codi està modificat per 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->capacitat = capacitat;  pila->superior = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  pila de retorn; } // La pila està plena quan la part superior és igual a l'últim índex int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // La pila està buida quan la part superior és igual a -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funció per afegir un element a la pila. Augmenta la part superior en 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = element;  printf('%d empès a la pila
', element); } // Funció per eliminar un element de la pila. Disminueix la part superior en 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  retornar pila->matriu[pila->superior--]; } // Funció per tornar la part superior de la pila sense eliminar-la int peek(struct Stack* stack) { if (isEmpty(pila)) return INT_MIN;  retornar pila->matriu[pila->part superior]; } // Programa controlador per provar les funcions anteriors int main() { struct Stack* stack = createStack(100);  push(pila, 10);  empènyer (pila, 20);  empènyer (pila, 30);  printf('%d ha sortit de la pila
', pop(pila));  retorn 0; }>>>Java-1;i--){ System.out.print(' '+ a[i]);  } } } // Classe de codi del controlador Main { public static void main(String args[]) { Stack s = new Stack();  s.empènyer(10);  s.empènyer(20);  s.empènyer(30);  System.out.println(s.pop() + ' Ha sortit de la pila');  System.out.println('L'element superior és:' + s.peek());  System.out.print('Elements presents a la pila :');  s.print();  } } //Aquest codi ha estat modificat per Vinay Pandey>

Python

# 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');  retornar fals;  } else { t+=1;  a[t] = x;    console.log(x + ' empès a la pila ');  retornar veritat;  } } funció pop() { si (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);  empenta (20);  empenta (30);  console.log(pop() + 'Ha sortit de la pila');  console.log(' L'element superior és :' + peek());  console.log(' Elements presents a la pila: ');  imprimir(); // Aquest codi és aportat per Rajput-Ji>>>  
  Sortida  
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>
  
    Avantatges de la implementació de matrius:    
 
Fàcil d'implementar.
La memòria es desa perquè els punters no intervenen.
    Desavantatges de la implementació de matrius:    
 
No és dinàmic, és a dir, no creix ni es redueix en funció de les necessitats en temps d'execució. [Però en el cas de matrius de mida dinàmica com el vector en C++, llista a Python, ArrayList a Java, les piles també poden créixer i reduir-se amb la implementació de matrius].
La mida total de la pila s'ha de definir prèviament.

// Programa C++ per a la implementació de llistes enllaçades de la pila #incloure utilitzant espai de noms std; // Una estructura per representar una pila classe StackNode { públic: int dades; StackNode* Pròxim; }; StackNode* nouNode(int dades) { StackNode* stackNode = nou StackNode(); stackNode->dades = dades; stackNode->Pròxim = NUL; tornar stackNode; } int està buit(StackNode* arrel) { tornar !arrel; } buit empènyer(StackNode** arrel, int dades) { StackNode* stackNode = nouNode(dades); stackNode->Pròxim = *arrel; *arrel = stackNode; cout << dades << 'pused='' to='' stack<='' span=''> '; } int pop(StackNode** arrel) { si (està buit(*arrel)) tornar INT_MIN; StackNode* temp = *arrel; *arrel = (*arrel)->Pròxim; int va esclatar = temp->dades; lliure(temp); tornar va esclatar; } int ullada(StackNode* arrel) { si (està buit(arrel)) tornar INT_MIN; tornar arrel->dades; } // Codi del conductor int principal() { StackNode* arrel = NUL; empènyer(&arrel, 10); empènyer(&arrel, 20); empènyer(&arrel, 30); cout << pop(&arrel) << ' va sortir de la pila '; cout << 'L'element superior és' << ullada(arrel) << endl; cout <<'Elements presents a la pila :'; //imprimeix tots els elements de la pila: mentre(!està buit(arrel)) { // imprimeix l'element superior a la pila cout << ullada(arrel) <<' '; // elimina l'element superior de la pila pop(&arrel); } tornar 0; } // Aquest codi és aportat per 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->dades = dades;  stackNode->next = NULL;  retorna stackNode; } int és buit(struct StackNode* arrel) { retorn !arrel; } void push(struct StackNode** arrel, int dades) { struct StackNode* stackNode = nouNode (dades);  stackNode->next = *arrel;  * arrel = stackNode;  printf('%d empès a la pila
', dades); } int pop(struct StackNode** arrel) { if (isEmpty(*arrel)) retorna INT_MIN;  struct StackNode* temp = *arrel;  *arrel = (*arrel)->següent;  int esclatat = temp->dades;  lliure (temp);  retorn va aparèixer; } int peek(struct StackNode* arrel) { if (isEmpty(arrel)) retorna INT_MIN;  retornar arrel->dades; } int main() { struct StackNode* arrel = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d ha sortit de la pila
', pop(&root));  printf('L'element superior és %d
', peek(arrel));  retorn 0; }>>>Java

Python

# 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

>


Sortida Avantatges de la implementació de la llista enllaçada:

• La implementació de la llista enllaçada d'una pila pot créixer i reduir-se segons les necessitats en temps d'execució.
• S'utilitza en moltes màquines virtuals com JVM.

Desavantatges de la implementació de la llista enllaçada:

• Requereix memòria addicional a causa de la participació dels punters.
• L'accés aleatori no és possible a la pila.

Anàlisi de complexitat de les operacions a l'estructura de dades de la pila:

Operacions	Complexitat temporal	Complexitat espacial
empènyer ()	O(1)	O(1)
pop()	O(1)	O(1) arp-a comanda
superior () o fer pipí k()	O(1)	O(1)
està buit()	O(1)	O(1)
està ple()	O(1)	O(1)

Avantatges de Stack Estructura de dades :

• Senzillesa: Les piles són una estructura de dades senzilla i fàcil d'entendre, la qual cosa les fa adequades per a una àmplia gamma d'aplicacions.
• Eficiència: Les operacions push i pop en una pila es poden realitzar en temps constant (O(1)) , proporcionant un accés eficient a les dades.
• Últim en entrar, primer sortit (LIFO): Les piles segueixen el principi LIFO, assegurant que l'últim element afegit a la pila és el primer que s'elimina. Aquest comportament és útil en molts escenaris, com ara les trucades de funcions i l'avaluació d'expressions.
• Ús limitat de memòria: Les piles només necessiten emmagatzemar els elements que s'han empès a elles, fent-les eficients en la memòria en comparació amb altres estructures de dades.

Inconvenients de Stack Estructura de dades :

• Accés limitat: Només es pot accedir als elements d'una pila des de la part superior, cosa que dificulta la recuperació o la modificació d'elements al centre de la pila.
• Potencial de desbordament: Si s'empenyen més elements a una pila dels que pot contenir, es produirà un error de desbordament, que provocarà una pèrdua de dades.
• No apte per a accés aleatori: Pila s no permeten l'accés aleatori als elements, la qual cosa els fa inadequats per a aplicacions on cal accedir als elements en un ordre específic.
• Aforament limitat: Les piles tenen una capacitat fixa, que pot ser una limitació si el nombre d'elements que cal emmagatzemar és desconegut o molt variable.

Aplicacions de l'estructura de dades de pila:

• Infix a Postfix /Conversió de prefix
• Funcions de refer-desfer en molts llocs com editors, Photoshop.
• Funcions d'avançament i retrocés als navegadors web
• A la gestió de memòria, qualsevol ordinador modern utilitza una pila com a gestió principal per a un propòsit d'execució. Cada programa que s'executa en un sistema informàtic té les seves pròpies assignacions de memòria.
• Stack també ajuda a implementar la crida de funcions als ordinadors. La darrera funció cridada sempre es completa primer.

Articles relacionats:

• Implementeu una pila utilitzant una llista enllaçada individualment
• Operacions bàsiques en l'estructura de dades de pila amb implementacions
• Els 50 principals problemes de l'estructura de dades de la pila es van preguntar a les entrevistes de SDE
• Aplicacions, avantatges i desavantatges de Stack
  
• Stack per a la programació competitiva