PDF de programación - Pilas y Colas

Imágen de pdf Pilas y Colas

Pilas y Colasgráfica de visualizaciones

Publicado el 14 de Enero del 2019
1.349 visualizaciones desde el 14 de Enero del 2019
3,3 MB
64 paginas
Creado hace 9a (20/01/2015)
Programación de sistemas



Pilas y Colas



Julio Villena Román

<[email protected]>



MATERIALES BASADOS EN EL TRABAJO DE DIFERENTES AUTORES:

Carlos Delgado Kloos, Jesús Arias Fisteus, Carlos Alario Hoyos

1

Contenidos

 Pilas (stacks)
 Colas (queues)
 Colas dobles (deques – double-ended queues)

2

Pilas

• Estructura de datos lineal



Inserción y extracción por un único extremo
 LIFO (Last-In-First-Out)

3

Pilas



Insertar por un extremo: push(x)

• Extraer por el mismo extremo: pop()

4

Ejemplo:
Revisión de paréntesis

• Correcto:

• Incorrecto:

o

o ()

o (()(()))

o )(

o (()

o ())



• Reglas:

o Básica: apertura + cierre

o Secuenciación: ()()

o Anidamiento: (())



5

Ejemplo:
Revisión de paréntesis



Reglas:
• Cada vez que encontremos un “(“ se añade a la pila
• Cada vez que encontremos un “)” se extraerá el “(“ de

arriba de la pila

• La expresión con paréntesis es correcta si la pila está

vacía al acabar la expresión y siempre hemos
encontrado un “)” correspondiente a un “(”


6

Ejemplo:
(()(()())())

(()(()())())

7

Ejemplo:
(()(()())())

(

(()(()())())

8

Ejemplo:
(()(()())())

(
(

(()(()())())

9

Ejemplo:
(()(()())())

(

(()(()())())

10

Ejemplo:
(()(()())())

(
(

(()(()())())

11

Ejemplo:
(()(()())())

(
(
(

(()(()())())

12

Ejemplo:
(()(()())())

(
(

(()(()())())

13

Ejemplo:
(()(()())())

(
(
(

(()(()())())

14

Ejemplo:
(()(()())())

(
(

(()(()())())

15

Ejemplo:
(()(()())())

(

(()(()())())

16

Ejemplo:
(()(()())())

(
(

(()(()())())

17

Ejemplo:
(()(()())())

(

(()(()())())

18

Ejemplo:
(()(()())())

Correcto: Expresión completa y

pila vacía!!

(()(()())())

19

Ejemplo:
([]{()<>}())

Correcto: Expresión completa y

pila vacía!!

([]{()<>}())

20

Ejemplo:
HTML



<b><i>hello</b></i>
• Correcto en HTML 1.0-4.0
• Incorrecto en XHTML

<b><i>hello</i></b>
• Correcto en ambos

21

Interfaz para pilas

public interface Stack<E> {
boolean isEmpty();
int size();
E top();
void push(E info);
E pop();
}



22

Interfaz para pilas (con excepciones)

public interface Stack<E> {
boolean isEmpty();
int size();
E top() throws

EmptyStackException;

void push(E info) throws

StackOverflowException;

E pop() throws

EmptyStackException;

}



23

Una interfaz dos implementaciones

Implementación basada en arrays:

 ArrayStack

Implementación basada en listas enlazadas:

 LinkedStack







24

ArrayStack

top



0

1

2 3

4

5

6 … … N-1

Pila vacía

top



1

0

1

2 3

4

5

6 … … N-1

Pila con 1 elemento

top



1 2 3 4



0

1

2 3

4

5

6 … … N-1

Pila con 4 elementos

25

ArrayStack (I)

public class ArrayStack<T> implements Stack<E> {

public static final int DEFAULT_CAPACITY = 1000;

private int capacity;

private E data[];

private int top = -1;

public ArrayStack() {

this(DEFAULT_CAPACITY);

}

public ArrayStack(int capacity) {
this.capacity = capacity;

data = new E[capacity];

}



26

ArrayStack (II)


public int size() {
return (top + 1);

}
public boolean isEmpty() {
return (top < 0);

}
public E top() throws EmptyStackException {
if (isEmpty())

throw new EmptyStackException(“Empty");
return data[top];
}




27

ArrayStack (III)


public void push(E o)
throws StackOverflowException {
if (size == capacity)
throw new StackOverflowException();
data[++top] = o;
}



28

ArrayStack (IV)


public E pop() throws StackEmptyException {
E o;
if (top == -1)
throw new EmptyStackException();
o = data[top];
data[top--] = null;
return o;
}

}



29

LinkedStack

Extremo de
inserción y
extracción

Pila vacía

Pila con 1 elemento

Pila con 4 elementos

30

Recordando la clase Node

{…}


public class Node<E> {
private E info;
private Node<E> next;

public Node()
public Node(E info) {…}
public Node(E info, Node<E> next)

public Node<E> getNext() {…}
public void setNext(Node<E> next) {…}
public E getInfo() {…}
public void setInfo(E info) {…}

}


{…}

31



Atributos

Constructor

LinkedStack (I)



public class LinkedStack<E> implements Stack<E> {
private Node<E> top;
private int size;
public LinkedStack() {
top = null;
size = 0;
}

public boolean isEmpty() {
return (top == null);
}

public int size() {
return size;
}

public E top() {
if(isEmpty()){
return null;
}
return top.getInfo();
}


Métodos de la interfaz
Stack a implementar (I)

32

Inserción (push)

top

Moscú

Madrid

Miami

Múnich

33

Extracción (pop)

top

Moscú

Madrid

Miami

Múnich

34

LinkedStack (II)




public void push(E info){
Node<E> n = new Node<E>(info, top);
top = n;
size++;
}

public E pop() {
E info;
if(isEmpty()){
return null;
} else{
info = top.getInfo();
top = top.getNext();
size--;
return info;
}
}
}



Métodos de la interfaz

Stack a implementar (II)

35

Colas

• Estructura de datos lineal



Inserción por un extremo y extracción por el

exremo opuesto
 FIFO (First-In-First-Out)

36

Colas



Insertar por un extremo: enqueue(x)

• Extraer por el extremo opuesto: dequeue()

37

Interfaz para colas

public interface Queue<E> {
boolean isEmpty();
int size();
E front();
void enqueue (E info);
E dequeue();
}


38

Interfaz para colas (con excepciones)

public interface Queue<E> {
boolean isEmpty();
int size();
E front() throws

EmptyQueueException;

void enqueue (E info) throws

QueueOverflowException;

E dequeue() throws

EmptyQueueException;

}


39

Una interfaz dos implementaciones

Implementación basada en arrays:

 ArrayQueue

Implementación basada en listas enlazadas:

 LinkedQueue







40

ArrayQueue

top

tail



top



1

0
tail

2 3

4

5

6 … … N-1

Cola vacía



1

0

top

1

2 3

4

5

6 … … N-1

tail

Insertamos 1 elemento

4

5


tail

6 … … N-1



1 2 5 9 3

0

1

2 3

4

top



5 9 3

0

1

2 3

4



4

5

Insertamos 5
elementos más

Extraemos dos
elementos

6 … … N-1

41

LinkedQueue

Extremo de
extracción

Cola vacía

Cola con 1 elemento

Extremo de
inserción

Cola con 4 elementos

42

LinkedQueue (I)



public class LinkedQueue<E> implements Queue<E> {
private Node<E> top = null;
private Node<E> tail = null;
private int size = 0;
public LinkedQueue(){
top = null;
tail = null;
size = 0;
}

public boolean isEmpty() {
return (top == null);
}

public int size() {
return size;
}

public E front() {
if (isEmpty()){
return null;
} else {
return top.getInfo();
}
}


Atributos

Constructor

Métodos de la interfaz
Queue a implementar (I)

43

Inserción (enqueue)

top

tail

n

Madrid

Miami

Múnich

Moscú

44

LinkedQueue (II)




public void enqueue (E info){
Node<E> n = new Node<E>(info, null);
if (isEmpty()){
top = n;
} else{
tail.setNext(n);
}
tail = n;
size++;
}




Métodos de la interfaz

Queue a implementar (II)

45

Extracción (dequeue)

top

tail

Madrid

Miami

Múnich

Moscú

46

LinkedQueue (III)




public E dequeue(){
E info;
if (isEmpty()){
info = null;
} else{
info = top.getInfo();
top = top.getNext();
size--;
if (isEmpty()){
tail = null;
}

return info;
}
}



}

Métodos de la interfaz

Queue a implementar (III)

47

Actividad


http://courses.cs.vt.edu/csonline/DataStr
uctures/Lessons/QueuesImplementationView/
applet.html



DepthBreadth.java en
http://www.faqs.org/docs/javap/c11/s3.html

48

Colas dobles (deques)

• Estructura de datos lineal

o Deque (double-ended queue)



Inserción y extracción por cualquiera de los extremos

49

Interfaz para colas dobles

public interface Deque<E> {
public boolean isEmpty();
public int size();
public E first();
public E last();
public void insertFirst(E info);
public void insertLast(E info);
public E removeFirst();
public E removeLast();
}


50

Interfaz para colas dobles

Stack

Deque

Queue

Deque

size()

size()

size()

size()

isEmpty() isEmpty()

isEmpty() isEmpty()

top()

last()

front()

first()

push(x)

insertLast(x)

enqueue(x) insertLast(x)

pop()

removeLast()

dequeue() removeFirst()

51

Implementación de colas dobles

• Las listas enlazadas no son apropiadas porque

removeLast necesita recorrer la lista

completa para obtener la referencia del

penúltimo

• Solución: listas doblemente enlazadas



52

Listas doblemente enlazadas

• Listas enlazadas en que cada nodo, además de

almacenar el dato y la referencia del siguiente nodo,

almacena también la referencia del nodo anterior
o Permiten recorrer la lista en ambos sentidos

o Reducen el coste de extracción del último nodo

top

tail



null

info

prev
  • Links de descarga
http://lwp-l.com/pdf14850

Comentarios de: Pilas y Colas (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad