C++

Forum

 
Amortized Analysis

closed account (G3AqfSEw)
It is possible to implement a deque using two stacks stack1 and stack2, by implementing the functions in the following manner:

pushback (x): push x on stack1.
pushfront (x): push x on stack2.
popfront (): if stack2 is not empty, then pop from it. Otherwise, pop the entire contents of stack1, pushing each one onto stack2. Now pop from stack2.
popback (): if stack1 is not empty, then pop from it. Otherwise, pop the entire contents of stack2, pushing each one onto stack1. Now pop from stack1.

1
2
3
4
5
6
7
8
9
10
11
 
Part (a)
Starting with an empty deque, indicate the contents of stack1 and stack2 after each of the following operations have occurred. Clearly indicate the top and bottom of each stack:

pushback (1)
pushback (2)
popfront ()
pushfront (3)
pushfront (4)
popback ()
pushfront (5)
pushback (6)


1
2
 
Part (b)
What is the worst-case runtime of each of the four functions listed above in the 2-stack implementation?


1
2
 
Part (c)
What is the amortized runtime per function call, if a user is not allowed to use popfront? What is the amortized runtime per function call, if a user is not allowed to use popback?


1
2
 
Part (d)
What sequence of operations can lead to a very poor amortized runtime, when all four functions given above can be used? What is the amortized runtime per function call?
Repeater (3046)
Well, what did you get for the first question?

Starting with an empty deque, indicate the contents of stack1 and stack2 after each of the following operations have occurred. Clearly indicate the top and bottom of each stack:

pushback (1)


What's the answer to that bit? Can you get that far?
closed account (G3AqfSEw)
This is what I got for part a. Is this correct?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
pushback (1)
   stack1 (1) stack2 ()
pushback (2) 
   stack1 (1, 2) stack2 ()
popfront ()
   stack1 (1, 2) stack2 (1, 2)
pushfront (3)
   stack1 (1, 2) stack2 (1, 2, 3)
pushfront (4)
   stack1 (1, 2) stack2 (1, 2, 3, 4)
popback ()
   stack1 (2, 1) stack2 (1, 2, 3, 4)
pushfront (5)
   stack1 (2, 1) stack2 (1, 2, 3, 4, 5)
pushback (6)
   stack1 (2, 1, 6) stack2 (1, 2, 3, 4, 5)
Repeater (3046)
popfront ()
stack1 (1, 2) stack2 (1, 2)


That's the first error.
closed account (G3AqfSEw)
1
2
3
4
5
6
 
pushback (1)
   stack1 (1) stack2 ()
pushback (2) 
   stack1 (1, 2) stack2 ()
popfront ()
   stack1 () stack2 (2)


When it says pop the entire contents of stack1, does all of stack1 go to stack2 and stack1 becomes empty? and then first element is popped from stack2?
Topic archived. No new replies allowed.