Thread: Is a queue essentially a linked-list?

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391

    Is a queue essentially a linked-list?

    I was writing up a simple queue class, and when it came to the copy ctor and the assignment operator, they didn't really differ from how they'd be implemented for a linked list. Is this right?

    Is the only difference between a linked-list and a queue the public interface?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I suppose. IOW, you can implement a queue using a linked list, although you don't have to.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    There are a variety of ways of implementing a queue. Using a linked-list is one of the most straightforward.
    Other ways of storing the data can be thought of as simply optimisations of the linked-list way of doing it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Is the only difference between a linked-list and a queue the public interface?
    A queue is simply an abstraction. It tells you what operations are supported for a collection of data, and you can implement it however you want as long as you ultimately support those operations.
    My best code is written with the delete key.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    An example of what prelude says can be seen in this implementation:
    Code:
    const int size = 16;
    
    class queue
    {
    private:
       int in;
       int out;
       int q[size];
    public:
       queue() : in(0), out(0) {}
       void put_back(int x) {
          if (out !=in+1) { 
             q[in] = x;
             in++;
          }
        }
        int pop_front() {
           int x = -1;   // Empty returns -1. 
           if (out != in) 
           {
              x = q[out];
              out++;
           }
           return x;
        }
    };

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  2. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM