Pilas y colas

Tabla de Contenidos

!

"

# #
$ %

&

Índice de Listados
$ $ $ $ $ $ $ ' ! (' ! ' ! ' ! "' ! &' ! *' ! ! ) ! & ( ( * * + (

1. Introducción
! % & ( # & ! # & " # # % + , % % $ $ )* " # ! - " . # % ! # $ "' $ " # $

! &

2. Pilas
* + #& % 2 2 # , " % 2.1 % • push( / # • pop( 4 & $ , # #& #5 % % push $ pop-$ * # % + #5 * # Funciones asociadas a las pilas , #& % ( % + % 3! / 0" & # !* 3 /0 ! /0 "1 # )

1 * 6 %

% ! 2 ', "1 # !

push * * , ( A AB A AC

6

2 % *

pop "7 #

push(A) push(B) pop() push(C) push(D) pop() pop() pop() 2.2 1

B

ACD AC A D C A

Soporte para la implementación de una pila $ $ ' % 3 $ 3 % # # -

2.2.1 1 % • 1 • / %

Uso de listas 3 # # * ! pop" , 3 ( 3 ! push" , 3 ( -

• &* • 9 2.2.2 1 ' + & • • 7 + + : % & / + %, % + ( push(A) + # 3 -base% # cima # Uso de tablas 3 ,

#

, ( 3 ( 3 3 # & + , #& # , , 3 % # pop $push

push(B)

pop()

⇐ ⇐ , ; % , & & , 2.3 Aplicaciones de pilas # > ,= 0 " # * 3 '$ < ⇐ , + 3 , #5, (base + dimension) == cima < = * # # ; % * 9 ; $ dimension# ; ⇐

& $ LIFO !

/

8

2.4 5 $ &

Ejercicio con tablas 3 % # ! -- $/"$ +- * 4 :(7 - 3) * (2 + 1) 4 : 7 3 – 2 1 + * ', 3 # $ 3 ' % ( , 3 $ = # ( ! :" 4 , # ? * % -

& • @fA # • 1 • 1 , " 10" , " # , , * * $ , pila# 5 # , -$

! # MAXELE ! + < , 3 int $ #& +

!

0 cima-1$

0#

2.4.1 &

Organización en ficheros %' 6 calc.c2 # % %

%' 6 pila.c2 # %' 6 pila.h2 # & 6 cogeOp.c2 % % ,, & 6 pila.c2 ! ,= static" ! % , * " # % 2.4.2

coge_op$ 3 isspace isdigit , pila ! %' ! 3 ": # , %'

$ # cima

,static" $ + % , , ', (

Aclaraciones sobre el programa principal

; • 7

3 +( < ( , numero ! # ( #& * #& # • : + ( % + # % ! # %

%

coge_op= @0A $ "& #

• 7

#

% # 5 , @\nA ! +"$ 3 ' '$ + "5 # # 5

+ # • & • 0 ( + # % $ , 3 #B = p06/pilaConTablas 7 %' makefile % switch# pilaConTablas# 1 3 , % , # push $pop( , # , p06 = %' #5 % , ' , # # # % % ' , @fA#

%' #

• % •

%push 0

, '

% 3 , #& ' % 3 -$ 1 , % # > < - 1 $ #

# & #>

%

pop * -0 *

#

Listado 1: Fichero pila.c
#define MAXELE 10 #include "pila.h" static int pila[MAXELE]; static int cima = 0;

/* base es 0 */

/* Función que almacena un elemento en la pila */ /* Si la pila no está llena, añadir i a la pila en la posición cima e incrementar cima. En este caso se devuelve 0. Si lapila está llena, no se hace nada y se devuelve 1 */ int push (int i) { /*Añadir código*/ }

/* Función que extrae un elemento de la pila */ /* Si la pila no está vacía, copiar el elemento que está en la posición cima en la dirección apuntada por el parámetro y decrementar cima. En este caso se devuelve 0. Si la pila está vacía, no se hace nada y se devuelve 1 */ int pop (int *pi) { /*Añadircódigo*/ }

/* Función que vacía la pila */ void vaciar_pila (void) { cima=0; }

;

%'

,

3

(

Listado 2: Fichero pila.h
#ifndef PILA_H #define PILA_H int push(int i); int pop(int *f); #endif

Listado 3: Fichero makefile
# # # Macros

COMPILADOR OBJETO CABECERA OPCIONES EJECUTABLE # # #

= = = = =

gcc pila.o cogeOp.o calc.o pila.h cogeOp.h -Wall -c calculadoraConstruccion del ejecutable

$(EJECUTABLE): $(OBJETO) $(CABECERA) $(COMPILADOR) -o $(EJECUTABLE) $(OBJETO) pila.o: pila.c $(CABECERA) $(COMPILADOR) $(OPCIONES) pila.c cogeOp.o: cogeOp.c $(CABECERA) $(COMPILADOR) $(OPCIONES) cogeOp.c calc.o: calc.c $(CABECERA) $(COMPILADOR) $(OPCIONES) calc.c

C

Listado 4: fichero cogeOp.c
#include #include #include “cogeOp.h” /*para usar isspace e isdigit*/int coge_op(int *pnum) { /*Funcion que lee un elemento de la entrada*/ int c; int num; do { c = getchar(); }while (isspace(c) && c!= '\n'); if (isdigit(c)) { num = 0; do{ num = num *10 + c - '0'; c = getchar(); } while(isdigit(c)); *pnum = num; if (c!=’f’) ungetc(c,stdin); c = '0'; } return c; }

Listado 5: fichero cogeOp.h
#ifndef COGEOP_H #define COGEOP_H int coge_op(int *pnum); #endif

D...