• 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]);
}
Ir a Pagina del Curso