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
Comentarios de: Pilas y Colas (0)
No hay comentarios