Design a stack that can also dequeue in O(1) amortized time?

Question

I have an abstract data type that can be viewed as a list stored left to right, with the following possible operations: Push: add a new item to the left end of the list Pop: remove the item on the left end of the list Pull: remove the item on the right end of the list

Implement this using three stacks and constant additional memory, so that the amortized time for any push, pop, or pull operation is constant. The stacks have basic operations, isEmpty, Push, and Pop.

Amortized time means "If I spend this amount of time, I can spend another block of it and store it in a bank of time to be used later." like for each push operation, spend three blocks of constant time, so for every element pushed, you have 2 extra blocks of constant time.

Answer 1

Use a doubly-linked list and keep pointers to the head and tail. For the rest, you need to write your own code first and then let us help you correct it.

Answer 2

You could do something which uses only the 3 stacks. Think tower of Hanoi.

Answer 3

Making a few assumptions:

1. That this is homework
2. That this paragraph is part of the assignment

Implement this using three stacks and constant additional memory, so that the amortized time for any push, pop, or pull operation is constant. The stacks have basic operations, isEmpty, Push, and Pop.

Then my first advice would be to ignore the people talking to you about linked lists. True, that's how any reasonable person would implement it without the three stack requirement, but the key factor in homework isn't to do it the way a reasonable person would, but rather how your instructor wants you to.

My second bit of advice would be to get some blocks, a deck of cards, or a bunch of styrofoam cups and designate three stacks (e.g. with coasters or something). Start playing around with what happens when you transfer the contents of one stack to another, and that should give you an idea.

Answer 4

Start by implementing a queue in terms of two stacks (a pretty standard problem) and generalize.