What is a Stack, Queue, Vector, Array and List? [closed]

Question

I was introduced to array. Than list. Than vector. Than stack and queue. They can all contain certain type of memory. But than why is there so many of them?

I read that list is better when adding or deleting, and when doing other things, vector is better. But what are stack and queue? What about std::array?

Is there any good and kind programmer who can (simply or specifically) explain differences, pros, cons, and when to use these different containers?

Answer 1

These are different data structures that you are talking about. Why are we using different ones then? The reason for this is that different data structures are good at different things.

Data structures differ from themselves by relationships between their elements, and the actions that can be done on the data structure.

Different operations on different data structures can have a different complexity. A complexity is a measure of how much the number of operations grow by an increase in the amount of data.

Since your question is about C++, I will talk about 2 data structures: vector and list. There is one more sequential container - deque, which is similar to a vector, the major difference is that operations such as inserting an element at the front are much faster.

Vector

This is a really useful data structure that is an auto growing array. Since an array is stored in a continuous chunk of memory, some operations are less computation intensive than others.

Let's look at the operations that we can do on a vector.

Element access

Since all elements are in a continuous chunk of memory, getting the nth element is O(1).

Adding to the end

If we have space left, and we know the size of the vector, this operation is O(1). If we do not have space, we need to allocate more space, and copy all the data to the new space. This is O(n), but this happens rarely.

Insert and Removal

This involves moving all the elements after the place of inserting to the right. This is O(n)

List

This structure has some advantages over a vector. The elements are not in a continuous chunk of memory, which makes the insert operations much faster.

Element access

To get to the nth element, you have to go through each list node from the beginning until you reach the nth element. This operation is O(n)

Adding to the end

If we have a pointer to the last element, this operation is O(1).

Insert and Removal

This involves finding the place to insert - O(n) and fixing up the pointers. This seems like the same complexity, but a vector has to copy elements, while a list only looks for the right place. A big difference would be seen if we want to insert an element at the very beginning. A list, would have to look through nothing, while a vector would have to move almost all the elements.

Stack and Queue

These are container adapters. They wrap the above containers, implement stronger relationships, and add new operations.

The difference between these two is that a stack is LIFO - last in first out, while the queue is FIFO - first in first out. Different algorithms use different data structures, since the operations available are faster.

Answer 2

So I'll give a very short answer: Each object has a different target and need.

stack and queue are objects that obfuscate some accessing methods, and usually allow better mechanisms to implement concurrency. If you need to get data by a specific order - stack and queue are the objects for you.

Vector, at least in C is an implementation over arrays that allow you to increase and decrease the array size in run time without hurting the most important property of arrays - being sequential in memory.

lists are not sequential in memory but very dynamic - adding and removing items cost less than in vector, at the price of access time (since their not sequential)

to summarize:

if you need to get the items one by one, in the order they were given - use queue.

if you need to get the last item that was inserted first - use stack.

if you know the number of elements your going to use in advance, and there order does not matter at all - use arrays.

if the order does not matter , and the number of elements change in run time, while the adding/removing is not often, but querying the data is - use vector.

if there are more inserts/deletes then querying - use lists. in lists you can also leverage orders cheaply with pointer changes - so this can be used to it too.

These are pretty short and not through at all.. there is much more behind of each data structure...