Problem 3. a) Describe the output of the following series of stack operations on

Question

Problem 3. a) Describe the output of the following series of stack operations on a single, initially empty stack: push(5), push(3), pop(), push(2), push(8), pop0, push(9), push(1), pop), push(7), push(6), pop), popO, push(4), pop), pop b) Describe the output of the following series of queue operations on a single, initially empty queue: engueue(5), enqueue(G3), dequeue0, enqueue(2), enqueue(8), dequeue), enqueue(9, enqueue(1), dequeue), enqueue(7), enqueue(6), dequeue), dequeue), enue(4), dequeue), dequeue). dequeue), enqueue(2), enqueue(8), dequeue), enqueue(9), c) Describe in pseudo-code a linear-time algorithm for creating a copy stack S' of a stack S. As the result, you must end up with two identical stacks S and S. To access the stack, you are only allowed to use the methods of stack ADT. d) Describe how to implement two stacks using one array. The total number of elements in both stacks is limited by the array length; ll stack operations should run in O(1) time.

Explanation / Answer

a) push(6)

now stack will have 6

push(3) now stack will have 6,3

pop() now 3 will be deleted from the stack since it follows lifo order

push(2) now stack will have 6,2

push(8) now stack will have 6,2,8

pop() since top element is 8 it pops() 8 from the stack

push(9) inserts 9 into stack now stack wil have 6,2,9

push(1) inserts 1 into stack now stack wil have 6,2,9,1

pop() deletes 1 from stack

push(7) inserts 7 into stack and now stack has 6,2,9,7

push(6) inserts 6 into stack and now stack has 6,2,9,7,6

pop() deletes 6 from stack

pop() deletes 7 from stack

push(4) inserts 4 into stack and stack has 6,2,9,4

pop() deletes 4 from stack

pop() deletes 9 from stack

now stack will be left with 6 and 2

output eill be: 3,8,1,6,7,4,9

b)queue will follow FIFO so deletion will be done from starting

enqueue(5) inserts 5 into queue queue contents 2

enqueue(3) inserts 3 into queue queue contents 2,3

dequeue() deletes 2 and queue contents 3

enqueue(2) inserts 2 into queue queue contents 3,2

enqueue(8) inserts 5 into queue queue contents 3,2,8

dequeue() deletes 3 from queue and queue contents are 2,8

enqueue(9) inserts 9 into queue queue contents 2,8,9

enqueue(1) inserts 1 into queue queue contents 2,8,9,1

dequeue() deletes 2 from queue and queue has contents 8,9,1

enqueue(7) inserts 7 into queue queue contents 8,9,1,7

enqueue(6) inserts 6 into queue queue contents 8,9,1,7,6

dequeue() deletes 8 from queue and queue contents will be 9,1,7,6

dequeue() deletes 9 from dequeue and queue contents will be 1,7,6

enqueue(4) inserts 4 into queue queue contents 1,7,6,4

dequeue() deletes 1 from queue and stack will have 7,6,4

dequeue()deletes 7 from queue now queue will have 6,4

Output: 2,3,2,8,9,1,7

c)Begin

Stack s1,s2;

top1=0;

arr[top];//top is the nu,ber of elements in stack 1

i=0;

while S1 is not Empty //emptying the stack 1 and storing in array

arr[i++]=s1.pop();

End While

for j:i-1 to 0//whiel emptying the array elements will be stored in reverse order do traversing from n-1 th index to zero and storing in S2

S2[top1++]=arr[j];

end for

for j:0 to i-1//again filling the stack s1

S1[top1++]=arr[j];

end for

End

d)we can implement two stacks using one array by dividing it into two equal halves and while inserting starting from 0th index of array for one stack and starting from ending of array for another for stack operations will result in an 0(1) operations time for both the stacks.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.