Estructura de datos de pila es un estructura de datos lineal que sigue Principio LIFO (último en entrar, primero en salir) , por lo que el último elemento insertado es el primero en salir. En este artículo, cubriremos todos los conceptos básicos de Stack, Operaciones en Stack, su implementación, ventajas y desventajas que lo ayudarán a resolver todos los problemas basados ​​en Stack.

Tabla de contenidos

• ¿Qué es la estructura de datos de la pila?
• Operaciones básicas en la estructura de datos de la pila
• Operación isEmpty en la estructura de datos de la pila
• Implementación de la estructura de datos de la pila mediante lista vinculada
• Análisis de complejidad de operaciones en la estructura de datos de la pila
• Ventajas de la estructura de datos de la pila
• Desventajas de la estructura de datos de la pila
• Aplicaciones de la estructura de datos de la pila

¿Qué es la estructura de datos de la pila?

Pila es un estructura de datos lineal Residencia en Principio LIFO (último en entrar, primero en salir) en el que la inserción de un nuevo elemento y la eliminación de un elemento existente se realiza en el mismo extremo representado como el arriba de la pila.

Para implementar la pila, se requiere mantener el puntero a la parte superior de la pila , que es el último elemento que se insertará porque Podemos acceder a los elementos solo en la parte superior de la pila.

Representación de la estructura de datos de la pila:

La pila sigue el principio LIFO (último en entrar, primero en salir), por lo que el elemento que se empuja en último lugar aparece primero.

Pila de tamaño fijo : Como sugiere el nombre, una pila de tamaño fijo tiene un tamaño fijo y no puede crecer ni reducirse dinámicamente. Si la pila está llena y se intenta agregarle un elemento, se produce un error de desbordamiento. Si la pila está vacía y se intenta eliminar un elemento de ella, se produce un error de desbordamiento insuficiente.

Pila de tamaño dinámico : Una pila de tamaño dinámico puede crecer o reducirse dinámicamente. Cuando la pila está llena, automáticamente aumenta su tamaño para acomodar el nuevo elemento, y cuando la pila está vacía, disminuye su tamaño. Este tipo de pila se implementa mediante una lista vinculada, ya que permite cambiar fácilmente el tamaño de la pila.

Operaciones básicas en pila Estructura de datos :

Para realizar manipulaciones en una pila, se nos proporcionan ciertas operaciones.

cómo convertir una cadena a un número entero

• empujar() para insertar un elemento en la pila
• estallido() para eliminar un elemento de la pila
• arriba() Devuelve el elemento superior de la pila.
• esta vacio() devuelve verdadero si la pila está vacía; de lo contrario, es falso.
• está lleno() devuelve verdadero si la pila está llena; de lo contrario, es falso.

Algoritmo para operación de empuje:

• Antes de empujar el elemento a la pila, verificamos si la pila está lleno .
• Si la pila está llena (arriba == capacidad-1) , entonces Desbordamientos de pila y no podemos insertar el elemento en la pila.
• De lo contrario, incrementamos el valor de top en 1. (arriba = arriba + 1) y el nuevo valor se inserta en posición superior .
• Los elementos se pueden empujar hacia la pila hasta llegar al capacidad de la pila.

Algoritmo para operación pop:

• Antes de sacar el elemento de la pila, verificamos si la pila está vacío .
• Si la pila está vacía (arriba == -1), entonces Desbordamientos de pila y no podemos eliminar ningún elemento de la pila.
• De lo contrario, almacenamos el valor en la parte superior, disminuimos el valor de la parte superior en 1 (arriba = arriba – 1) y devolver el valor superior almacenado.

Algoritmo para operación superior:

• Antes de devolver el elemento superior de la pila, verificamos si la pila está vacía.
• Si la pila está vacía (arriba == -1), simplemente imprimimos La pila está vacía.
• De lo contrario, devolvemos el elemento almacenado en índice = arriba .

Algoritmo para la operación isEmpty :

• Comprueba el valor de arriba en pila.
• Si (arriba == -1) , entonces la pila es vacío así que regresa verdadero .
• De lo contrario, la pila no está vacía así que regresa FALSO .

Algoritmo para operación isFull:

cómo devolver una matriz java

• Comprueba el valor de arriba en pila.
• Si (arriba == capacidad-1), entonces la pila es lleno así que regresa verdadero .
• De lo contrario, la pila no está llena así que regresa FALSO .

Implementación de pila Estructura de datos :

Las operaciones básicas que se pueden realizar en una pila incluyen empujar, hacer estallar y mirar. Hay dos formas de implementar una pila:

• Usando matriz
• Usando la lista enlazada

En una implementación basada en matrices, la operación de inserción se implementa incrementando el índice del elemento superior y almacenando el nuevo elemento en ese índice. La operación pop se implementa devolviendo el valor almacenado en el índice superior y luego disminuyendo el índice del elemento superior.

En una implementación basada en lista vinculada, la operación de inserción se implementa creando un nuevo nodo con el nuevo elemento y estableciendo el siguiente puntero del nodo superior actual en el nuevo nodo. La operación pop se implementa estableciendo el siguiente puntero del nodo superior actual en el siguiente nodo y devolviendo el valor del nodo superior actual.

/* Programa C++ para implementar la pila básica operaciones */ #incluir #incluir usando espacio de nombres enfermedad de transmisión sexual; #definir MAX 1000 clase Pila { En t arriba; público: En t a[MÁXIMO]; // Tamaño máximo de pila Pila() { arriba = -1; } booleano empujar(En t X); En t estallido(); En t ojeada(); booleano esta vacio(); }; booleano Pila::empujar(En t X) { si (arriba >= (MÁXIMO - 1)) { corte << ' pila = '' desbordamiento'<='' span=''>; devolver FALSO; } demás { a[++arriba] = X; corte << X << 'empujado a la pila orte'; devolver verdadero; } } En t Pila::pop() { si (arriba < 0) { corte << 'Desbordamiento insuficiente de pila'; devolver 0; } demás { En t X = a[arriba--]; devolver X; } } En t Pila::mirar() { si (arriba < 0) { corte << 'La pila está vacía'; devolver 0; } demás { En t X = a[arriba]; devolver X; } } booleano Pila::está vacía() { devolver (arriba < 0); } // Programa controlador para probar las funciones anteriores En t principal() { clase Pila s; s.empujar(10); s.empujar(20); s.empujar(30); corte << s.estallido() << 'Salido de la pila orte'; //imprime el elemento superior de la pila después de hacer estallar corte << 'El elemento superior es: ' << s.ojeada() << fin; //imprime todos los elementos en la pila: corte <<'Elementos presentes en la pila: '; mientras(!s.esta vacio()) { // imprime el elemento superior en la pila corte << s.ojeada() <<' '; // eliminar el elemento superior de la pila s.estallido(); } devolver 0; } //El código es modificado por 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->capacidad = capacidad;  pila->arriba = -1;  pila->matriz = (int*)malloc(pila->capacidad * tamaño de(int));  pila de retorno; } // La pila está llena cuando la parte superior es igual al último índice int isFull(struct Stack* stack) { return pila->top == pila->capacidad - 1; } // La pila está vacía cuando la parte superior es igual a -1 int isEmpty(struct Stack* stack) { return pila->top == -1; } // Función para agregar un elemento a la pila. Aumenta la parte superior en 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  pila->matriz[++pila->arriba] = elemento;  printf('%d empujado a la pila
', elemento); } // Función para eliminar un elemento de la pila. Disminuye la parte superior en 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  devolver pila->matriz[pila->arriba--]; } // Función para devolver la parte superior de la pila sin eliminarla int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  devolver pila->matriz[pila->arriba]; } // Programa controlador para probar las funciones anteriores int main() { struct Stack* stack = createStack(100);  empujar(pila, 10);  empujar(pila, 20);  empujar(pila, 30);  printf('%d extraído de la pila
', pop(pila));  devolver 0; }>

Java

/* 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('Desbordamiento de pila');  falso retorno;  } más { a[++arriba] = x;  System.out.println(x + ' empujado a la pila');  devolver verdadero;  } } int pop() { si (arriba< 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]);  } } } // Clase de código de controlador 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() + ' Sacado de la pila');  System.out.println('El elemento superior es:' + s.peek());  System.out.print('Elementos presentes en la pila:');  pique();  } } //Este código fue modificado por Vinay Pandey>

Pitón

# 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');  falso retorno;  } más { t+=1;  a[t] = x;    console.log(x + ' empujado a la pila ');  devolver verdadero;  } } función 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]);  } } empujar(10);  empujar(20);  empujar(30);  console.log(pop() + ' Sacado de la pila');  console.log(' El elemento superior es :' + peek());  console.log(' Elementos presentes en la pila: ');  imprimir(); // Este código es una contribución de Rajput-Ji>

Producción

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>

Ventajas de la implementación de matrices:

• Fácil de implementar.
• La memoria se guarda ya que no intervienen punteros.

Desventajas de la implementación de matrices:

• No es dinámico, es decir, no crece ni se reduce según las necesidades en tiempo de ejecución. [Pero en el caso de matrices de tamaño dinámico como vector en C++, lista en Python, ArrayList en Java, las pilas también pueden crecer y reducirse con la implementación de matrices].
• El tamaño total de la pila debe definirse de antemano.

// Programa C++ para implementación de lista enlazada de pila #incluir usando espacio de nombres enfermedad de transmisión sexual; // Una estructura para representar una pila clase Nodo de pila { público: En t datos; Nodo de pila* próximo; }; Nodo de pila* nuevoNodo(En t datos) { Nodo de pila* pilaNodo = nuevo Nodo de pila(); pilaNodo->datos = datos; pilaNodo->próximo = NULO; devolver pilaNodo; } En t esta vacio(Nodo de pila* raíz) { devolver !raíz; } vacío empujar(Nodo de pila** raíz, En t datos) { Nodo de pila* pilaNodo = nuevoNodo(datos); pilaNodo->próximo = *raíz; *raíz = pilaNodo; corte << datos << 'empujado='' a='' pila<='' span=''> orte'; } En t estallido(Nodo de pila** raíz) { si (esta vacio(*raíz)) devolver INT_MIN; Nodo de pila* temperatura = *raíz; *raíz = (*raíz)->próximo; En t apareció = temperatura->datos; gratis(temperatura); devolver apareció; } En t ojeada(Nodo de pila* raíz) { si (esta vacio(raíz)) devolver INT_MIN; devolver raíz->datos; } // código de controlador En t principal() { Nodo de pila* raíz = NULO; empujar(&raíz, 10); empujar(&raíz, 20); empujar(&raíz, 30); corte << estallido(&raíz) << ' saltó de la pila orte'; corte << 'El elemento superior es ' << ojeada(raíz) << fin; corte <<'Elementos presentes en la pila: '; //imprime todos los elementos en la pila: mientras(!esta vacio(raíz)) { // imprime el elemento superior en la pila corte << ojeada(raíz) <<' '; // eliminar el elemento superior de la pila estallido(&raíz); } devolver 0; } // Este es el código aportado por 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->datos = datos;  stackNode->siguiente = NULL;  devolver nodo de pila; } int isEmpty(struct StackNode* raíz) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->siguiente = *root;  *raíz = nodopila;  printf('%d empujado a la pila
', datos); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  estructura StackNode* temp = *root;  *raíz = (*raíz)->siguiente;  int apareció = temp->datos;  libre (temporal);  el retorno apareció; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  devolver raíz->datos; } int main() { estructura StackNode* raíz = NULL;  empujar(&raíz, 10);  empujar(&raíz, 20);  empujar(&raíz, 30);  printf('%d extraído de la pila
', pop(&root));  printf('El elemento superior es %d
', peek(raíz));  devolver 0; }>

Java

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

Pitón

# 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

>

Producción

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>

Ventajas de la implementación de la lista enlazada:

• La implementación de la lista vinculada de una pila puede crecer y reducirse según las necesidades en tiempo de ejecución.
• Se utiliza en muchas máquinas virtuales como JVM.

Desventajas de la implementación de listas enlazadas:

• Requiere memoria adicional debido a la participación de punteros.
• El acceso aleatorio no es posible en la pila.

Análisis de complejidad de operaciones en la estructura de datos de la pila:

Ventajas de la pila Estructura de datos :

• Sencillez: Las pilas son una estructura de datos simple y fácil de entender, lo que las hace adecuadas para una amplia gama de aplicaciones.
• Eficiencia: Las operaciones push y pop en una pila se pueden realizar en tiempo constante (O(1)) , proporcionando un acceso eficiente a los datos.
• Último en entrar, primero en salir (LIFO): Las pilas siguen el principio LIFO, asegurando que el último elemento agregado a la pila sea el primero en eliminarse. Este comportamiento es útil en muchos escenarios, como llamadas a funciones y evaluación de expresiones.
• Uso de memoria limitado: Las pilas solo necesitan almacenar los elementos que se les han insertado, lo que las hace eficientes en memoria en comparación con otras estructuras de datos.

Desventajas de la pila Estructura de datos :

• Acceso limitado: Solo se puede acceder a los elementos de una pila desde la parte superior, lo que dificulta recuperar o modificar elementos en el medio de la pila.
• Potencial de desbordamiento: Si se colocan en una pila más elementos de los que puede contener, se producirá un error de desbordamiento que provocará una pérdida de datos.
• No apto para acceso aleatorio: Pila Los s no permiten el acceso aleatorio a elementos, lo que los hace inadecuados para aplicaciones en las que es necesario acceder a los elementos en un orden específico.
• Capacidad limitada: Las pilas tienen una capacidad fija, lo que puede ser una limitación si el número de elementos que se deben almacenar es desconocido o muy variable.

Aplicaciones de la estructura de datos de la pila:

• Infijo a posfijo /Conversión de prefijo
• Funciones de rehacer y deshacer en muchos lugares, como editores y Photoshop.
• Funciones de avance y retroceso en navegadores web
• En la administración de memoria, cualquier computadora moderna utiliza una pila como administración principal para fines de ejecución. Cada programa que se ejecuta en un sistema informático tiene sus propias asignaciones de memoria.
• Stack también ayuda a implementar llamadas a funciones en las computadoras. La última función llamada siempre se completa primero.

Artículos relacionados:

• Implementar una pila usando una lista enlazada individualmente
• Operaciones básicas en estructura de datos de pila con implementaciones
• Los 50 problemas principales sobre la estructura de datos de la pila planteados en las entrevistas SDE
• Aplicaciones, ventajas y desventajas de Stack
  
• Pila para programación competitiva