-3

I have a homework assignment where I need to build my own queue. My last homework assignment involved building a linked list.

Is a queue nothing more than a linked list that can only add to the front and delete from the end? Can I just copy and paste my linked list code and remove all extra functions besides this?

I've looked into documentation of queue and I see some specific functions such as outputting the front/back of the queue which I also added, but have I pretty much completed the assignment by making a linked list earlier?

user8382698
  • 1
  • A queue is an **abstraction**, there are multiple ways you could implement it. In the C++ Standard Library, there is a [`queue`](http://en.cppreference.com/w/cpp/container/queue) adaptor, which by default is built on top of a [`deque`](http://en.cppreference.com/w/cpp/container/deque), which is a [chunk-based](https://stackoverflow.com/q/6292332/1171191) data structure, some sort of hybrid of a vector and a linked list. This is a bit more efficient than a linked list when you only perform operations at the ends, but a linked list will work fine. – BoBTFish Jul 28 '17 at 15:12
  • Please do some reasearch before posting questions. [This](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)) is the first result on google and was found by searching *how are queues implemented* – NathanOliver Jul 28 '17 at 15:14
  • Queue is a data structure which has a certain set of semantics which are different form linked list semantics. Though you can implement a queue using linked list or an array, or something else. So, please read the corresponding material in your class, or at least google it. – Serge Jul 28 '17 at 15:15

3 Answers3

1

From here:

Queue is a FIFO (First-In, First-Out) list, a list-like structure that provides restricted access to its elements: elements may only be inserted at the back and removed from the front. Similarly to stacks, queues are less flexible than lists.

So, yes you are (almost) right. A queue can use a linked list as its underlying data container. However, do note that a queue could as well use a std::vector (maybe not the best idea) or something completely different to store its data. Anyhow, as you already have a linked list thats probably a good choice.

Do not copy-paste any code! Duplicate code is always bad. If you ever want to change something on your linked-list implementation you will have to do it in two places. As the queue restricts the access to its elements it is maybe easiest implemented like this:

class MyQueue {
    MyLinkedList data;
public:
    pop_front();
    push_back();
    // ...etc...
};
463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
0

From my Data Structures classes, I remember a queue being an Abstract Data Type (ADT), meaning it was a description of what the structure should be doing, whereas a Linked List is an implementation of the ADT using the specifications of the ADT. In code, the two terms are sometimes used interchangeably, or sometimes a queue is just a Linked List where you insert from one end, and remove from the other.

MikeChav
  • 104
  • 7
0

There are different was to implement a queue (it's an abstract data type), using linked lists, arrays, two stacks, and others. Your linked list offers much of the functionality you need to have a proper queue, so yes, your queue implementation will be quite similar to that of your linked list. Consider following some of the common naming conventions of queues such as enQueue (adding element), deQueue (removing element), isEmpty, or find others that make sense to you.

TEK
  • 125
  • 10