Je to kravina... tady to je (JAVA).Původně odeslal sisi
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...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
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() ); } }
Odpověď s citací