[Eclipse] Informatik Klausur

[Showtime]

Hallo liebe Java-Forum Gemeinde,

ich schreibe gerade eine Informatik Klausur in der Stufe 11 und benötige dringend eure Hilfe, da ich absolut nicht weiter weiß.
Ich weiß, ihr macht keine Hausaufgaben etc. für Leute, allerdings wäre mir die Hilfe sehr wichtig !

Also folgende Aufgabenstellungen :

1)

Zwei stacks seien so geordnet, dass die kleinsten Zahlen jeweils oben stehen.
Aus beiden stacks soll ein einziger geordneter stack gebildet werden. Erstelle ein Java-Programm.

2)

Die Anzahl der Elemente eines stacks soll bestimmt werden.

3)

In einem stack ist ein Element zu suchen. Falls vorhanden, soll dieses Element aus dem stack entfernt werden. Zur "Zwischenlagerung" soll ein weiterer stack dienen.


Ich würde mich wirklich sehr über schnelle, funktioniere Hilfe in Form von Java Programmen (Eclipse) freuen.

Vielen Dank im vorraus !

Mit freundlichen Grüßen,
Showtime

 

[OJIDASOAoidj]

Naja, ich werde dir mal ein paar Hilfestellungen geben.

Da du bestimmt schon etwas Erfahrung in Java hast erspare ich mir jetzt zu weit auszuschweifen.

Probiere es mal so:

Stelle dir einen Stack als Vector dh. variables Array vor, dass in einer Stappel form vorlieget. So nun hast du 2 Stacks. Ich würde es so machen indem ich einen Stack in ein Array transformiere mit .toArray Methode. Ein Stappel funktioniert mit dem "Als letztes rein, als erstes raus prinzip".
So mit einer for schleife addest du jetzt einzeln die Werte. Da es keine Beschränkungen gibt wie du vorgehen sollst würde ich aus dem großes Stack wieder ein Array machen und dann per Bubblesort oder whatever ordnen. Dazu steht in wikipedia allerdings mehr.

Die anzahl der elemente stack.size(); ??

Ich denke das muss genung sein für den Anfang.

Hier nochmal eine erklärung :


[OT]The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.[/OT]

 

[KranzKrone]

Nehme dir ein Kartenspiel und teile das Spiel in zwei ungleiche Stapel. Ein Stack ist genau ein Stapel, der genau die gleichen Eigenschaften, wie dein Kartenspiel verfügt.

Du kannst bei einem Stack die Karten nur von oben runternehmen, da es sonst kein Stack wäre. Das heißt du benötigts dazu eine Methode. Weiterhin brauchst du einen 3. Stapelplatz für deine Sortierung (das wäre der Speicherplatz im PC).

Das bedeutet du hast eine Klasse welche einen Stack verwaltet und eine Klasse welche die beiden Stackverwaltet und steuert. Weiterhin brauchst du eine Sortiermethode, hierzu würde ich dir Bubblesort empfehlen, da du den Quellcode, fast von Wikipedia bekommen kannst.

Ich vermutet das du noch nicht alle Elemente von Java kennst, deshalb würde ich die eine

ArrayList<Integer> stack1 = new ArrayList<Integer>();

empfehlen.

Um von oben zu nehmen, lässt du dir einfach die Größe der ArrayListe geben und rechnest diese minus 1 und hast genau die oberste Stelle deines Stapels (Stack).

Türme von Hanoi ist auch so eine Aufgabe aus dieser Richtung.

 

[Landei]

Weiterhin brauchst du eine Sortiermethode, hierzu würde ich dir Bubblesort empfehlen, da du den Quellcode, fast von Wikipedia bekommen kannst.

Nö, hierzu nicht. Die beiden Ausgangsstacks sind schon geordnet, man muss nur die Elemente so von oben wegnehmen und auf den neuen Stack legen, dass die Ordnung erhalten bleibt.

 

[xehpuk]

Ich gehe mal davon aus, dass die Klausur eh vorbei ist. Daher hier meine Lösung …

Da bei Aufgabe 1 explizit von Zahlen die Rede war, lasse ich ihn bei null-Elementen krachen.
Bei Aufgabe 3 hingegen habe ich null-Elemente erlaubt.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Stacktastic {
	private static <E extends Number & Comparable<E>> Stack<E> merge(final Stack<E> stack, final Stack<E> stack2) {
		final Stack<E> s = new Stack<E>(stack);
		final Stack<E> s2 = new Stack<E>(stack2);
		final Stack<E> temp = new Stack<E>();
		for (boolean empty, empty2; !((empty = s.isEmpty()) & (empty2 = s2.isEmpty()));) {
			if (empty) {
				temp.push(s2.pop());
			} else {
				if (empty2) {
					temp.push(s.pop());
				} else {
					if (s2.peek().compareTo(s.peek()) < 0) {
						temp.push(s2.pop());
					} else {
						temp.push(s.pop());
					}
				}
			}
		}
		final Stack<E> result = new Stack<E>();
		while (!temp.isEmpty()) {
			result.push(temp.pop());
		}
		return result;
	}
	
	private static <E> int size(final Stack<E> stack) {
		final Stack<E> s = new Stack<E>(stack);
		int result;
		for (result = 0; !s.isEmpty(); result++) {
			s.pop();
		}
		return result;
	}
	
	private static <E> void remove(final Stack<E> stack, final E e) {
		final Stack<E> temp = new Stack<E>();
		while (!stack.isEmpty()) {
			final E e2 = stack.pop();
			if (e == null) {
				if (e2 == null) {
					break;
				}
			} else {
				if (e.equals(e2)) {
					break;
				}
			}
			temp.push(e2);
		}
		while (!temp.isEmpty()) {
			stack.push(temp.pop());
		}
	}
	
	private static void aufgabe1() {
		final Random r = new Random();
		final List<Integer> data = new ArrayList<Integer>(), data2 = new ArrayList<Integer>();
		final Stack<Integer> stack = new Stack<Integer>(), stack2 = new Stack<Integer>();
		for (int i = 0, m = r.nextInt(10); i < m; i++) {
			data.add(r.nextInt(10));
		}
		for (int i = 0, m = r.nextInt(10); i < m; i++) {
			data2.add(r.nextInt(10));
		}
		Collections.sort(data, Collections.reverseOrder());
		Collections.sort(data2, Collections.reverseOrder());
		for (final Integer e : data) {
			stack.push(e);
		}
		for (final Integer e : data2) {
			stack2.push(e);
		}
		System.out.println("Aufgabe 1 (merge)");
		System.out.println("Stack 1: " + stack);
		System.out.println("Stack 2: " + stack2);
		System.out.println("Stack 3: " + merge(stack, stack2));
		System.out.println();
	}
	
	private static void aufgabe2() {
		final Random r = new Random();
		final Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0, m = r.nextInt(10); i < m; i++) {
			stack.push(i);
		}
		System.out.println("Aufgabe 2 (size)");
		System.out.println("Stack: " + stack);
		System.out.println("Größe: " + size(stack));
		System.out.println();
	}
	
	private static void aufgabe3() {
		final Random r = new Random();
		final Stack<Integer> stack = new Stack<Integer>();
		final int m = r.nextInt(10);
		for (int i = 0; i < m; i++) {
			stack.push(r.nextInt(10) == 0 ? null : i);
		}
		final int i = r.nextInt(m + 2);
		final Integer e = i == m + 1 ? null : i; 
		System.out.println("Aufgabe 3 (remove)");
		System.out.println("Stack  : " + stack);
		System.out.println("Element: " + e);
		remove(stack, e);
		System.out.println("Stack  : " + stack);
		System.out.println();
	}
	
	public static void main(String... args) {
		aufgabe1();
		aufgabe2();
		aufgabe3();
	}
}

Es wurde nicht erwähnt, um welchen Stack es sich handelt. Kann mir nicht vorstellen, dass damit [JAPI]java.util.Stack[/JAPI] gemeint war, da die Aufgaben dort wegen der sinnfreien Erweiterung von [JAPI]java.util.Vector[/JAPI] trivial gewesen wären.
Deswegen habe ich einen eigenen (der Einfachheit halber ohne Interface) geschrieben, der die gängigsten Methoden anbietet:

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class Stack<E> {
	private final List<E> data;
	
	public Stack() {
		this(new ArrayList<E>());
	}
	
	public Stack(final Stack<? extends E> source) {
		this(new ArrayList<E>(source.data));
	}
	
	private Stack(final List<E> data) {
		this.data = data;
	}
	
	public void push(final E e) {
		data.add(e);
	}
	
	public E pop() {
		try {
			return data.remove(data.size() - 1);
		} catch (final IndexOutOfBoundsException ioobe) {
			throw new NoSuchElementException();
		}
	}
	
	public E peek() {
		try {
			return data.get(data.size() - 1);
		} catch (final IndexOutOfBoundsException ioobe) {
			throw new NoSuchElementException();
		}
	}
	
	public boolean isEmpty() {
		return data.isEmpty();
	}
	
	@Override
	public String toString() {
		return data.toString();
	}
}