in

Estructura de datos de pila (introducción y programa)

gfg 200x200 min

La pila es una estructura de datos lineal que sigue un orden particular en el que se realizan las operaciones. El orden puede ser LIFO (último en entrar, primero en salir) o FILO (primero en entrar, último en salir).

Principalmente se realizan las siguientes tres operaciones básicas en la pila:

  • Empujar: Agrega un elemento a la pila. Si la pila está llena, se dice que es una condición de desbordamiento.
  • Música pop: Elimina un artículo de la pila. Los elementos aparecen en el orden inverso en el que se empujan. Si la pila está vacía, se dice que es una condición de desbordamiento.
  • Peek or Top: Devuelve el elemento superior de la pila.
  • esta vacio: Devuelve verdadero si la pila está vacía, de lo contrario es falso.

stack

¿Cómo entender una pila de forma práctica?
Hay muchos ejemplos reales de una pila. Considere el ejemplo simple de platos apilados uno sobre otro en una cantina. La placa que está en la parte superior es la primera que se retira, es decir, la placa que se ha colocado en la posición más baja permanece en la pila durante el período de tiempo más largo. Entonces, simplemente se puede ver que sigue el orden LIFO / FILO.

Complejidades de tiempo de las operaciones en la pila:

push (), pop (), isEmpty () y peek () toman O (1) tiempo. No ejecutamos ningún bucle en ninguna de estas operaciones.

Aplicaciones de pila:

  • Equilibrio de símbolos
  • Conversión de infijo a sufijo / prefijo
  • Funciones de rehacer y deshacer en muchos lugares como editores, photoshop.
  • Función de avance y retroceso en los navegadores web
  • Se utiliza en muchos algoritmos como Tower of Hanoi, recorridos de árboles, problema de intervalo de existencias, problema de histograma.
  • El retroceso es una de las técnicas de diseño de algoritmos. Algunos ejemplos de retroceso son el problema de Knight-Tour, el problema de N-Queen, encontrar su camino a través de un laberinto y ajedrez o damas similares a un juego en todos estos problemas en los que nos sumergimos de alguna manera, si esa manera no es eficiente, volvemos a lo anterior. estado y entrar en otro camino. Para volver de un estado actual, necesitamos almacenar el estado anterior para ese propósito, necesitamos una pila.
  • En algoritmos de gráficos como clasificación topológica y componentes fuertemente conectados
  • En la administración de memoria, cualquier computadora moderna usa una pila como administración principal para un propósito de ejecución. Cada programa que se ejecuta en un sistema informático tiene sus propias asignaciones de memoria
  • La inversión de cadenas también es otra aplicación de la pila. Aquí, uno por uno, cada personaje se inserta en la pila. Entonces, el primer carácter de la cadena está en la parte inferior de la pila y el último elemento de una cadena está en la parte superior de la pila. Después de realizar las operaciones pop en la pila, obtenemos una cadena en orden inverso.

Implementación:
Hay dos formas de implementar una pila:

  • Usando matriz
  • Usando lista enlazada

Implementando Stack usando Arrays

C ++

   

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000

class Stack {

    int top;

public:

    int a[MAX];

    Stack() { top = -1; }

    bool push(int x);

    int pop();

    int peek();

    bool isEmpty();

};

bool Stack::push(int x)

{

    if (top >= (MAX - 1)) {

        cout << "Stack Overflow";

        return false;

    }

    else {

        a[++top] = x;

        cout << x << " pushed into stackn";

        return true;

    }

}

int Stack::pop()

{

    if (top < 0) {

        cout << "Stack Underflow";

        return 0;

    }

    else {

        int x = a[top--];

        return x;

    }

}

int Stack::peek()

{

    if (top < 0) {

        cout << "Stack is Empty";

        return 0;

    }

    else {

        int x = a[top];

        return x;

    }

}

bool Stack::isEmpty()

{

    return (top < 0);

}

int main()

{

    class Stack s;

    s.push(10);

    s.push(20);

    s.push(30);

    cout << s.pop() << " Popped from stackn";

    

    cout<<"Elements present in stack : ";

    while(!s.isEmpty())

    {

        

        cout<<s.peek()<<" ";

        

        s.pop();

    }

    return 0;

}

C

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

struct Stack {

    int top;

    unsigned capacity;

    int* array;

};

struct Stack* createStack(unsigned capacity)

{

    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

    stack->capacity = capacity;

    stack->top = -1;

    stack->array = (int*)malloc(stack->capacity * sizeof(int));

    return stack;

}

int isFull(struct Stack* stack)

{

    return stack->top == stack->capacity - 1;

}

int isEmpty(struct Stack* stack)

{

    return stack->top == -1;

}

void push(struct Stack* stack, int item)

{

    if (isFull(stack))

        return;

    stack->array[++stack->top] = item;

    printf("%d pushed to stackn", item);

}

int pop(struct Stack* stack)

{

    if (isEmpty(stack))

        return INT_MIN;

    return stack->array[stack->top--];

}

int peek(struct Stack* stack)

{

    if (isEmpty(stack))

        return INT_MIN;

    return stack->array[stack->top];

}

int main()

{

    struct Stack* stack = createStack(100);

    push(stack, 10);

    push(stack, 20);

    push(stack, 30);

    printf("%d popped from stackn", pop(stack));

    return 0;

}

Java

class Stack {

    static final int MAX = 1000;

    int top;

    int a[] = new int[MAX];

    boolean isEmpty()

    {

        return (top < 0);

    }

    Stack()

    {

        top = -1;

    }

    boolean push(int x)

    {

        if (top >= (MAX - 1)) {

            System.out.println("Stack Overflow");

            return false;

        }

        else {

            a[++top] = x;

            System.out.println(x + " pushed into stack");

            return true;

        }

    }

    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]);

    }

  }

}

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() + " Popped from stack");

        System.out.println("Top element is :" + s.peek());

        System.out.print("Elements present in stack :");

        s.print();

    }

}

Pitón

from sys import maxsize

def createStack():

    stack = []

    return stack

def isEmpty(stack):

    return len(stack) == 0

def push(stack, item):

    stack.append(item)

    print(item + " pushed to stack ")

    

def pop(stack):

    if (isEmpty(stack)):

        return str(-maxsize -1)

    

    return stack.pop()

def peek(stack):

    if (isEmpty(stack)):

        return str(-maxsize -1)

    return apilar[len(stack) - 1]

stack = createStack()

push(stack, str(10))

push(stack, str(20))

push(stack, str(30))

print(pop(stack) + " popped from stack")

C#

using System;

namespace ImplementStack {

class Stack {

    private int[] ele;

    private int top;

    private int max;

    public Stack(int size)

    {

        ele = new int[size];

        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]);

            }

        }

    }

}

class Program {

    static void Main()

    {

        Stack p = new Stack(5);

        p.push(10);

        p.push(20);

        p.push(30);

        p.printStack();

        p.pop();

    }

}

}

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  

Pros: Fácil de implementar. La memoria se guarda ya que los punteros no están involucrados.
Contras: No es dinámico. No crece ni se encoge según las necesidades en tiempo de ejecución.
Implementando Stack usando Linked List:

C ++

#include <bits/stdc++.h>

using namespace std;

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 data)

{

    StackNode* stackNode = newNode(data);

    stackNode->next = *root;

    *root = stackNode;

    cout << data << " pushed to stackn";

}

int pop(StackNode** root)

{

    if (isEmpty(*root))

        return INT_MIN;

    StackNode* temp = *root;

    *root = (*root)->next;

    int popped = temp->data;

    free(temp);

    return popped;

}

int peek(StackNode* root)

{

    if (isEmpty(root))

        return INT_MIN;

    return root->data;

}

int main()

{

    StackNode* root = NULL;

    push(&root, 10);

    push(&root, 20);

    push(&root, 30);

    cout << pop(&root) << " popped from stackn";

    cout << "Top element is " << peek(root) << endl;

    

    cout<<"Elements present in stack : ";

     

    while(!isEmpty(root))

    {

        

        cout<<peek(root)<<" ";

        

        pop(&root);

    }

    return 0;

}

C

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

struct StackNode {

    int data;

    struct StackNode* next;

};

struct StackNode* newNode(int data)

{

    struct StackNode* stackNode =

      (struct StackNode*)

      malloc(sizeof(struct StackNode));

    stackNode->data = data;

    stackNode->next = NULL;

    return stackNode;

}

int isEmpty(struct StackNode* root)

{

    return !root;

}

void push(struct StackNode** root, int data)

{

    struct StackNode* stackNode = newNode(data);

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

apple touch icon@2

Longitud de un objeto JavaScript

edit

Amargo vs amargo – Diferencia y comparación