CODEWITHSUNDEEP
c++cdata-structures
user655298
user655298

Reputation: 9

Stacks and Queues are linear data structure or non linear data structure?

I have been facing this problem since long time. Few authors say that stacks and queues are linear data structure and in few non-linear. Which one is right and why?

In wikipedia, it is given that queue is a linear data structure. I too believe that they are linear, as there are no diversions as in the case of trees. However, while attempting an online test, it was overridden saying that these are non-linear.

Please answer me in precise, which is true and why.

Upvotes: 0

Views: 4188

Answers (5)

Shuo
Shuo

Reputation: 8937

liner datastructure has nothing to to with it's implementation detail or its memory model. It just means all its elements has its preceding or following, exclude the head and end. Not like a tree or gragh.

Liner datastructure includes queue, stack.

If somebody mis uses the liner as "Continouse memory", he/she is wrong.

Upvotes: 0

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385264

What do you mean by "linear" here? They're certainly neither circular nor spherical.

Also, the answer will depend on what stacks/queues you're talking about.

Did you mean "contiguous"?

If you mean std::stack and std::queue (then remove the "C" tag from your question, please), then it still depends. They're both container adaptors meaning that the underlying implementation can be specified as a template parameter. By default, std::stack and std::queue are built on std::deque — which is not guaranteed to be contiguous.

For some other arbitrary container specification, it would depend.

Did you mean "sequence"?

Standard C++ has three sequence containers: std::vector, std::list and std::deque. This means that a std::stack/std::queue is not a sequence container in itself, but its implementation may be, depending on which one you pick.

Hope that helps.

Upvotes: 3

Majd
Majd

Reputation: 1368

It depends! A queue/stack can be linear as in the case of FIFO and LIFO, however it can be non-linear in the case of priority queue for example, where serving an element depends on some parameter you specify!
So, both can be true! It all depends on how you implement the data-structure you are using!
However, most likely a stack is considered linear, a queue can be both, linked lists and trees are non-linear.

Upvotes: 1

Simon Richter
Simon Richter

Reputation: 29608

Either can be true. The words "stack" and "queue" only define the permitted access patterns, not the implementation details. For example, you can implement either as a linked list.

Upvotes: 0

tibur
tibur

Reputation: 11636

For me, a queue or a stack is only a specification. The implementation can vary.

Upvotes: 0

Related Questions