Estructura de datos y algoritmos: pila

Una pila es un tipo de datos abstracto (ADT), comúnmente utilizado en la mayoría de los lenguajes de programación. Se llama pila porque 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, podemos colocar o quitar una tarjeta o un plato de la parte superior de la pila únicamente. Asimismo, 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 la convierte en estructura de datos LIFO. LIFO son las siglas de Last-in-first-out. Aquí, se accede primero al elemento que se coloca (inserta o agrega) en último lugar. En terminología de pila, la operación de inserción se llamaPUSH operación y operación de remoción se llama POP operación.

Representación de pila

El siguiente diagrama muestra una pila y sus operaciones:

Una pila se puede implementar mediante Array, Structure, Pointer y Linked List. La pila puede tener un tamaño fijo o puede tener una sensación de cambio de tamaño dinámico. Aquí, vamos a implementar la pila usando matrices, 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 desinicializarla. Aparte de estos elementos básicos, se utiliza una pila para las siguientes dos operaciones principales:

push() - Empujar (almacenar) un elemento en la pila.
pop() - Eliminar (acceder) un elemento de la pila.

Cuando los datos se PUSHEN a la pila.

Para usar una pila de manera eficiente, también debemos verificar el estado de la pila. Con el mismo propósito, se agrega la siguiente funcionalidad a las pilas:

peek() - obtener el elemento de datos superior de la pila, sin eliminarlo.
isFull() - compruebe si la pila está llena.
isEmpty() - comprobar si la pila está vacía.

En todo momento, mantenemos un puntero a los últimos datos PUSHED en la pila. Como este puntero siempre representa la parte superior de la pila, de ahí el nombretop. lostop puntero proporciona el valor superior de la pila sin eliminarlo realmente.

Primero, deberíamos aprender sobre los procedimientos para admitir funciones de pila:

ojeada()

Algoritmo de la función peek () -

begin procedure peek
   return stack[top]
end procedure

Implementación de la función peek () en lenguaje de programación C -

Example

int peek() {
   return stack[top];
}

está lleno()

Algoritmo de la función isfull () -

begin procedure isfull

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

Implementación de la función isfull () en lenguaje de programación C -

Example

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

esta vacio()

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 la parte superior en -1, ya que el índice en la matriz comienza desde 0. Por lo tanto, verificamos si la parte superior está por debajo de cero o -1 para determinar si la pila está vacía. Aquí está el código:

Example

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

Operación de empuje

El proceso de poner un nuevo elemento de datos en la pila se conoce como operación de inserción. La operación de empuje implica una serie de pasos:

Step 1 - Comprueba si la pila está llena.
Step 2 - Si la pila está llena, produce un error y sale.
Step 3 - Si la pila no está llena, aumenta top para señalar el siguiente espacio vacío.
Step 4 - Agrega un elemento de datos a la ubicación de la pila, donde apunta la parte superior.
Step 5 - Devuelve el éxito.

Si la lista vinculada se usa 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[top] ← data

end procedure

La implementación de este algoritmo en C es muy sencilla. Ver el siguiente código -

Example

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

Operación Pop

Acceder al contenido mientras se elimina de la pila se conoce como operación emergente. En una implementación de matriz de la operación pop (), el elemento de datos no se elimina realmente, en su lugartopse reduce a una posición más baja en la pila para apuntar al siguiente valor. Pero en la implementación de listas vinculadas, pop () en realidad elimina el elemento de datos y desasigna el espacio de memoria.

Una operación Pop puede implicar los siguientes pasos:

Step 1 - Comprueba si la pila está vacía.
Step 2 - Si la pila está vacía, produce un error y sale.
Step 3 - Si la pila no está vacía, accede al elemento de datos en el que top está apuntando.
Step 4 - Disminuye el valor de top en 1.
Step 5 - Devuelve el éxito.

Algoritmo para operación pop

Un algoritmo simple para la operación Pop se puede derivar de la siguiente manera:

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

La implementación de este algoritmo en C es la siguiente:

Example

int pop(int data) {

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

Para obtener un programa de pila completo en lenguaje de programación C, haga clic aquí .

↰ Previous page Next page ↱