How can we understand what data structure is needed? [closed]

Question

Suppose I am trying to design an algorithm to solve a problem.

How should I proceed?

How can I understand what data structure is appropriate to solve my problem?

When trying to design an algorithm to evaluate an infix expression I thought it would be appropriate to use two stacks to solve the problem. But later I found that tree is needed to do the job.

How did the implementer come to know that tree would be appropriate?

Answer 1

There's no rule of thumb. For your particular problem a completely new data structure might be needed. This often happens in AI problems, which is why Lisp was such a handy language because it was easy to construct new data structures from lists. (or actually s-expressions, which are equivalent to trees).

But most problems you encounter in the working world are much more mundane, and can easily be solved with a standard data structure. After a while you begin to associate certain problems with certain solutions (get something fast? a hash table. get something fast but also have some ordering requirements? a tree) and can decompose a more complex problem into simpler components that can be solved with these type of standard data structures.