# Algorithmen und Datenstrukturen, Blatt 6

## Aufgabe 1

### Aufgabe 1a)

7,6,5,4,3,2,1 $\rightarrow$ 7,3,4,5,6,1,2

Im Stack ist diese Rangiermöglichkeit durchführbar
Hier für geht man folgendermaßen vor:
1 $\rightarrow$ Stack
2 $\rightarrow$ nach rechts
1 $\rightarrow$ nach rechts
3 $\rightarrow$ Stack
4 $\rightarrow$ Stack
5 $\rightarrow$ Stack
6 $\rightarrow$ nach rechts
5 $\rightarrow$ nach rechts
4 $\rightarrow$ nach rechts
3 $\rightarrow$ nach rechts
7 $\rightarrow$ nach rechts

Bei der Queue ist dies nicht möglich: man würde zunächst folgendermaßen vorgehen
1 $\rightarrow$ Spur
2 $\rightarrow$ Überholspur, nach rechts
1 $\rightarrow$ nach rechts
5,4,3 $\rightarrow$ Spur
6$\rightarrow$ Überholspur nach rechts

Als nächstes müsste die Reihenfolge der Waggons 5,4,3 verändert werden.
Diese befinden sich allerding in der Spur der Queue und somit ist es nicht möglich,
die Reihenfolge wie vorgegeben aufzustellen.

### Aufgabe 1b)

7,6,5,4,3,2,1 $\rightarrow$ 6,3,7,2,1,5,4
Mit dem Stack ist diese Reihenfolge nicht möglich.
Man würde zunächst wie folgt vorgehen:
3,2,1 $\rightarrow$ Stack
5,4 $\rightarrow$ nach rechts
Als nächstes müsste Waggon 1 nach rechts.
Dieser befindet sich jedoch ganz unten im Stack und
ist deshalb nicht vor den Waggons 2 und 3 sichtbar.

Mit der Queue ist diese Reihenfolge wie folgt zu erreichen:

3,2,1 $\rightarrow$ Spur
5,4 $\rightarrow$ Überholspur, nach rechts
2,1 $\rightarrow$ nach rechts
6 $\rightarrow$ Spur
7 $\rightarrow$ Überholspur, nach rechts
6,3 $\rightarrow$ nach rechts

## Aufgabe 2

### Aufgabe 2a)

class StakaQueue 

stack <x> stack1 (s1)
stack <x> stack2 (s2)

enqueue (x y)
 while( s1 not empty)
     s2.push(s1.pop)
 s1.push(y)
 while(s2 not empty)
     s1.push(s1.pop)

x dequeue()
    if(s2.isEmpty)
        while(s2 not empty)
            s2.push(s1.pop())
    return s2.pop()

### Aufgabe 2b)

class QueueAStack
    Queue <x> q1
    Queue <x> q2
    int size
    
    stack()
        size=0
   
   push( x item)
       size++
       q2.add (item)
       while(q2 ist not empty)
           q2.add(q1.peek())
           q1.remove()
        Queue<x>q >q1
        q1=q2
        q2=q
        
    pop()
        if(q1 is empty)
            return
        q1.remove
        size--
        
    x top()
        if(q1 is empty)
            return null
        return q1.peek()
    
    int size()
        return size

### Aufgabe 2c)

class Katze
    Stack <int> s1
    Stack <int> s2 // maxStack
    
    newPush(int x)
        s1.push
        if(x >= s2)
            s2.push
        
    newPop()
        if (s1.peek==s2.peek)
            s2.pop()
        else s1.pop
    
    int findMax()
        if(s2 is empty)
            return null
        else 
            return s2.peek()

###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`