Potřebuju poradit (dobrovolný úkol do školy), jak vytvořit frontu pomocí zasobníku (resp. zasobníků) a zasobník pomocí fronty (resp. front)... Neví někdo? - stačí teoretický návrh
Printable View
Potřebuju poradit (dobrovolný úkol do školy), jak vytvořit frontu pomocí zasobníku (resp. zasobníků) a zasobník pomocí fronty (resp. front)... Neví někdo? - stačí teoretický návrh
Trosku tomu mozna nerozumim, ja myslel ze fronta a zasobnik maji trosku odlisne pouziti, tak proc by se melo konstruovat jedno z druheho ???
Jinak v Jave je to uz hotove - viz trida Stack, ktera je potomkem Vectoru a s Vectorem neni zadny problem zachazet jako s frontou (lepsi nez Vector ale bude pouzit LinkedList, ten je na to lepe optimalizovany)
Jasně - ja vím jak udělat zásobník/frontu pomocí pole, seznamu (list).. Problém je ale ten, že mám za úkol udělat frontu/zásobník pomocí zásobníku/fronty - úkol do Základů Algoritmizace (takže nějaké hotové věci mě nezajímají)!
Jeste ze uz nechodim do skoly :-) :-) :-)
mno zasobnik a fronta totez jest, rozdil je odkud beru prvky kdzy vkladam na vrchol
nevim jak mas tu frontu nebo zasobnik nadefinovanou nebo kdo ji psal tak tezke radit
Anduril: Kdyz ale nechces pouzit ani pole ani list, tak teda nevim jak to chces vubec resit ? Snad ne vymyslet nejakou hruzu ze zretezenych objektu jako ma treba binarni strom ? :) Stejne nekonec vymyslis neco hodne podobneho, jako je List :)
S jednym zasobnikom to urcite neurobis (pokial s nim budes pracovat len ako so zasobnikom, tzn. operacie push a pop). S dvomi by to uz islo - pridanie do fronty = push do 1. zasobnika. Vyber z fronty = pop vsetko z 1. zasobnika a push do druheho, posledny prvok -> vysledok. Potom zasa vsetko pop z 2. zasobnika a push do prveho. Tomu sa hovori efektivne programovanie :lol:
Presne tak ako hovori Rainbow... Analogicky sa da pomocou dvoch front simulovat jeden zasobnik. Ale je to neuveritelna *KRAVINA* - naozaj nechapem, co tym moze niekto z pedagogickeho hladiska sledovat...Citace:
Původně odeslal Rainbow
Je to kravina... tady to je (JAVA).Citace:
Původně odeslal sisi
Dělal jsem to včera v noci, takže tam jsou možná nějaké chyby/nesmysly ;-)
Fronta pomocí dvou zásobníků:
Kód:// CStack
// klasický zásobník
public class CStack
{
private int[] m_array;
private int m_sp;
// Konstruktor
public CStack( int size )
{
m_array = new int[size];
m_sp = 0;
}
// Vložení hodnoty do zásobníku
public boolean Push( int value )
{
if( m_sp>=m_array.length ) return( false );
m_array[m_sp++] = value;
return( true );
}
// Výběr hodnoty ze zásobníku
public int Pop()
{
if( IsEmpty() ) return( -1 );
return( m_array[--m_sp] );
}
// Test prázdnosti zásobníku
public boolean IsEmpty()
{
return( m_sp<=0 );
}
// Získání 1. hodnoty na řadě v zásobníku
public int Test()
{
if( IsEmpty() ) return( -1 );
return( m_array[m_sp-1] );
}
// Vymazání zásobníku
public void Reset()
{
while( !IsEmpty() )
Pop();
}
}
// CStackQueue
// fronta implementovaná pomocí dvou zásobníků
public class CStackQueue
{
CStack m_stack1; // zásobník 1 - vkládání dat
CStack m_stack2; // zásobník 2 - výběr dat
int m_cur; // aktivní zásobník
// Přelití zásobníků
private void RecastStacks()
{
if( m_cur==1 ) {
m_stack2.Reset();
while( !m_stack1.IsEmpty() ) {
m_stack2.Push( m_stack1.Pop() );
}
m_cur = 2;
}
else {
m_stack1.Reset();
while( !m_stack2.IsEmpty() ) {
m_stack1.Push( m_stack2.Pop() );
}
m_cur = 1;
}
}
// Konstruktor
// size = velikost fronty (resp. zásobníků)
public CStackQueue( int size )
{
m_stack1 = new CStack( size );
m_stack2 = new CStack( size );
m_cur = 1;
}
// Vložení hodnoty do fronty
public void Insert( int value )
{
if( m_cur!=1 ) RecastStacks();
m_stack1.Push( value );
}
// Výběr hodnoty z fronty
public int Remove()
{
if( m_cur!=2 ) RecastStacks();
return( m_stack2.Pop() );
}
// Test prázdnosti fronty
public boolean IsEmpty()
{
if( m_cur==1 ) return( m_stack1.IsEmpty() );
else return( m_stack2.IsEmpty() );
}
// Vymazání fronty
public void Reset()
{
m_stack1.Reset();
m_stack2.Reset();
m_cur = 1;
}
// Test 1. hodnoty ve frontě
public int Test()
{
if( m_cur!=2 ) RecastStacks();
return( m_stack2.Test() );
}
}
// Test
public class Test
{
public static void main( String[] args )
{
CStackQueue sq = new CStackQueue( 10 );
sq.Insert( 1 );
sq.Insert( 2 );
sq.Insert( 3 );
sq.Insert( 4 );
sq.Insert( 5 );
System.out.println( "Test fronty (1. prvek na rade): " + sq.Test() );
sq.Remove();
System.out.println( "Test fronty (1. prvek na rade): " + sq.Test() );
sq.Insert( 6 );
while( !sq.IsEmpty() )
System.out.println( "> " + sq.Remove() );
}
}
Zásobník pomocí dvou front:
Kód:// CQueue
// klasická fronta implementovaná pomocí dynam. struktur
public class CQueue
{
CQueueItem m_head;
CQueueItem m_tail;
// Konstruktor
public CQueue()
{
m_head = m_tail = null;
}
// Vložení hodnoty do fronty
public void Insert( int data )
{
CQueueItem n = new CQueueItem( data );
if( IsEmpty() )
m_head = n;
else
m_tail.next = n;
m_tail = n;
}
// Vybrání hodnoty z fronty
public int Remove()
{
CQueueItem n;
int ret = -1;
if( !IsEmpty() ) {
n = m_head;
m_head = m_head.next;
ret = n.data;
n = null;
}
return( ret );
}
// Test prázdnosti fronty
public boolean IsEmpty()
{
return( m_head==null );
}
// Zjištění hodnoty prvku fronty, který je nařadě
public int Test()
{
if( !IsEmpty() )
return( m_head.data );
else
return( -1 );
}
// Vymazání fronty
public void Reset()
{
while( m_head!=null )
{
m_tail = m_head;
m_head = m_head.next;
m_tail = null;
}
}
}
// CQueueItem
// jeden prvek fronty CQueue
public class CQueueItem
{
int data;
CQueueItem next;
public CQueueItem( int value )
{
data = value;
next = null;
}
}
// CQueueStack
// Zásobník implementovaný pomocí 2 front
public class CQueueStack
{
CQueue m_queue1;
CQueue m_queue2;
int m_cur;
// Konstruktor
public CQueueStack()
{
m_queue1 = new CQueue();
m_queue2 = new CQueue();
m_cur = 1;
}
// Vložení hodnoty do zásobníku
public void Push( int value )
{
if( m_cur==1 ) {
m_queue1.Insert( value );
}
else {
m_queue2.Insert( value );
}
}
// Vybrání zásobníku
public int Pop()
{
int last = -1;
if( IsEmpty() ) return( -1 );
if( m_cur==1 ) {
m_queue2.Reset();
while( !m_queue1.IsEmpty() )
{
last = m_queue1.Remove();
if( m_queue1.IsEmpty() ) break;
else m_queue2.Insert( last );
}
m_cur = 2;
}
else {
m_queue1.Reset();
while( !m_queue2.IsEmpty() )
{
last = m_queue2.Remove();
if( m_queue2.IsEmpty() ) break;
else m_queue1.Insert( last );
}
m_cur = 1;
}
return( last );
}
// Test prázdnosti zásobníku
public boolean IsEmpty()
{
if( m_cur==1) return( m_queue1.IsEmpty() );
else return( m_queue2.IsEmpty() );
}
// Vymazání zásobníku
public void Reset()
{
m_queue1.Reset();
m_queue2.Reset();
m_cur = 1;
}
}
// Test
public class Test
{
public static void main( String[] args )
{
CQueueStack qs = new CQueueStack();
qs.Push( 1 );
qs.Push( 2 );
qs.Push( 3 );
System.out.println( "> " + qs.Pop() );
System.out.println( "> " + qs.Pop() );
System.out.println( "--" );
qs.Push( 4 );
while( !qs.IsEmpty() )
System.out.println( "> " + qs.Pop() );
qs.Push( 1 );
qs.Push( 2 );
qs.Push( 3 );
System.out.println( "--" );
while( !qs.IsEmpty() )
System.out.println( "> " + qs.Pop() );
}
}
Jen mala poznamka - nazvy metod by mely vzdy zacinat malym pismenem (je to respektovana konvence - velkym nazvy trid)
V Javě - to možná jo... Jinak je to myslím jedno.Citace:
Původně odeslal viki_
Já jsem to vždy psal velkým - ve škole nás to taky tak učí..