[Java/C++] Fronta pomocí zásobníku a opačně

[Anduril]

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

[viki_]

Trosku tomu mozna nerozumim, ja myslel ze fronta a zasobnik maji trosku odlisne pouziti, tak proc by se melo konstruovat jedno z druheho

[viki_]

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)

[Anduril]

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í)!

[viki_]

Jeste ze uz nechodim do skoly

[Glottis]

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

[viki_]

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

[Rainbow]

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

[sisi]

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

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...

[Anduril]

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

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...

Je to kravina... tady to je (JAVA).
Dělal jsem to včera v noci, takže tam jsou možná nějaké chyby/nesmysly

Fronta pomocí dvou zásobníků:

// 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&#40; m_sp<=0 &#41;;
  &#125;  

  // Získání 1. hodnoty na řadě v zásobníku
  public int Test&#40;&#41;
  &#123;
    if&#40; IsEmpty&#40;&#41; &#41; return&#40; -1 &#41;;

    return&#40; m_array&#91;m_sp-1&#93; &#41;;
  &#125;

  // Vymazání zásobníku  
  public void Reset&#40;&#41;
  &#123;
    while&#40; !IsEmpty&#40;&#41; &#41;
      Pop&#40;&#41;; 
  &#125;
&#125;

// CStackQueue
// fronta implementovaná pomocí dvou zásobníků
public class CStackQueue
&#123;
  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&#40;&#41;
  &#123;
    if&#40; m_cur==1 &#41; &#123;
      m_stack2.Reset&#40;&#41;;
      while&#40; !m_stack1.IsEmpty&#40;&#41; &#41; &#123;
        m_stack2.Push&#40; m_stack1.Pop&#40;&#41; &#41;;
      &#125;
      m_cur = 2;
    &#125;
    else &#123;
      m_stack1.Reset&#40;&#41;;
      while&#40; !m_stack2.IsEmpty&#40;&#41; &#41; &#123;
        m_stack1.Push&#40; m_stack2.Pop&#40;&#41; &#41;;
      &#125;
      m_cur = 1;
    &#125;
  &#125;

  // Konstruktor
  // size = velikost fronty &#40;resp. zásobníků&#41;
  public CStackQueue&#40; int size &#41;
  &#123;
    m_stack1 = new CStack&#40; size &#41;;
    m_stack2 = new CStack&#40; size &#41;;
    m_cur = 1;
  &#125;

  // Vložení hodnoty do fronty
  public void Insert&#40; int value &#41;
  &#123;
    if&#40; m_cur!=1 &#41; RecastStacks&#40;&#41;;
    
    m_stack1.Push&#40; value &#41;;
  &#125;
 
  // Výběr hodnoty z fronty
  public int Remove&#40;&#41;
  &#123;
    if&#40; m_cur!=2 &#41; RecastStacks&#40;&#41;;
    
    return&#40; m_stack2.Pop&#40;&#41; &#41;;    
  &#125;

  // Test prázdnosti fronty
  public boolean IsEmpty&#40;&#41;
  &#123;
    if&#40; m_cur==1 &#41; return&#40; m_stack1.IsEmpty&#40;&#41; &#41;;
    else return&#40; m_stack2.IsEmpty&#40;&#41; &#41;;
  &#125;

  // Vymazání fronty
  public void Reset&#40;&#41;
  &#123;
    m_stack1.Reset&#40;&#41;;
    m_stack2.Reset&#40;&#41;;
    m_cur = 1;
  &#125;

  // Test 1. hodnoty ve frontě
  public int Test&#40;&#41;
  &#123;
    if&#40; m_cur!=2 &#41; RecastStacks&#40;&#41;;
    
    return&#40; m_stack2.Test&#40;&#41; &#41;;        
  &#125;
&#125;

// Test
public class Test
&#123;
  public static void main&#40; String&#91;&#93; args &#41;
  &#123;
    CStackQueue sq = new CStackQueue&#40; 10 &#41;;
    
    sq.Insert&#40; 1 &#41;;
    sq.Insert&#40; 2 &#41;;
    sq.Insert&#40; 3 &#41;;
    sq.Insert&#40; 4 &#41;;
    sq.Insert&#40; 5 &#41;;
    
    System.out.println&#40; "Test fronty &#40;1. prvek na rade&#41;&#58; " + sq.Test&#40;&#41; &#41;;
    sq.Remove&#40;&#41;;
    System.out.println&#40; "Test fronty &#40;1. prvek na rade&#41;&#58; " + sq.Test&#40;&#41; &#41;;

    sq.Insert&#40; 6 &#41;;

    while&#40; !sq.IsEmpty&#40;&#41; &#41;
      System.out.println&#40; "> " + sq.Remove&#40;&#41; &#41;;

  &#125;
&#125;

Zásobník pomocí dvou front:

// 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() );    
  }
}

[viki_]

Jen mala poznamka - nazvy metod by mely vzdy zacinat malym pismenem (je to respektovana konvence - velkym nazvy trid)

[Anduril]

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.
Já jsem to vždy psal velkým - ve škole nás to taky tak učí..

[viki_]

viz http://java.sun.com/docs/codeconv/ht....doc8.html#367