Queue

Definition:

According to wikipidea:

• A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal operations


• collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position.


• FIFO (First In First Out)

[wiki]http://en.wikipedia.org/wiki/Queue_(data_structure)

Illustrations:

[350 x 340 - 40k - jpg - www.ac-nancy-metz.fr/.../Henry/bus-queue.jpg ]


Below is the image at: www.ac-nancy-metz.fr/.../anglais/Henry/ville.htm

Implementation of Stack

//To implement an array in a certain stacks.

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 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(23);
theList.insertFirst(13);
theList.insertFirst(22);

theList.deleteFirst();

theList.displayList();
}
}

Double Ended Linked List

♥ Definition

According to our previous topic that our instructor introduced it double-ended linked list, it was an addition reference that point to the last linked list and first linked list.

B. Illustration:


[Illustration given by of our instructor]

Implementation of Double Ended Link List

// To implement a double ended link list.

//constructor
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 FirstLastList {

private Link first;
private Link last;

public FirstLastList() {

first = null;
last = null;

}

public boolean isEmpty() {

return (first == null);

}
// inserting a node in first element

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 in a last element

public void insertLast(int id,double dd) {

Link newLink = new Link(id,dd);

if (isEmpty())
first = newLink;

else

last.next = newLink;
last = newLink;
}

// delete the first node in the list
public Link deleteFirst(int id,double dd) {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

// delete the last node in a list
public Link deleteLast(int id, double dd){
int temp=last.iData;
if(last.next==null)
first=null;
last=last.next;
return temp;
}
// display an element in a list
public void displayList(){
System.out.print("List(first-->Last);");
Link current=first;
while(current!=null){
current.displayLink();
current=current.next;
}

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

}

//main method to apply
public class FirstLastApp{

public static void main(String[] args) {

FirstLastList theList = new FirstLastList();

theList.insertFirst(19,1.90);
theList.insertFirst(13,1.9);
theList.insertFirst(25,5.62);
theList.insertLast(24,6.8);
theList.insertLast(23,3.79);
theList.insertLast(56,2.25);

System.out.println(theList);

theList.deleteFirst();

theList.deleteFirst();

System.out.println(theList);
}

}

Doubly Linked List

♥ Definition/Concept

According to Wikipedia:

A more sophisticated kind of linked list is a doubly-linked list or two-way lined list, that every each node has two links one points to the previous node or points to a null value or empty list if it is the first node, and one points to the next, or points to a null value or empty list if it is the final node.[wiki]

A double linked list is a linked list, in which each node contains a pointer to a next node and a pointer to a previous element in the list.[google]

♣ As I understand of doubly linked list it has a node that points in the next node and the other points in the previous node, to access with next and previous node.

♥ Illustrations


Doubly-linked-list.svg‎ (SVG file, nominally 610 × 41 pixels, file size: 23 KB)
[This is a file from the Wikimedia Commons]

♥ Implementation

// To implement a doubly linked list.

//constructor
class Link{

public int iData;
public Link next;
public Link previous;
public Link(int id) {

iData = id;
}

// display element in a list
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;
}

//insertion of first element
public void insertFirst(int dd)
{
Link newLink = new Link(dd);

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

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

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

//deletion of last element
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 to apply
public class DoublyLinkedApp
{
public static void main(String[] args)
{
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(12);
theList.insertFirst(87);
theList.insertFirst(30);
theList.insertLast(22);
theList.insertLast(25);
theList.insertLast(27);

System.out.println(theList);

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

theList.insertAfter(12, 10);
theList.insertAfter(30, 21);
System.out.println(theList);
}
}

♥ Reference

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

http://www.google.com.ph/search?hl=en&q=double+linked+list&btnG=Google+Search&meta=

[wiki] http://en.wikipedia.org/wiki/File:Doubly-linked-list.svg

Stacks

1.) Definition and concept of stack

[Wikipedia]

• In the field of computer science, they said that a stack is an abstract data type and a data structure.
• LIFO( Last in First out) – principle used by stack
  

Applications

• Stacks has a concept which may used as extensively at every level of a modern computer system.
• PC stacks at the architecture level- which are used in the basic design of an operating system for interrupt handling and operating system function calls. [wiki]
  

[According to the book]

♣ The fundamental operations on a stack

• push which is equivalent to an insert, and
• pop, which deletes the most recently inserted element

[ Mark Allen Weiss,"Data Strustures and Algorithm Analysis in C"

Florida International University, pg 61]

2.) Illustration of Stack

this image is copyright at: [400 x 376 - 182k - jpg - www.sneewittchen.com/blackblackblack/stacks.jpg]

3.) References

http://en.wikipedia.org/wiki/Stack_(data_structure)

[ Mark Allen Weiss,"Data Strustures and Algorithm Analysis in C" Florida International University, pg 61]

www.sneewittchen.com/blackblackblack/

♥♥♥Other Source♥♥♥

http://www.java2s.com/Tutorial/Java/0140__Collections/DoubleEndedListslistwithfirstandlastreferences.htm

http://www.java2s.com/Tutorial/Java/0140__Collections/Adoublylinkedlist.htm

http://www.java2s.com/Tutorial/Java/0140__Collections/Demonstratingastackimplementedasalist.htm

http://www.java2s.com/Tutorial/Java/0140__Collections/AQueueImplementedbyaLinkedList.htm