Pilhas e filas java

LEIC-FEUP 2001/2002 Algoritmos e Estruturas de Dados 1

Pilhas Filas e Listas
Sumário
Pilha: interface, aplicações e implementação Fila: interface, aplicações e implementação Lista Ligada: interface, aplicações e implementação

PFL

Pilha
Estrutura LIFO (last in, first out)
Acesso restrito ao último elemento inserido

Operações
Inserir:

push

Remover: pop Pesquisar: top push pop top
PFL

Cristina Ribeiro

Estruturas Lineares 1

LEIC-FEUP 2001/2002 Algoritmos e Estruturas de Dados 1

Interface
// // // // // // // // // // // Stack interface ******************PUBLIC OPERATIONS********************* void push( x ) --> Insert x void pop( ) --> Remove most recently inserted item Object top( ) --> Return most recently inserted item Object topAndPop( ) --> Return and remove most recent item boolean isEmpty( ) --> Return true if empty; else false void makeEmpty( ) --> Remove all items ******************ERRORS******************************** top, pop, or topAndPop on empty stack

public interface Stack { boolean isEmpty( ); Object top( ) throws Underflow; throws Underflow; void pop( ) Object topAndPop( ) throws Underflow; void push( Object x ); void makeEmpty( ); }
PFL

Class Stack em java.util
§3.8 Class Stack public class java.util.Stack extends java.util.Vector (I-§3.10) { // Constructors public Stack(); §3.8.1 // public public public public public } Methods boolean empty(); Object peek(); Object pop(); Object push(Object int search(Object

§3.8.2 §3.8.3 §3.8.4 item); §3.8.5 o); §3.8.6

Não usa interface: define operações da pilha como extensão de vector - permite outras operações (de vector)
PFL

Cristina Ribeiro

Estruturas Lineares 2

LEIC-FEUP 2001/2002 Algoritmos e Estruturas de Dados 1

Aplicações
Compilação de linguagens de programação verificação sintáctica (gramáticas)
• Pilha é adequada para guardar contextos, mantendo disponível o corrente

chamada de procedimentos
• Chamada: empilha registo de