Análisis y Diseño de Algoritmos
Prof: Ing. Victor Garro
Asistente: Marco Elizondo Vargas
Listas Lineales
Introduccion
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.
–
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]);
}
–
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.
•
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]);
}