Assignment 7
The exercise
Suppose you want to implement two stacks using a single array. Two possibilities are outlined here:Odd-even strategy
In this case Stack 1 uses locations 0,2,4,... of the array, whereas Stack 2 uses the array locations 1,3,5,....Colliding strategy
In this case the two stacks start from the two ends of the array and grow in opposite directions (towards one another).
The following figure demonstrates these two strategies.
Implement both the strategies. Write two sets of initialize, push and pop routines. Show the output of your code on randomly generated sequences of requests. In order to have good-looking outputs, you may enforce the following:
- Keep the array size small, say, around 25.
- For the first few iterations do push only.
- Subsequently make push twice as likely as pop.
- Make the first stack twice more active (on an average) than the second.
You may rely on the randomness of C's built-in pseudorandom generator to ensure these statistical properties.
Don't print very big output files. Generate 4 runs of your program with a total size of less than 300 lines. Two runs should correspond to the odd-even strategy, the remaining two the colliding strategy.
Sample output
Enter strategy -- 0 (odd-even) or 1 (colliding) : 0 Iteration 1 : Push d in stack 1. New stack : d_______________________________ Iteration 2 : Push i in stack 1. New stack : d_i_____________________________ Iteration 3 : Push l in stack 1. New stack : d_i_l___________________________ Iteration 4 : Push h in stack 1. New stack : d_i_l_h_________________________ Iteration 5 : Push m in stack 1. New stack : d_i_l_h_m_______________________ Iteration 6 : Push q in stack 1. New stack : d_i_l_h_m_q_____________________ Iteration 7 : Push m in stack 1. New stack : d_i_l_h_m_q_m___________________ Iteration 8 : Push k in stack 1. New stack : d_i_l_h_m_q_m_k_________________ Iteration 9 : Push g in stack 1. New stack : d_i_l_h_m_q_m_k_g_______________ Iteration 10 : Push z in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_____________ Iteration 11 : Push i in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i___________ Iteration 12 : Push u in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i_u_________ Iteration 13 : Push q in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i_u_q_______ Iteration 14 : Pop in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i_u_________ Iteration 15 : Push u in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i_u_u_______ Iteration 16 : Push b in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i_u_u_b_____ Iteration 17 : Pop in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i_u_u_______ Iteration 18 : Push t in stack 1. New stack : d_i_l_h_m_q_m_k_g_z_i_u_u_t_____ Iteration 19 : Push F in stack 2. New stack : dFi_l_h_m_q_m_k_g_z_i_u_u_t_____ Iteration 20 : Push n in stack 1. New stack : dFi_l_h_m_q_m_k_g_z_i_u_u_t_n___ Iteration 21 : Pop in stack 1. New stack : dFi_l_h_m_q_m_k_g_z_i_u_u_t_____ Iteration 22 : Push N in stack 2. New stack : dFiNl_h_m_q_m_k_g_z_i_u_u_t_____ Iteration 23 : Pop in stack 1. New stack : dFiNl_h_m_q_m_k_g_z_i_u_u_______ Iteration 24 : Push z in stack 1. New stack : dFiNl_h_m_q_m_k_g_z_i_u_u_z_____ Iteration 25 : Pop in stack 1. New stack : dFiNl_h_m_q_m_k_g_z_i_u_u_______ Iteration 26 : Push f in stack 1. New stack : dFiNl_h_m_q_m_k_g_z_i_u_u_f_____ Iteration 27 : Push M in stack 2. New stack : dFiNlMh_m_q_m_k_g_z_i_u_u_f_____ Iteration 28 : Push t in stack 1. New stack : dFiNlMh_m_q_m_k_g_z_i_u_u_f_t___ Iteration 29 : Push S in stack 2. New stack : dFiNlMhSm_q_m_k_g_z_i_u_u_f_t___ Iteration 30 : Pop in stack 2. New stack : dFiNlMh_m_q_m_k_g_z_i_u_u_f_t___ Iteration 31 : Push l in stack 1. New stack : dFiNlMh_m_q_m_k_g_z_i_u_u_f_t_l_ Iteration 32 : Push a in stack 1. New stack : Error: Overflow in Stack 1. Enter strategy -- 0 (odd-even) or 1 (colliding) : 1 Iteration 1 : Push C in stack 2. New stack : _______________________________C Iteration 2 : Push u in stack 1. New stack : u______________________________C Iteration 3 : Push g in stack 1. New stack : ug_____________________________C Iteration 4 : Push w in stack 1. New stack : ugw____________________________C Iteration 5 : Push Q in stack 2. New stack : ugw___________________________QC Iteration 6 : Push b in stack 1. New stack : ugwb__________________________QC Iteration 7 : Push d in stack 1. New stack : ugwbd_________________________QC Iteration 8 : Push g in stack 1. New stack : ugwbdg________________________QC Iteration 9 : Pop in stack 1. New stack : ugwbd_________________________QC Iteration 10 : Push Z in stack 2. New stack : ugwbd________________________ZQC Iteration 11 : Pop in stack 1. New stack : ugwb_________________________ZQC Iteration 12 : Push h in stack 1. New stack : ugwbh________________________ZQC Iteration 13 : Pop in stack 1. New stack : ugwb_________________________ZQC Iteration 14 : Pop in stack 2. New stack : ugwb__________________________QC Iteration 15 : Push E in stack 2. New stack : ugwb_________________________EQC Iteration 16 : Push p in stack 1. New stack : ugwbp________________________EQC Iteration 17 : Push l in stack 1. New stack : ugwbpl_______________________EQC Iteration 18 : Push X in stack 2. New stack : ugwbpl______________________XEQC Iteration 19 : Push d in stack 1. New stack : ugwbpld_____________________XEQC Iteration 20 : Push b in stack 1. New stack : ugwbpldb____________________XEQC Iteration 21 : Push F in stack 2. New stack : ugwbpldb___________________FXEQC Iteration 22 : Pop in stack 1. New stack : ugwbpld____________________FXEQC Iteration 23 : Push p in stack 1. New stack : ugwbpldp___________________FXEQC Iteration 24 : Push y in stack 1. New stack : ugwbpldpy__________________FXEQC Iteration 25 : Push K in stack 2. New stack : ugwbpldpy_________________KFXEQC Iteration 26 : Push t in stack 1. New stack : ugwbpldpyt________________KFXEQC Iteration 27 : Push I in stack 2. New stack : ugwbpldpyt_______________IKFXEQC Iteration 28 : Push E in stack 2. New stack : ugwbpldpyt______________EIKFXEQC Iteration 29 : Push a in stack 1. New stack : ugwbpldpyta_____________EIKFXEQC Iteration 30 : Pop in stack 1. New stack : ugwbpldpyt______________EIKFXEQC Iteration 31 : Push l in stack 1. New stack : ugwbpldpytl_____________EIKFXEQC Iteration 32 : Pop in stack 1. New stack : ugwbpldpyt______________EIKFXEQC Iteration 33 : Pop in stack 2. New stack : ugwbpldpyt_______________IKFXEQC Iteration 34 : Push H in stack 2. New stack : ugwbpldpyt______________HIKFXEQC Iteration 35 : Push d in stack 1. New stack : ugwbpldpytd_____________HIKFXEQC Iteration 36 : Push c in stack 1. New stack : ugwbpldpytdc____________HIKFXEQC Iteration 37 : Push F in stack 2. New stack : ugwbpldpytdc___________FHIKFXEQC Iteration 38 : Push z in stack 1. New stack : ugwbpldpytdcz__________FHIKFXEQC Iteration 39 : Push h in stack 1. New stack : ugwbpldpytdczh_________FHIKFXEQC Iteration 40 : Push n in stack 1. New stack : ugwbpldpytdczhn________FHIKFXEQC Iteration 41 : Push x in stack 1. New stack : ugwbpldpytdczhnx_______FHIKFXEQC Iteration 42 : Push l in stack 1. New stack : ugwbpldpytdczhnxl______FHIKFXEQC Iteration 43 : Push F in stack 2. New stack : ugwbpldpytdczhnxl_____FFHIKFXEQC Iteration 44 : Pop in stack 2. New stack : ugwbpldpytdczhnxl______FHIKFXEQC Iteration 45 : Push i in stack 1. New stack : ugwbpldpytdczhnxli_____FHIKFXEQC Iteration 46 : Push i in stack 1. New stack : ugwbpldpytdczhnxlii____FHIKFXEQC Iteration 47 : Push u in stack 1. New stack : ugwbpldpytdczhnxliiu___FHIKFXEQC Iteration 48 : Push z in stack 1. New stack : ugwbpldpytdczhnxliiuz__FHIKFXEQC Iteration 49 : Push o in stack 1. New stack : ugwbpldpytdczhnxliiuzo_FHIKFXEQC Iteration 50 : Push j in stack 1. New stack : ugwbpldpytdczhnxliiuzojFHIKFXEQC Iteration 51 : Pop in stack 1. New stack : ugwbpldpytdczhnxliiuzo_FHIKFXEQC Iteration 52 : Push V in stack 2. New stack : ugwbpldpytdczhnxliiuzoVFHIKFXEQC Iteration 53 : Push i in stack 1. New stack : Error: Overflow in stack. Enter strategy -- 0 (odd-even) or 1 (colliding) : 1 Iteration 1 : Push k in stack 1. New stack : k_______________________________ Iteration 2 : Push P in stack 2. New stack : k______________________________P Iteration 3 : Push g in stack 1. New stack : kg_____________________________P Iteration 4 : Push z in stack 1. New stack : kgz____________________________P Iteration 5 : Push l in stack 1. New stack : kgzl___________________________P Iteration 6 : Push w in stack 1. New stack : kgzlw__________________________P Iteration 7 : Push u in stack 1. New stack : kgzlwu_________________________P Iteration 8 : Push o in stack 1. New stack : kgzlwuo________________________P Iteration 9 : Pop in stack 1. New stack : kgzlwu_________________________P Iteration 10 : Pop in stack 2. New stack : kgzlwu__________________________ Iteration 11 : Push i in stack 1. New stack : kgzlwui_________________________ Iteration 12 : Pop in stack 1. New stack : kgzlwu__________________________ Iteration 13 : Pop in stack 1. New stack : kgzlw___________________________ Iteration 14 : Pop in stack 2. New stack : Error: Underflow in Stack 2.