Análisis y Diseño de Algoritmos                                                                                                      

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

 

Listas Lineales

 

Introduccion Pilas y COLAS

 

Pilas y Colas

•         Los pilas y las colas son conjuntos de datos dinámicos en los que hay restricciones sobre el elemento que puede removerse.

•         En las pilas sólo se puede remover el elemento más recientemente insertado. Implementa así una política last-in, first-out o LIFO.

•         Las colas sólo pueden remover el elemento más antiguo del conjunto. Implementa una política first-in, first-out o FIFO.

 

PILAS

–        La operación de inserción es llamada aquí PUSH.

–        La operación eliminación es llamada POP.

–        No puede hacerse  POP de un stack vacío.

–        Si la implementación del stack posee un límite para el número de elementos y éste se excede, decimos que hay un overflow. También es un error.

–        Se incorpora la función TOP que retorna el valor más reciente sin modificar el stack.

 

Operaciones:

a)      t = pop(s) remueve el elemento superior de la pila s y lo retorna como valor de la funcion.

b)      Push(s,t): Agrega el elemento t al tope de la pilas

c)      Empty(s): returna True si la pila esta vacia y False en caso contrario

 

•         Const int MAX_ELEMENTS = 100;

•         typedef struct stack {
            int top;
            int element [MAX_ELEMENTS];
} STACK;

•         void MakeNull(STACK *S) {
            S->top=-1;
}

•         int Stack_Empty(STACK * S) {
            return (S->top == -1);
}

•         void Push( STACK *S, int x) {
     if  (S->top < MAX_ELEMENTS) {
            (*S).top++; 

                  (*S).element[(*S).top]=x;   /* pudo ser S->element [S->top]=x; */
                  /* o ambas en (*S).element[++(*S).top]=x; */

  }
}

•         int Pop (STACK *S) {
   if ((*S).top > -1) {  /* stack no vacío */
            return((*S).element[(*S).top--]);
}

•         int Top(STACK *S) {
            if (S->top > -1)
            return (S->element[S->top]);
}                    

        

 

COLAS

–        Operación Inserción es llamada Encolar

–        La operación eliminación es llamada desencolar.

–        Cada cola tiene una head (cabeza) y un tail (cola).

–        Se incorpora la función Head que retorna el valor más antiguo de la cola.

 

Implementacion de Cola con arreglo circular

 

•         Const int MAX_ELEMENTS = 100;

•         typedef struct queue {
    int head;  /* apunta al elemento más antiguo de la queue, el “primero” */
    int tail;     /* apunta elemento más recientemente ingresado, el de atrás */
    int count;  /* no. elementos en la cola. Permite distinguir cola vacía de llena */
    int element [MAX_ELEMENTS];
} QUEUE;

•         void MakeNull(QUEUE *Q) {
            Q->head=0;
            Q->tail=MAX_ELEMENTS-1;
            Q->count=0;
}

•         int Queue_Empty(QUEUE * Q) {
            return (Q->count == 0);
}

•         void Enqueue( QUEUE *Q, int x) {
            if  (Q->count++ < MAX_ELEMENTS) {
                        Q->tail= ++Q->tail%MAX_ELEMENTS;
                        Q->element[Q->tail] = x;

                  }
       }

•         int Dequeue (QUEUE *Q) {
            int aux=Q->head;
            if  (Q->count--  > 0) {  /* Queue no vacío */
                  Q->head= ++Q->head % MAX_ELEMENTS;
                 return((*Q).element[aux]);

                  }
      }

•         int Head(QUEUE *Q) {
            if (Q->count >0)
                return (Q->element[Q->head]);
}