Question

Create a stack S with 13 elements by using 4220145971536. Consider an empty queue Q, remove the elements one-by-one from S and insert them into Q, then remove them oneby-one from Q and re-insert them into S. Finally, show the elements of S (from top to bottom). Show all the steps.

Answer 1

Solution:

Given,

=>Stack S with size = 13

=>Elements = 4, 2, 2, 0, 1, 4, 5, 9, 7, 1, 5, 3, 6

=>Queue Q

Explanation:

Initially:

Stack S:

6
3
5
1
7
9
5
4
1
0
2
2
4

top = 12

Queue Q:

0 1 2 3 4 5 6 7 8 9 10 11 12

front = rear = -1

=>top pointer in stack is used for inserting and removing the elements.

=>front pointer is used for inserting the elements into the queue and rear pointer is used for removing the elements from the queue.

Step 1:

=>pop off element 6 from stack and inert into the queue.

Stack S:

3
5
1
7
9
5
4
1
0
2
2
4

top = 11

Queue Q:

6

   0 1   2 3 4 5 6 7 8 9 10 11 12

front = rear = 0 as it is first insertion.

Step 2:

=>Pop off element 3 from stack and insert into queue.

Stack S:

5
1
7
9
5
4
1
0
2
2
4

top = 10

Queue Q:

6

3

    0 1 2 3 4 5 6   7 8 9   10 11 12

front = 1 and rear = 0

and so on.

Final step:

Stack S:

top = -1

Queue Q:

6

3

5

1

7

9

5

4

1

0

2

2

4

0 1 2 3 4 5 6 7 8 9 10 11 12

front = 12 and rear = 0

Now removing the elements from queue and insert into stack S:

Step 1:

=>Remove element 6 from Q and insert into the stack S.

Queue Q:

3

5

1

7

9

5

4

1

0

2

2

4

0 1 2 3 4 5 6 7 8 9 10 11 12

front = 12 and rear = 1

Stack S:

6

top = 0

Step 2:

=>Remove element 3 form queue Q and insert into stack S.

Queue Q:

5

1

7

9

5

4

1

0

2

2

4

0 1 2 3 4 5 6 7 8 9 10 11 12

front = 12 and rear = 2

Stack S:

3

6

top = 1

and so on

Final step:

Queue Q:

0 1 2 3 4 5 6 7 8 9 10 11 12

front = rear = -1 for last deletion.

Stack S:

4
2
2
0
1
4
5
9
7
1
5
3
6

top = 12

=>Elements of stack S from top to bottom = 4, 2, 2, 0, 1, 4, 5, 9, 7, 1, 5, 3, 6

I have explained each and every part with the help of statements attached to it.