Estruturas de Dados em Java: Listas, Pilhas e Filas
Sejam L e P duas listas que contêm inteiros ordenados por ordem crescente. A operação printLots irá listar os elementos de L que estão nas posições especificadas em P. Por exemplo, se P for a lista {1, 3, 4, 6}, o método printLots(L,P) deve listar o 1.º, 3.º, 4.º e 6.º elemento da lista L.
public static void printLots(List L, List P){
String Aux = "";
for(int i = 0; i < P.size(); i++){
int W = P.get(i);
int X = L.get(W);
char Z = Integer.toString(X);
Aux = Aux + Z; }
System.out.println(Aux); }
SE FOR VOID FAZ-SE PRINT, SE NÃO, RETURN.
2. Implemente o método contains(Type x) como método de instância da classe LinkedList. O método deve retornar true se x pertence à lista, e false caso contrário. A classe LinkedList é a classe que implementa listas ligadas usando "Single Nodes".
public boolean contains(Type x){
LinkedList lista = new LinkedList();
SingleNode W;
for (int i = 0; i < lista.size(); i++){
W = lista.get(i);
Type Xo = W.element();
if (Xo == x){
return true; }
return false; }
3. Um iterador para listas (objeto do tipo ListIterator) estende as funcionalidades de Iterator para as coleções. Os métodos previous() e hasPrevious() permitem a travessia das listas do fim para o início. Considere que a classe MyDoubleListIterator implementa estes iteradores, usando nós duplamente ligados. Defina para esta classe os métodos abaixo, considerando que estão definidas para a classe 3 variáveis de instância: DoubleNode current; // nó atual, DoubleNode beginMarker; // dummy node início, DoubleNode endMarker; // dummy node fim.
a)
public boolean hasPrevious(){ return (current.getPrev() != null); }
b)
public T previous(){
current = current.getPrev();
T previtem = current.element();
return previtem; }
STACK
public interface Stack{
//public Stack();
//public Stack(int n);
void push (AnyType o);
AnyType top () throws EmptyException;
AnyType pop () throws EmptyException;
int size();
boolean empty(); }
LINKED LISTS
public interface Lista {
void add(T x); --> acrescenta o elemento especificado no final desta lista
void add(int i, T x); --> acrescenta o elemento especificado na posição especificada
void set(int i, T x); --> substitui o elemento na posição especificada nessa lista pelo elemento especificado
T remove(T x); --> remove a 1.ª ocorrência do elemento especificado, se estiver presente
void clear(); --> remove todos os elementos da lista
T get(int i); --> retorna o elemento na posição especificada
int size(); --> retorna o tamanho da lista
LIST
métodos:
boolean --> add(E e) --> acrescenta no fim da lista
void --> add(int index, E element) --> insere o elemento especificado na posição especificada
boolean --> contains(Object o) --> true se a lista contiver este elemento
--> equals(Object o) --> compara um objeto específico com um da lista
E --> get(int index) --> retorna o elemento nessa posição
int --> indexOf(Object o) --> retorna o índice do elemento e se não tiver retorna -1
boolean --> isEmpty() --> true se estiver vazia
E --> remove(int index)
boolean --> remove(Object o) --> remove o 1.º com esse nome
E --> set(int index, E element) --> substitui o elemento na posição especificada nesta lista pelo elemento especificado
int --> size() --> retorna o n.º de elementos da lista
1. Uma capicua. Implemente o método capicua (long n) que retorna true se o número passado por parâmetro é ou não uma capicua. Está proibido de usar arrays e outras estruturas de dados com exceção das Stacks.
public boolean capicua(long n){
Stack Xi = new Stack(50);
String numero = Long.toString(n);
String Aux = "";
for(int i = 0; i < numero.length(); i++){
char W = numero.charAt(i);
Xi.push(W); }
for(int j = 0; j < numero.length(); j++){
char Xo = Xi.pop();
Aux = Aux + Xo; }
if (Aux.equals(numero)){
return true; }
else{ return false; }
2. Uma deque é uma estrutura de dados que consiste numa lista de elementos sobre a qual são permitidas as seguintes operações:
• push(x), adiciona x à frente na lista
• pop(), remove o elemento da frente e retorna-o
• inject(x), adiciona x no fim da lista
• eject(), retira o elemento do fim da lista e retorna-o
(a) Apresente uma interface para Deque(s)
void push (E x);
E pop();
void inject(E x);
E eject();
(b) Apresente uma implementação da interface da alínea anterior, usando como estrutura de dados uma única stack.
public class MyDeque{
//variáveis de instância
private E[] deque;
int frente = 0;
int fim = 0;
int tamanho = 0;
public void push(E x){
if(this.tamanho == 0){
deque[frente] = x;
this.tamanho++;
fim++; }
this.tamanho++;
for(int i = this.tamanho - 1; i >= frente; i--){
deque[i] = deque[i - 1]; }
deque[frente] = x;
fim++; }
public E pop(){
if(this.tamanho == 0){ return null; }
else{
E x = deque[frente];
for(int i = this.tamanho - 1; i >= frente; i--){
deque[i + 1] = deque[i]; } }
this.tamanho--;
return x; }
CONTINUA
public void inject(E x){
this.tamanho++;
deque[this.tamanho] = x; }
public E eject(){
E K = deque[this.tamanho];
this.tamanho--;
return K; }
3. public static void method1(Queue q, int n){
for(int i = 0; i < n; i++){
q.enqueue(q.dequeue()); }}
(a) Se q=[1;2;3;4;5;6], após method1(q,q.size());, como fica q? Responda o que achar, podendo inclusive responder que existe algum tipo de erro, devendo especificar qual! q=[1,2,3,4,5,6]
(b) Responda agora assumindo igualmente que q=[1;2;3;4;5;6] e executa-se method1(q,100);. Qual o valor de q? Justifique! q=[5,6,1,2,3,4] pois (q,6) dá uma volta e fica igual, logo 100/6 = 16 * 6 + 4, logo vai dar 16 voltas e temos que fazer (q,4).)
4. Apresente o código Java para o método inverte, que recebe uma queue e retorna outra queue com os mesmos valores mas invertida. Isto é, se q={a,b,c,d}, inverte(q) retorna a queue {d,c,b,a}.
public static Queue inverte(Queue q){
Stack C = new Stack(50);
for(int i = 0; i < q.size(); i++){
char X = q.dequeue();
C.push(X); }
for(int j = 0; j < C.size(); j++){
char W = C.pop();
q.enqueue(W); }
return q; }
a) Complexidade? O(n) pois, apesar de existirem 2 ciclos, estão separados, não temos nenhum ciclo dentro de outro.
Se pedir para resolver por exemplo F(7), ir fazendo os cálculos, substituindo o n por 7 e, se o código tiver stacks, ir construindo a stack.
1. Apresente uma implementação de Queue(s) que use Stack(s). Resolva o exercício no teste completando o código seguinte:
public class QueueWithStack{
/* variáveis de instância */
public int posicao_atual = -1;
public int tamanho; }
public QueueWithStack(){ /* Construtor que cria uma fila de tamanho pré-definido */
this.tamanho = 50;
Stack Stack = new Stack(tamanho); }
public QueueWithStack(int n){ /* Construtor que cria uma fila de tamanho n */
this.tamanho = n;
Stack Stack = new Stack(tamanho); }
public void enqueue(E x){ /* adiciona x no fim da fila */
Stack.push(x);
this.posicao_atual++; }
public E dequeue(){ /* Remove o 1.º elemento da fila e devolve-o */
Stack Aux = new Stack(tamanho);
for(int i = 0; i < Stack.size(); i++){
E W = Stack.pop();
Aux.push(W); }
E K = Aux.pop();
for(int j = 0; j < Aux.size(); j++){
E Z = Aux.pop();
Stack.push(Z); }
this.posicao_atual--;
return K; }
public E front(){ /* Devolve o 1.º elemento da fila */
Stack Aux2 = new Stack(tamanho);
for(int i = 0; i < Stack.size(); i++){
E W = Stack.pop();
Aux2.push(W); }
E K = Aux2.top();
for(int j = 0; j < Aux2.size(); j++){
E Z = Aux2.pop();
Stack.push(Z); }
return K; }
public boolean isEmpty(){ /* está vazia? */
if(Stack.empty() == true){
return true; }
else{ return false; } }
public int size(){ /* Retorna o número de elementos da fila */
return Stack.size(); }
2. Numa pequena estação ferroviária, a entrada e saída de comboios é realizada usando o esquema representado na figura 1. Suponha quatro carruagens numeradas de 1 a 4.
• ADICIONAR(carruagem), que permite a entrada de uma carruagem na estação pela zona A, • RETIRAR(), que permite que uma carruagem saia da estação (pela zona C), • F(), que permite que uma carruagem passe da zona A para a zona B, • G(), que permite que uma carruagem passe da zona B para a zona C. A sequência de ações: ADICIONAR(1), ADICIONAR(2), ADICIONAR(3), ADICIONAR(4), F(), F(), F(), F(), G(), G(), G(), G(), RETIRAR(), RETIRAR().
a) public class Estacao{
queueZonaA = new Queue(4);
stackZonaB = new Stack(4);
queueZonaC = new Queue(4);
public void ADICIONAR(int carruagem){
ZonaA.enqueue(carruagem); }
public void RETIRAR(){
ZonaC.dequeue(); }
public void F(){
int Y = ZonaA.dequeue();
ZonaB.push(Y); }
public void G(){
int S = ZonaB.pop();
ZonaC.enqueue(S); } }
3. Apresente o código Java para o método maxOf que retorna o maior elemento da stack passada por argumento. A stack deve ficar inalterada.
public static E maxOf(Stack s){ Stack Tecla = new Stack(50); Stack Aux = new Stack(50); int Maior = 0; for (int i = 0; i < s.size(); i++){
int w = Tecla.pop();
if(w > Maior){
Maior = w; }
Aux.push(w); } for (int j = 0; j < Aux.size(); j++){
int a = Aux.pop();
Tecla.push(a); } return Maior; }