Queue ADT Homework

[Rheiko]

So the story is I had a presentation a few days ago explaining about what is Queue and how it works, like how to do enQueue, deQueue, etc, etc.

After everything's done, the lecturer gave us a task to explain about Queue ADT on a piece of paper. We have never been taught anything regarding ADT yet. So I did my own research and found a lot of information but some of them are this, this, and this.

Even so, I'm still unsure if I have completely grasped the definition of ADT. So I think, ADT is basically processes that work behind the scene, there's no need to know how they work and there are many ways or methods to achieve its goal. So processes like enQueue and deQueue are part of Queue ADT. Please correct me if I'm wrong.

But then we were given this.

//Queue ADT Data Structures
//Queue ADT Type Definitions
  typedef struct node
    {
    void* dataPtr;
    struct node* next;
    } QUEUE_NODE;
  typedef struct
    {
    QUEUE_NODE* front;
    QUEUE_NODE* rear;
    } QUEUE;
//Prototype Declarations
  QUEUE* createQueue (void);
  QUEUE* destroyQueue (QUEUE* queue);

  bool dequeue (QUEUE* queue, void** itemPtr);
  bool enqueue (QUEUE* queue, void* itemPtr);
  bool queueFront (QUEUE* queue, void** itemPtr);
  bool queueRear (QUEUE* queue, void** itemPtr);
  bool queueCount (QUEUE* queue);

  bool emptyQueue (QUEUE* queue);
  bool fullQueue (QUEUE* queue);
//End of Queue ADT Definitions

So I'm assuming we were given the task to explain about ADT on a piece of paper based on this code...? But I don't really understand the code.

I would be really grateful if anyone could help.
Thanks in advance.

 

[Dr Super Good]

To quote Wikipedia...

In computer science, an abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

In other words, an Abstract Data Type is a way of storing data from a user perspective who only cares about what data they can store and how. It is abstract in the sense that all implementation details can be masked from them without effecting their ability to be used.

The code is a list of C style declarations that could be used to represent a queue ADT.

The typedef at the top actually expose concrete implementation details, a quirk of the C language. However as far as the user is concerned they only need to care about the "QUEUE" type as that is used for the abstract representation of the queue ADT. The functions below are used to create, manipulate and destroy instances of the queue ATD.

As far as implementation details leaked goes one can see the implementation is that of a single linked list. The "QUEUE_NODE" defines the implementation of each node, which holds a pointer to some data as well as a pointer to the next node in the queue. The QUEUE type itself has pointers to both beginning and end nodes so that enqueue and dequeue operations can complete with O(1) complexity by adding to the queue end or removing from the queue beginning. That said the entire purpose of using an ATD is to mask these details, so it is possible to completely change this to something like a circular array queue without the user needing to change any code. In other words as a user one should never be poking the members of those structs even if due to how the C language works one could since then the data type is no longer abstrct.

The functions to manipulate the queue ATD are pretty standard. The queue itself is represented as a pointer to a QUEUE object. This is created and destroyed using the appropriate functions so as to abstract away memory management. Creating the queue gives you a pointer value to a QUEUE however I am unsure why destroying a QUEUE also gives you one. It might be for error reporting to confirm the QUEUE was destroyed however if destroying does fail that is usually a sign of a pretty serious application fault so maybe this was a CnP typo.

There is a list of expected manipulation methods to enqueue, dequeue and peek values at both ends. The queue stores items in the form of pointers to data, possibly even other ADTs (since QUEUE is handled by the user as a pointer to QUEUE). Data is returned by updating a pointer to data, passed in as a pointer to pointer to data for this purpose. A boolean value is returned to represent successful completion of the operation, eg so that fail values like false can be returned when enqueuing to a full queue, or dequeuing or peeking from an empty queue.

The declaration for "queueCount" clearly has a typo. It is meant to return something like "size_t" (most correct) or "unsigned int" (less correct, more simple to understand as is a primitive type) or any other kind of integer numeric value. It is meant to return the number of data elements (nodes) currently in the queue. This is not possible with the current return type of bool since that can only be used to represent 2 states from an abstract point of view so could at most act like another version of the empty/full functions.

The empty/full functions return if the queue is in the appropriate state. Although the leaked implementation details point towards this implementation of queue having no technical limit to queue size due to the nature of linked lists (fullQueue always returns false), other implementations such as circular array (limited by array size) might. This helps preserve the abstract nature of the data structure by exposing implementation limits through an abstract API. Empty queue returns true when no elements are in the queue, or in other words when queueCount returns 0 (if it had a sensible numeric return type).

I am not too sure this is what you are after but hopefully it helps. Do be aware that if you are handing in any marked assessments based on this you cannot copy what I have written above as it will flag plagiarism checks due to the public visibility of this forum.