Queue

/* Programmer: Matet P. Tipudan

Program name: Queue
Purpose: To implement a Queue Code.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures*/

A. Definition/Concept:

♥A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position.[Wikipedia]

B. Illustration:

C. References:

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

Stack Implementation

A. Definition/ Concept:

♥Always remember that the stack is a very common data structure used in programs. By data  structure, we mean something that is meant to hold data and provides certain operations on that data.[1]
♥Stacks are linear data structures. This means that their contexts are stored in what looks like a line (although vertically). This linear property, however, is not sufficient to discriminate a stack from other linear data structures. For example, an array is a sort of linear data structure in which you can access any element directly. In contrast, in a stack, you can only access the element at its top.[2]
♥Since a stack usually holds a bunch of items with the same type, we could implement a stack as an array. [www.google.com]


B. java Code:


//purpose: To implement an array of list in a certain Stack


public class LLStack{
private java.util.LinkedList list=nw java.util.LinkedList();
public LLStack(){
}
public void clear(){
list.clear();
}
public boolean isEmpty(){
return list.isEmpty();
}
public Object topEl(){
if(isEmpty())
throw new java.util.EmptyStackException();
return list.getLast();
}
public Object pop(){
if(isEmpty())
throw new java.util.EmptyStackException();
return list.removeLast();
}
public void push(Object el){
list.addLast(el);
}
public String toString(){
return list.toString();
}
}


C. References:

[1]Data structures and algorithms in Java 2nd Edition by: Adam Drozdek
[2]http://www.cs.bu.edu/teaching/c/stack/linked-list/

Doubly Linked Lists

A. Definition/ Concept

♥According to the book by: Mark Allen Weiss Doubly Linked Lists sometimes to traverse lists backwards. The standard implementation does not help here, but the solution is simple. Merely add an extra field to the data structure, containing a pointer to the previous cell. The cost of this is an extra link, which adds to the space requirement and also doubles the cost of insertions and deletions, because you no longer have to refer to a key by using a pointer to the previous cell.[Book of Data Structure and Algorithm Analysis]
♥According to Wikipedia, a more sophisticated kind of linked list is a doubly-linked list or two-way linked list. 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.[WIKIPEDIA]


B.Illustration



A doubly-linked list containing three integer values: the value, the link forward to the next node, and the link backward to the previous node

C. java Code


//constructor class

class Link {

public int iData;

public Link next;

public Link previous;

public Link(int id) {

iData = id;

}

public String toString() {

return "{" + iData + "} ";

}

}

//a class that has the methods or operation of doubly linked list


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;

}

public String toString() {

String str = "List (first-->last): ";

Link current = first;

while (current != null) {

str += current.toString();

current = current.next;

}

System.out.println("");

System.out.print("List (last-->first): ");

current = last;

while (current != null) {

str += current.toString();

current = current.previous;

}

return str;

}

}


//main class that executes the operation on the doubly linked lists

public class MainClass {

public static void main(String[] args) {

DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(22);

theList.insertFirst(44);

theList.insertFirst(66);

theList.insertLast(11);

theList.insertLast(33);

theList.insertLast(55);

System.out.println(theList);

theList.deleteFirst();

theList.deleteLast();

theList.deleteKey(11);

System.out.println(theList);

theList.insertAfter(22, 77);

theList.insertAfter(33, 88);

System.out.println(theList);

}

}


D.References

[Book of Data Structure and Algorithm Analysis]Mark Allen Weiss
[WIKI]http://en.wikipedia.org/wiki/Linked_list
[WIKI]http://en.wikipedia.org/wiki/File:Doubly-linked-list.svg

Double-ended Linked List

A. Definition/ Concept :

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


B. Illustration:

D. Reference:

[WIKI] http://www.rosettacode.org/wiki/Doubly-Linked_List_(element_insertion)

C. java Code:

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);
}
public void insertFirst(int id,double dd)
{
Link newLink = new Link(id,dd);
if (isEmpty ())

last = newLink;

newLink.next = first;

first = newLink;
}
public void insertLast(int id,double dd)
{

Link newLink = new Link(id,dd);

if (isEmpty())first = newLink;

elselast.next = newLink;

last = newLink;
}
public int deleteFirst()
{
int temp = first.iData;

if (first.next == null)

last = null;

first = first.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 FirstLastApp
{
public static void main(String[] args)
{
FirstLastList theList = new FirstLastList();

theList.insertFirst(22,2.99);

theList.insertFirst(44,4.99);

theList.insertFirst(66,6.99);

theList.insertLast(11,1.99);

theList.insertLast(33,3.99);

theList.insertLast(55,5.99);

System.out.println(theList);

theList.deleteFirst();

theList.deleteFirst();

System.out.println(theList);
}
}

D. Reference:

[WIKI] http://www.rosettacode.org/wiki/Doubly-Linked_List_(element_insertion)

Stack

A. Definition/ Concept

♀According to Wikipedia page stack is container nodes and has two basic operations: push and pop. Push adds a given node to the top of the stack leaving previous nodes below. Pop removes and returns the current top node of the stack.

♀In computer science, a stack is an abstract data type and data structures based on the principle of Last in First Out. Example of this is, a modern Personal Computer uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls. ["Wikipedia"]

B. Illustration

Figure 1 illustration of the stack["Wikipedia"]

C. References

["WIKI"] http://en.wikipedia.org/wiki/Stack_(data_structure)

["WIKI"] http://en.wikipedia.org/wiki/File:Data_stack.svg