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