I implement manually stack and queue. What would be more efficient to use to store elements, an array or a vector?

  • one
    What does it mean more effectively? Determine exactly. For the effectiveness of different operations are suitable different supporting data structures. And yes, there is no such one trump data structure that would be more effective than all others for the implementation of the stack and the queue in all aspects. So roll out your performance criteria. - VladD

2 answers 2

The question without reference to the language is abstract. First you need to implement the stack, then the queue can be made on 2 stacks (but not needed). The stack can be implemented on anything that can painlessly expand, the array cannot be expanded, you have to create a new copy of the elements and delete the old one. In essence, the vector does the same ...

Therefore, the answer is a vector, if the profiler shows a bottleneck in it, then rewrite it into arrays and do a manual re-allocation (not the fact that it will be faster, you need to do everything carefully). If it is possible to limit the stack size from above to some acceptable value, then there is no difference. Or an array or vector immediately stretch.

    Performance comparison article: http://microfork.com/stdvector-stdlist-stdqueue-preformance-analisys/

    For self-implementation: use a profiler, and test on your real data and in your applications . At a minimum, one should take into account the work of the processor cache (allocate memory by pages, group frequently used data into adjacent memory areas, prefetch if it is possible to predict data usage) and features of SMP operation.

    And it depends on the size and variation of the size of your data: for example, if you work with a dataset of no more than N Mb (and less RAM / k is guaranteed), it will be most effective to immediately allocate the maximum memory with one block to the classic shared array, and implement the stack / queue on it (not forgetting to use data alignment in memory).