CODEWITHSUNDEEP
data-structures
Alex
Alex

Reputation: 12079

Which data structure to use as Stack with random position insertion ability?

Card game, where used cards go back to the deck, but are not inserted of the bottom, but at a random position within the 2nd half of the deck.

Such as given a deck with cards [c5, c6, c7, c8, c9] the next pop operation should return c5, and after c5 is used, it should be reinserted into the deck within the 2nd half,
ie before c8 OR after c8 Or after c9

How would you design an efficient data structure for this deck?

Amount of cards is constant

Upvotes: 2

Views: 194

Answers (1)

Gene
Gene

Reputation: 47010

If the number of cards is really always 52, then an array makes a fine data structure. Since the number of elements is constant, all operations are constant time. Moving elements in consecutive memory locations is extremely fast in modern systems. You'll have a hard time doing better with a more sophisticated data structure.

If the number of cards can vary arbitrarily, I suggest a an order statistic tree. In such trees, each node tracks the number of nodes in the subtree of which it is the root. This enables insertion and removal at any ordinal position. Effectively, this gives you an array where insertion and removal are O(log n) it the tree is balanced.

Happily since you are re-inserting randomly, you get expected O(log n) performance "for free" if you initially create a balanced tree for the deck. If you want worst case O(log n), you can make the tree self-balancing (red-black, AVL, etc.).

To deal from the top of the deck, remove position 0. To re-insert, pick a random number in 0-51, and insert at that ordinal position.

Upvotes: 3

Related Questions