Click here to Skip to main content
15,558,870 members
Please Sign up or sign in to vote.
1.80/5 (5 votes)
See more:
Hi,

I want to implement a queue using a linked list in C#.net but don’t want to use a standard container which are available in C#. This queue will hold a PdfDocument and WordDocument object.

This queue has two functions: PUSH() which will insert documents into the queue and POP() will retrieve the documents from the queue.

If anybody has any ideas please share with me. It will be highly appreciated

Thanks.
Nabhendu
Posted
Updated 14-Nov-17 9:53am
v2
Comments
[no name] 22-Mar-11 11:39am    
Whats wrong with the standard "Queue<t>"? http://msdn.microsoft.com/en-us/library/7977ey2c.aspx

If you do not explain this we can not help you with a solution....
Sergey Alexandrovich Kryukov 22-Mar-11 11:50am    
Not using standard container means a work for study purposes. What's the use is someone give you the solution? Also, why anyone can be interested in that? So, please do this exercise. If you face any problems, you will be able to get help. Just ask a question.
--SA
ndas.net 22-Mar-11 23:07pm    
I want to develop my own queue base class...
Micha3ldg 23-Mar-11 3:44am    
Why not use the Generic Queue? Your class will be strong type.
http://msdn.microsoft.com/en-us/library/7977ey2c.aspx

As the others that commented on your question already said I too advise you to use the standard classes available in .NET. Most importantly though is this:


  1. Push and Pop are method names that carry the connotation of a stack. Something is "Pushed" onto a stack and removed from it with a "Pop". A stack is a datastructure that acts as a LIFO which means Last In First Out. The most recently pushed element will be popped before any element that was pushed before that.
  2. The correct method names for a queue are "Enqueue" for placing an element into the queue and "Dequeue" for taking an element from the queue. The manner in which this done is called FIFO, meaning First In First Out. An element A that was placed into a queue before element B will also be removed from the queue before element B. (When talking about priority queues there are subtle differences, but you can always read up on that later.


As to how to implement that:

  1. Your Queue class will need two references to instances of the QueueElement class.

    1. The linking direction is from start of queue to tail of queue
    2. Head: Points to the start of the queue where elements will be removed (Dequeue)
    3. Tail: Points to the end of the queue where elements will be added (Enqueue)

  2. Make Queue and QueueElement generic so that you'll have the possibility to create a queue for all kinds of classes.
  3. To enqueue an element do this:

    1. Create a QueueElement instance
    2. Store the content element into the QueueElement
    3. Make the successor of the QueueElement that is pointed to by tail point to the QueueElement just created.
    4. Make the tail reference of the queue point to the just created QueueElement.
    5. If head was null make head also point to the same element as tail.

  4. To dequeue an element do this:

    1. Store the head reference in a local variable.
    2. Make the head reference point to the successor element of the head QueueElement.
    3. The element at the end of the linked list always has null as it's successor.
    4. If the head of the queue is null set the tail also to null
    5. Return the reference stored in the local variable.



That's more or less it.

Happy coding!
 
Share this answer
 
Comments
CPallini 24-Mar-11 8:43am    
5.
[no name] 24-Mar-11 10:15am    
Well said!
But why do you "want" to reinvent that wheel? The .Net framework already has a perfectly capable queue class. You can extend it with extension methods, and get all the benefits of fully tested code without actually having to test the basic queue functionality. What functionality do you want to add that it doesn't already have? What do you think you could do better?
 
Share this answer
 
Comments
fjdiewornncalwe 24-Mar-11 15:03pm    
I totally agree that for practical, commercial development we should not be reinventing the wheel "because we want to". But let's be honest... I'm pegging that you were like me as a kid. You wanted to take everything apart to see how it worked. That thought process has value in development, too. But like I said, not in a commercial environment.
C#
class Node {
  private int data {get; set;}
  public Node previous {get; set;}
  public Node (int val)
  {
    data = val;
    previous = null;
  }
}

class Queue {
  private Node Front, Rear, Prev = null;
  public Queue()
  {
    Front = Rear = null;
  }
  public void Enque(int val)
  {
    Node n = new Node(val);
    if (Prev == null)
    {
      Front = Rear = n;
    }
    else if (Front == Rear)
    {
      Rear.previous = n;
      Front = Rear.previous;
    }
    else
    {
      Front.previous = n;
      Front = Front.previous;
    }
  }
  public int Deque()
  {
    int val = Rear.data;
    Rear = Rear.previous;
    return val;
  }
}


I haven't tested this solution so test it before use. Also I did it in short amount of time so if you find any bugs or any other glitch, please let me know. Thanks.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900