Queue

Definition

• According to wikipedia, A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. [1] http://en.wikipedia.org/wiki/Queue_(data_structure)



• First-In-First-Out (FIFO) data structure- the first element added to the queue will be the first one to be removed. [1]

Illustration

Double Ended Linked list

Definition:
It allows for insertions in the front or in the back of the list. Each type of link list will build off of the previous one. First we'll examine the singly linked list before moving onto the double-ended and doubly linked lists. [safari books]

Doubly-ended Implementation :

class Link
{
public int iData;
public double dData:
public Link next;

public Link(int id,double dd)
{
iData = id;
dData=dd;
}

public void displayLink()
{
System.out.print("{"+iData+","dData+"}");
}
}

class DoubleEndList
{
private Link first;
private Link last;


public DoubleEndList()
{
first = null;
last = null;
}


public boolean isEmpty()
{
return (first == null);
}

public void insertFirst(int id,double dd)
{
Link newLink = new Link(id,dd);

if (isEmpty ())
last = newLink;
newLink.next = first;

first = newLink;
}

//inserting a node on the last
public void insertLast(int id,double dd)
{
Link newLink = new Link(id,dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}

public Link deleteFirst(int id,double dd)
{
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}


public Link deleteLast(int id, double dd)
{
int temp=last.iData;
if(last.next==null)
first=null;
last=last.next;
return temp;
}


public void displayList()
{
System.out.print("List(first-->Last);");
Link current=first;
while(current!=null)
{
current.displayLink();
current=current.next;
}
}
System.out.println(" ");
}

public class DoubleEndApp
{
public static void main(String[] args)
{

DoubleEndList theList = new DoubleEndList();

//apply the insertion methods on the first and the last node
theList.insertFirst(12,2.55);
theList.insertFirst(21,4.55);
theList.insertFirst(67,8.99);
theList.insertLast(18,9.99);
theList.insertLast(43,3.33);
theList.insertLast(34,5.66);

System.out.println(theList);

theList.deleteFirst();
theList.deleteLast();
System.out.println(theList);
}
}

Illustrations


Reference:
[safari books] http://my.safaribooksonline.com/30000LTI00162/ch05lev1sec2

DOUBLY LINKED LIST

A) Definition

• It is convenient to traverse lists backwards and the implementation does not here but the solution is simple.[1]
• It contains a pointer to the previous cell, extra link,which adds to the space requirement and doubles the cost of insertions and deletions. It simplifies deletion, because you no longer have to refer to a key by using pointer to the previous cell.[1]

B) Illustration

Java Codes:

class Link
{
public int iData;
public Link next;
public Link previous;
public Link(int id)
{
iData = id;
}


public void displayList()
{
return "{" + iData + "} ";
}
}


class DoublyLinkedList
{
private Link first;
private Link last;

public DoublyLinkedList()
{
first = null;
last = null;
}

public boolean isEmpty()
{
return first == null;
}

public void insertFirst(int dd)
{
Link newLink = new Link(dd);

if (isEmpty())
{
last = newLink;
}else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}

public void insertLast(int dd)
{
Link newLink = new Link(dd);
if (isEmpty())
{
first = newLink;
}else{
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}

public Link deleteFirst()
{
Link temp = first;
if(first.next == null)
{
last = null;
}else{
first.next.previous = null;
}
first = first.next;
return temp;
}

public Link deleteLast()
{
Link temp = last;
if(first.next == null)
{
first = null;
}else{
last.previous.next = null;
}
last = last.previous;
return temp;
}

public boolean insertAfter(int key, int dd)
{
Link current = first;
while (current.iData != key)
{
current = current.next;
if (current == null)
{
return false;
}
}
Link newLink = new Link(dd);
if (current == last)
{
newLink.next = null;
last = newLink;
}else{
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}

public Link deleteKey(int key)
{
Link current = first;
while (current.iData != key)
{
current = current.next;
if (current == null)
return null;
}
if (current == first)
{
first = current.next;
}else{
current.previous.next = current.next;
}
if (current == last)
{
last = current.previous;
}else{
current.next.previous = current.previous;
}
return current;
}
}

// the main method
public class DoublyLinkedApp
{
public static void main(String[] args)
{
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(2);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(3);
theList.insertLast(55);

System.out.println(theList);

theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);
System.out.println(theList);

theList.insertAfter(2, 77);
theList.insertAfter(3, 88);
System.out.println(theList);
}
}

C) Reference

[1]Data Structures and Algorithm Analysis in C; Mark Allen Weiss; Florida International University

[wiki] http://en.wikipedia.org/wiki/Linked_list#Doubly-linked_list

Stack

Concept

According to wikipedia  a stack is an abstack data type and its based on the principle of Last In First Out(LIFO).It is uesd to run a Java Virtual Machine,it is ubiquitous.

Basic Operations

Push-adds a given node to the top .
Pop- removes and returns the current top node.
top(peek)- can return the current top element.


some environments
*Dup(licate)- the top item is popped and pushed again.
*peek- the topmost item is popped.
*Swap or exchange- the two topmost items exchange places.
*rotate- the topmost items are moved in a rotating fashion.
[wiki]





B)Illustration

illustration of Stack[3]

C)References
http://en.wikipedia.org/wiki/File:Data_stack.svg
http://en.wikipedia.org/wiki/Stack_(data_structure)

Implementation of Stack


class Link{
public int iData=0;


public Link(int iData, )
{
iData=id;

}

public void displayLink()
{
System.out.println(iData+":" );
}
}

class StackList{
private Link first;

public StackList(){
first=null;

}

public boolean isEmpty() {
return (first == null);
}

public void insertFirst( int id) {
Link newLink = new Link( id);
newLink.next = first;
first = newLink;
}

public Link deleteFirst()
{
Link temp=first;
return temp;
}

public Link pick()
{
Link temp=first;
return temp;
}

public void displayList
{
System.out.print("Elements on the stack: ");
Link temp=first;
while(temp!=null)
{
temp.displayList();
}

System.out.println(" ");
}
}


class StackListApp
{
public static void main (String[]args)
{
StackList theList=new StackList();

theList.insertFirst(12);
theList.insertFirst(25);
theList.insertFirst(91);


theList.deleteFirst();

theList.displayList();
}
}