DS-operations on queue.

Operations:
The main primitive operations of a queue are known as:
Add - adds a new node
Remove - removes a node
Additional primitives can be defined:
IsEmpty - reports whether the queueis empty
IsFull - reports whether the queue is full
Initialise - creates/initialises the queue
Destroy - deletes the contents of the queue (may be implemented by re-initialising
the queue)

Common operations from the C++ Standard Template Library include the following:

bool empty() - Returns True if the queue is empty, and False otherwise.

T& front() - Returns a reference to the value at the front of a non-empty queue. There is also a constant version of this function, const T& front().

void pop() - Removes the item at the front of a non-empty queue.

void push(const T& foo) - Inserts the argument foo at the back of the queue.

size_type size() - Returns the total number of elements in the queue.

 

 

Some other Operations on queue are :
1. enqueue - insert item at the back of queue 

2. dequeue - return (and virtually remove) the front item from queue 

3. init - intialize queue , reset all variables.

refer : http://en.wikipedia.org/wiki/Queue_%28data_structure%29

          http://harvestsoft.net/files/queue.pdf

          http://hamilton.bell.ac.uk/swdev2/notes/notes_13.pdf

DS- multi linked list

Multi-Linked lists

A multiple linked list has several pointers in each node. They are used to traverse the nodes in different orders, for example one set of links ordered by date of birth and another ordered alphabetically by name.

Read more: http://wiki.answers.com/Q/What_is_multiple_link_list#ixzz1Fl59W2BN

A list can have two pointers without having a backward pointer. For instance, we may want to keep a set of data ordered on more than one "key". A key is a unique data item included in a record which distinguishes one record from all other records included in the list.  Suppose we want to be able to access customer accounts in order by account number (integer) and by customer name (string). We can in fact have one list that is ordered both ways. We need two pointer fields.  Each node of the list will have the form:

refer: http://frank.mtsu.edu/~csci217/manual/lab10/lab10.html#D

 

Now, let's assume that we have a class called MultiListClass and that we wish to implement this list with a dummy header node.

 Here is an example list which implements the multi-linked list:

Insertion and deletion require about twice the work since two sets of pointers must be adjusted: one for the name and one for the account number.  Essentially, you perform the same adjustments as in a singly linked list but you do it twice.

DS- doubly linked list (page 2)

Doubly-Linked Lists — linked lists containing integer values or pointers to data, with the ability to iterate over the list in both directions.

Each element in the list contains a piece of data, together with pointers which link to the previous and next elements in the list. Using these pointers it is possible to move through the list in both directions (unlike the Singly-Linked Lists which only allows movement through the list in the forward direction).

The data contained in each element can be either integer values, by using one of the Type Conversion Macros, or simply pointers to any type of data.

While adding or removing a node in a doubly-linked list requires changing more links than the same operations on a singly-linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.

refer : http://en.wikipedia.org/wiki/Doubly-linked_list
          http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html

DS- doubly linked list (page 1)

A doubly-linked list is a linked data structure that consists of a set of sequentially-linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.


plsss...refer : http://richardbowles.tripod.com/cpp/linklist/doublist.htm


A doubly linked list is one where there are links from each node in both directions:

current position

Data

Data

Data

Data

NULL

NULL

DS- link list v/s array (page 2 )

3)Memory allocation:
Most often, arrays are static. The drawback to this approach is that large arrays require large amounts of memory, which may go unused.
On the other hand, linked lists are usually dynamic. They can grow and shrink as needed at runtime. Due to this trait, linked lists are more appealing when the number of elements is unknown.

4) Accessing elements:
The elements within arrays are accessed by their indices. Thus, data access is easy and fast if you know which element to retrieve. If you don’t know the index of the element needed, but the elements are sorted based on some key value, you can perform highly efficient search algorithms to locate specific elements.

Linked lists are usually traversed element by element until a match is found. Because the memory for linked lists is not guaranteed to be contiguous, this list traversal is the only method for searching the list (without involving the use of other data structures as indices ). 


5) Making the decision:
If your data is best represented using a multidimensional structure, or the number of elements is known in advance and will remain consistent, an array is best. If your data is easily represented in one dimension, and the number of elements is unknown or is expected to change often throughout the operation of your program, a linked list is more efficient.

also refer :
http://geeksforgeeks.org/?p=10245
http://geekexplains.blogspot.com/2008/05/array-vs-linked-list-advantages-and.html

DS- link list v/s array ( page 1)

Arrays and linked lists are among the most common data structures, and each is applicable in different situations.

1) An array is an ordered arrangement of data elements that are accessed by their referencing indices.
A linked list is a group of items, each of which contains a pointer pointing to the next item.


2)Sizing:
Arrays can be one-dimensional or multidimensional, depending upon your requirements. For example, you could use a one-dimensional array to store the scores of all students in a class for one test. A multidimensional array would be better to store the scores of all students for all tests throughout the semester. Figure A provides an example of a one-dimensional array, and Figure B shows a multidimensional array.

Figure A

One-dimensional array

Figure B

Multidimensional array

In Figure B, the scores may be averaged by test (across), by student (down), or by class (entire array), while each unique score is maintained.

In contrast to arrays, linked lists are, by their very nature, one-dimensional. They can be singly linked lists, as shown in Figure C, where traversal of the list can be done in only one direction, or doubly linked lists, such as in Figure D, where each element points to both the previous element and the next element in the list.

Figure C
Singly linked list

CG-Bresenham’s circle drawing algorithm.

Bresenham's circle algorithm calculates the locations of the pixels in the first 45 degrees. It assumes that the circle is centered on the origin. So for every pixel (x,y) it calculates we draw a pixel in each of the 8 octants of the circle :

PutPixel(Center X + X, Center Y + Y)
PutPixel(Center X + X, Center Y - Y)
PutPixel(Center X - X, Center Y + Y)
PutPixel(Center X - X, Center Y - Y)
PutPixel(Center X + Y, Center Y + X)
PutPixel(Center X + Y, Center Y - X)
PutPixel(Center X - Y, Center Y + X)
PutPixel(Center X - Y, Center Y - X)

So let's get into the actual algorithm. Given a radius for the circle we perform this initialisation:

d := 3 - (2 * RADIUS)
x := 0
y := RADIUS

 Now for each pixel we do the following operations:

Draw the 8 circle pixels
if d < 0 then
    d := d + (4 * x) + 6
else
  begin
    d := d + 4 * (x - y) + 10
    y := y - 1;
  end;

 And we keep doing this until x = y. Note that the values added to the decision variable in this algorithm (x and y) are constantly changing, so we cannot precalculate them. The muliplications however are by 4, and we can accomplish this by shifting left twice.