Cap´ıtulo IV Tipo Abstracto de Dados Pilha — Fila com Disciplina LIFO

Capı́tulo IV
Tipo Abstracto de Dados
Pilha
—
Fila com Disciplina LIFO
(Last In First Out)
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
1
Interface Pilha de Elementos do Tipo E
package dataStructures;
public interface Stack<E>
{
// Returns true iff the stack contains no elements.
boolean isEmpty( );
// Returns the number of elements in the stack.
int size( );
// Returns the element at the top of the stack.
E top( ) throws EmptyStackException;
// Inserts the specified element onto the top of the stack.
void push( E element );
// Removes and returns the element at the top of the stack.
E pop( ) throws EmptyStackException;
}
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
2
Pilha em Vector
0
1
25 10
0
1
25 10
0
1
25 10
2
3
0
31
2
3
0
4
5
3
4
5
31 −4
2
3
0
31
ı́ndiceTopo
4
ı́ndiceTopo
4
5
empilha -4
desempilha (; −4)
ı́ndiceTopo
3
Quando a pilha está vazia
0
1
2
3
4
5
ı́ndiceTopo
?
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
3
Pilha em Vector
0
1
25 10
0
1
25 10
0
1
25 10
2
3
0
31
2
3
0
4
5
3
4
5
31 −4
2
3
0
31
ı́ndiceTopo
4
ı́ndiceTopo
4
5
empilha -4
desempilha (; −4)
ı́ndiceTopo
3
Quando a pilha está vazia
0
1
2
3
4
5
ı́ndiceTopo
−1
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
4
Classe Pilha em Vector (1)
package dataStructures;
public class StackInArray<E> implements Stack<E>
{
// Default capacity of the stack.
public static final int DEFAULT CAPACITY = 1000;
// Memory of the stack: an array.
protected E[] array;
// Index of the element at the top of the stack.
protected int top;
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
5
Classe Pilha em Vector (2)
public StackInArray( )
{
this(DEFAULT CAPACITY);
}
public StackInArray( int capacity )
{
// Compiler gives a warning.
array = (E[]) new Object[capacity];
top = −1;
}
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
6
Classe Pilha em Vector (3)
// Returns true iff the stack contains no elements.
public boolean isEmpty( )
{
return top == −1;
}
// Returns true iff the stack cannot contain more elements.
public boolean isFull( )
{
return this.size() == array.length;
}
// Returns the number of elements in the stack.
public int size( )
{
return top + 1;
}
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
7
Classe Pilha em Vector (4)
// Returns the element at the top of the stack.
public E top( ) throws EmptyStackException
{
if ( this.isEmpty() )
throw new EmptyStackException(”Stack is empty.”);
return array[top];
}
// Inserts the specified element onto the top of the stack.
public void push( E element ) throws FullStackException
{
if ( this.isFull() )
throw new FullStackException(”Stack is full.”);
top++;
array[top] = element;
}
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
8
Classe Pilha em Vector (5)
// Removes and returns the element at the top of the stack.
public E pop( ) throws EmptyStackException
{
if ( this.isEmpty() )
throw new EmptyStackException(”Stack is empty.”);
E element = array[top];
array[top] = null; // For garbage collection.
top--;
return element;
}
}
// End of StackInArray.
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
9
Pilha em Lista Simplesmente Ligada
com Cabeça
-
31
-
25
empilha -4
cabeça
-
−4
-
31
-
25
desempilha (; −4)
cabeça
-
31
-
25
cabeça
Quando a pilha está vazia
?
cabeça
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
10
Pilha em Lista Simplesmente Ligada
com Cabeça
-
31
-
25
empilha -4
cabeça
-
−4
-
31
-
25
desempilha (; −4)
cabeça
-
31
-
25
cabeça
Quando a pilha está vazia
cabeça
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
11
Pilha em Lista Ligada (versão implementada)
cabeça
?
cauda
25
6
cabeça
cauda
31
empilha -4
?
−4
31
25
6
cabeça
desempilha
?
cauda
31
25
6
Quando a pilha está vazia
cabeça
cauda
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
12
Classe Pilha em Lista Duplamente Ligada (1)
package dataStructures;
public class StackInList<E> implements Stack<E>
{
// Memory of the stack: a list.
protected List<E> list;
public StackInList( )
{
list = new DoublyLinkedList<E>();
}
// Returns true iff the stack contains no elements.
public boolean isEmpty( )
{
return list.isEmpty();
}
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
13
Classe Pilha em Lista Duplamente Ligada (2)
// Returns the number of elements in the stack.
public int size( )
{
return list.size();
}
// Returns the element at the top of the stack.
public E top( ) throws EmptyStackException
{
if ( list.isEmpty() )
throw new EmptyStackException(”Stack is empty.”);
return list.getFirst();
}
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
14
Classe Pilha em Lista Duplamente Ligada (3)
// Inserts the specified element onto the top of the stack.
public void push( E element )
{
list.addFirst(element);
}
// Removes and returns the element at the top of the stack.
public E pop( ) throws EmptyStackException
{
if ( list.isEmpty() )
throw new EmptyStackException(”Stack is empty.”);
return list.removeFirst();
}
}
// End of StackInList.
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
15
Complexidades (em todos os casos)
Operação
Pilha em Vector
Pilha em Lista Ligada
isEmpty
O(1)
O(1)
size
O(1)
O(1)
top
O(1)
O(1)
push
O(1)
O(1)
pop
O(1)
O(1)
Margarida Mamede, DI – FCT/UNL
AED, 2009/10, Capı́tulo IV
16