none
Queue and Stack classes

    Question

  • Hi guys,

    I have red a lot of article about Queue and Stack classes. But i couldnt understand why we need to use them? whats the purpose of using them? i can do everything with List what i do with Queue and Stack classes( or i think i can). thus, why to Queue and Stack classes? what do you guys use them in professional life?

    Thanks,

    Thursday, March 22, 2012 6:49 AM

Answers

  • A list uses Array in the background to store items, while queues and stacks use Linked List.

    If you know the difference between these two you would automatically start using Stacks and Queues wherever applicable :)

    A linked list operation to add and remove items is much faster than arrays.

    Array is a contiguous block. When you want to expand or shrink it, its not so easy. The entire array needs to be copied to a different memory location.

    In linked list, the memory can be allocated anywhere, and one item points to another and the other to the other. So no need to disturb the other items when you want to add/remove items.

    But each has its own advantages and disadvantages. Searches are fast in arrays but inserts/deletes are slow.  While in case of LinkedLists, inserts/deletes are fast and searches slow.

    This is the reason why you don't have search in Stacks & Queues. The primary purpose is push/pop data from one or the other end, either FIFO or LIFO.


    Pradeep, Microsoft MVP (Visual Basic)
    http://pradeep1210.wordpress.com



    • Edited by pradeep1210 Thursday, March 22, 2012 8:46 AM
    • Marked as answer by Lisyus35 Thursday, March 22, 2012 4:52 PM
    Thursday, March 22, 2012 8:37 AM

All replies

  • Hi Lisy,

    I appreciate your thought on this.  I can add my view to your query.

    I agree to you that the List class supports all the operations Queue and Stack has.

    But a Queue provides more functionality to support the Queue data structure. similarly the stack too.

    The Queue and Stack provides much flexibility and more manageable code than the List in the queue/stack scenarios.

    In summary we can say they are fine tuned solutions for the particular problem they are addressing.

    Eg 1: For creating a command pattern implementation for supporting undo/redo operation a Stack is better than List.

    Eg 2: For implementing PostFix Expression evaluation Stack is better than List


    It is like we are comparing a passenger car with a van.  Both can do the travelling accomplishments.  But a car more sophisticated for pleasured travel, ease of use, modesty etc.

    Thought: The array too supports all functions the List do.  Then why they both exists?

    Answers: More Manageable Code / Object Oriented Methods / Less Overhead in Size Management


    Resolving n Evolving in C# (http://jeanpaulva.com)


    Thursday, March 22, 2012 6:58 AM
  • Lisys,

    QUEUE is use to manage orders in Fist In Fist out basis that is FIFO order.

    Use Queue to execute Online orders. Order come first we should give prefernce to first to execute the same.

    STATCK purpose is opposite to QUEUE that is Last in Fist out LIFO.

    we use STATCK to execute function in LIFO order. The best example is Recursion.

     

    Thursday, March 22, 2012 7:24 AM
  • A list uses Array in the background to store items, while queues and stacks use Linked List.

    If you know the difference between these two you would automatically start using Stacks and Queues wherever applicable :)

    A linked list operation to add and remove items is much faster than arrays.

    Array is a contiguous block. When you want to expand or shrink it, its not so easy. The entire array needs to be copied to a different memory location.

    In linked list, the memory can be allocated anywhere, and one item points to another and the other to the other. So no need to disturb the other items when you want to add/remove items.

    But each has its own advantages and disadvantages. Searches are fast in arrays but inserts/deletes are slow.  While in case of LinkedLists, inserts/deletes are fast and searches slow.

    This is the reason why you don't have search in Stacks & Queues. The primary purpose is push/pop data from one or the other end, either FIFO or LIFO.


    Pradeep, Microsoft MVP (Visual Basic)
    http://pradeep1210.wordpress.com



    • Edited by pradeep1210 Thursday, March 22, 2012 8:46 AM
    • Marked as answer by Lisyus35 Thursday, March 22, 2012 4:52 PM
    Thursday, March 22, 2012 8:37 AM
  • It is easy, when you go to England to a bakery then everybody goes to the end of the (queue) line and waits until everybody has bought a bread.

    However, if you go to Holland then everybody enters the shop and the first thing they try is to become the first helped. 

    In a queue the first who enters is the first helped, in a stack the last who enters is the first helped.

    In a program is the main difference that a queue when helped is done with the method dequeue and who enters to enqueue while in a stack this is done with pop and push. 

     

    Success
    Cor



    Thursday, March 22, 2012 10:08 AM
  • A stack is not terribly difficult to implement using a list.  You add new items onto the end, and you take old items off of the back.  It is sometimes useful to wrap this functionality into another class so that you ensure you always add items to the appropriate place and remove them from the appropriate place, but it's not a huge deal, that's true.  That said, there are other ways to implement a stack, such as the Linked List mentioned by another poster.  By encapsulation a 'Stack' as its own class you can potentially change the underlying implementation without any change from the point of view of the consumer.  (In C++ STL for example you have the option of passing an empty data structure to the Stack class and it will use that data structure as the backing class; cool stuff.)  The C# implementation of Stack uses an array (sorry pradeep1210) as stated on the MSDN page: "Stack(Of T) is implemented as an array."  While it is true that adding to the end of an array and adding to the end of a linked list are both O(1) operations, adding to the end of a Linked list still does have more to do.  I needs to new up an object (Node), populate it with data, add the references between the existing nodes and start/end pointers as well as setting the pointers of the new node, etc.  It's all constant, but it's still a whole lot longer than just setting the value of a single array element.  Resizing the array will take longer when it does happen, but given that it tends to not happen THAT often it's still a net win in the average case.

    Most of the same arguments all apply to Queue as well.  A queue can be implemented as a List/Array, but it's not quite so simple to do it effectively.  The naive way to implement a queue would be to add items to the end of the array and then remove items from the start.  This seems easy, except that "remove from the start" is extremely ineffective with an Array/ArrayList.  It involves copying every single value in the array.  However, it's not too much harder to implement a circular array.  A circular array has an integer that has an index that keeps track of where the "start" and "end" of the array is.  When you add an item you add it to where "start" points to and then move "start" up one.  When you remove an item you remove the item that "remove" points to and then move "remove" up one.  You also need logic for determining when the queue is full so that you can create a new, larger, array and move all of the items to it.  Since this is somewhat more complicated it has clearly become much more important to wrap this functionality in a "Queue" class.  We could use a Linked List for a queue, and it would make the Queue class's code shorter, but using an Array has just the same advantages as with a Stack, and by using a circular array adding/removing are still O(1) when not resizing.  The MSDN documentation for a Queue also indicates that it is implemented via an Array, not a Linked List.

    Thursday, March 22, 2012 2:24 PM
  • A list uses Array in the background to store items, while queues and stacks use Linked List.

    Another case of fine reasoning being spoiled by the truth.
    Thursday, March 22, 2012 2:25 PM