Anuncios

Una pila es un Tipo de dato Abstracto (TDA), comúnmente utilizado en la mayoría de los lenguajes de programación. Se llama pila, ya que se comporta como una pila del mundo real, por ejemplo, una baraja de cartas o una pila de platos, etc.

una pila del mundo real permite operaciones en un solo extremo. Por ejemplo, solo podemos colocar o quitar una carta o plato de la parte superior de la pila., Del mismo modo, Stack ADT permite todas las operaciones de datos en un solo extremo. En un momento dado, solo podemos acceder al elemento superior de una pila.

Esta característica lo convierte en una estructura de datos LIFO. LIFO significa Last-in-first-out. Aquí, el elemento que se coloca (insertado o agregado) último, se accede primero. En la terminología de la pila, la operación de inserción se llama operación de empuje y la operación de eliminación se llama operación POP.,

representación de pila

el siguiente diagrama representa una pila y sus operaciones −

una pila puede ser implementada por medio de matriz, Estructura, puntero y lista enlazada. La pila puede ser de tamaño fijo o puede tener una sensación de redimensionamiento dinámico. Aquí, vamos a implementar la pila usando arrays, lo que la convierte en una implementación de pila de tamaño fijo.

operaciones básicas

Las operaciones de pila pueden implicar inicializar la pila, usarla y luego desiniciarla., Aparte de estos elementos básicos, una pila se utiliza para las siguientes dos operaciones principales −

  • push () – empujar (almacenar) un elemento en la pila.

  • pop() − Extracción (acceder) a un elemento de la pila.

Cuando los datos se introducen en la pila.

para usar una pila de manera eficiente, necesitamos comprobar el estado de la pila también. Para el mismo propósito, se agrega la siguiente funcionalidad a stacks –

  • peek () – obtener el elemento de datos superior de la pila, sin eliminarlo.

  • isFull() − comprueba si la pila está llena.,

  • isEmpty() − comprueba si la pila está vacía.

en todo momento, mantenemos un puntero a los últimos datos insertados en la pila. Como este puntero siempre representa la parte superior de la pila, por lo tanto llamado top. El puntero superior proporciona el valor superior de la pila sin eliminarlo realmente., funciones de pila de soporte −

Peek()

algoritmo de la función peek () −

begin procedure peek return stackend procedure

implementación de la función peek() en el lenguaje de programación C −

ejemplo

int peek() { return stack;}

Isfull()

algoritmo de isfull() function −

begin procedure isfull if top equals to MAXSIZE return true else return false endif end procedure

implementación de la función isfull() en el lenguaje de programación C −

ejemplo

bool isfull() { if(top == MAXSIZE) return true; else return false;}

isEmpty()

algoritmo de la función isEmpty () −

begin procedure isempty if top less than 1 return true else return false endif end procedure

la implementación de la función isEmpty() en el lenguaje de programación C es ligeramente diferente., Inicializamos top en -1, ya que el índice en la matriz comienza desde 0. Así que comprobamos si la parte superior está por debajo de cero o -1 para determinar si la pila está vacía. Aquí está el código −

ejemplo

bool isempty() { if(top == -1) return true; else return false;}

Push Operation

El proceso de poner un nuevo elemento de datos en la pila se conoce como Push Operation. La operación Push implica una serie de pasos –

  • Paso 1-Comprueba si la pila está llena.

  • Paso 2 – si la pila está llena, produce un error y sale.

  • Paso 3 – si la pila no está llena, incrementa la parte superior para apuntar al siguiente espacio vacío.,

  • Paso 4: agrega un elemento de datos a la ubicación de la pila, donde está apuntando top.

  • Paso 5 − Devuelve éxito.

si la lista enlazada se utiliza para implementar la pila, entonces en el paso 3, necesitamos asignar espacio dinámicamente.

algoritmo para la operación PUSH

un algoritmo simple para la operación Push se puede derivar de la siguiente manera: 

begin procedure push: stack, data if stack is full return null endif top ← top + 1 stack ← dataend procedure

la implementación de este algoritmo en C, es muy fácil., Vea el siguiente código-

Ejemplo 

void push(int data) { if(!isFull()) { top = top + 1; stack = data; } else { printf("Could not insert data, Stack is full.\n"); }}

operación Pop

acceder al contenido mientras lo elimina de la pila, se conoce como una operación Pop. En una implementación de matriz de la operación pop (), el elemento de datos no se elimina realmente, en su lugar top se decrementa a una posición más baja en la pila para apuntar al siguiente valor. Pero en la implementación de listas enlazadas, pop () en realidad elimina el elemento de datos y desasignaespacio de memoria.

una operación Pop puede implicar los siguientes pasos −

  • Paso 1 − Comprueba si la pila está vacía.,

  • Paso 2 – si la pila está vacía, produce un error y sale.

  • Paso 3 – si la pila no está vacía, accede al elemento de datos al que apunta top.

  • Paso 4-disminuye el valor de top en 1.

  • Paso 5 − Devuelve éxito.,

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack if stack is empty return null endif data ← stack top ← top - 1 return dataend procedure

Implementation of this algorithm in C, is as follows −

Example

int pop(int data) { if(!isempty()) { data = stack; top = top - 1; return data; } else { printf("Could not retrieve data, Stack is empty.\n"); }}

For a complete stack program in C programming language, please click here.

Advertisements