Queue implementation

/* Programmer’s name: Lovely Bajar
Name of Program: Queue implementation
Date Started: March 11, 2009
Date Finished : March 12, 2009
Instructor : Mr. Dony Dongiapon
Course: IT 123: Data Structures
Objective: To be able to make a program that implements a queue data structure in a linked list
*/

Concept: List of employees in a given company

//class constructor
class Queue{
public int employeenum;
public String firstname;
public String Lastname;
public char Middlename;
public Queue next;


public Queue (int Enum, String Fname, String Lname, char M; )
{

emlopyeenum=Enum;
firstname=Fname;
lastname=Lname;
middlename=M;
}


//displaying the elements on the list
public void displayQueue()
{
System.out.print(employeename +” “ + firstname +” “ +” “+middlename+ “ “ +: + lastname)
}
}


/*a separate class which contains the ,methods that would be used in implementing the program */
class QueueList
private Queue first;
private Queue last;
public QueueList()
{
first=null;
last=null;
}


//checking if the queue has elements
public Boolean isEmpty()
{
return (first==null);
}

//inserting an element on the queue
public void Enqueue(int Enum, String Fname, String Lname, char M,)

{
Queue newQueue= new Queue (int Enum, String Fname, String Lname, char M,)

if( isEmpty())
last = newQueue;
newQueue.next=first;
first=newQueue;
}


//deleting an element on the queue
public void Dequeue (int Enum)
{
Queue newQueue=new Queue (int Enum, String Fname, String Lname, char M)

int temp=first.entrynum;
if (first.next==null)
last=null;
first=first.next;
return temp


}
}


public class MainClass {
public static void main(String[] args) {
LinkQueue theQueue = new LinkQueue();
theQueue.enqueue(1, “Nemilyn”, “Bayacag”, ‘M’ )

theQueue.enqueue(2, “Lovely”, “Bajar”, ‘C’ );
System.out.println(theQueue);

theQueue.enqueue(3,“Nellen”, “Ortiz”, ‘C’ )
System.out.println(theQueue)



theQueue.dequeue(3);

System.out.println(theQueue);



System.out.println(theQueue);
}
}

Double Ended Link List

illustration




code

class Link {
public int iData;

public Link next;

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

public String toString() {
return "{" + iData + "} ";
}
}

class FirstLastList {
private Link first;
private Link last;

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

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

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

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

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

public int deleteFirst() {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
//main method
public class Deli {
public static void main(String[] args) {
FirstLastList theList = new FirstLastList();

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.deleteFirst();

System.out.println(theList);
}
}

Doubly Link List

Concept

According to National Institute of Standards and Technology
*a list in which each item has a link to the previous item as well as the next. This allows an accessing items backward, forward and deleting an item in a constant time.

[ ANIST ]

*each node has 2 pointers, one to the next and the other to the previous and the end is defined by NULL. With the doubly link list , we can move the current pointer backward and forward .

Illustration

Reference:
http://richardbowles.tripod.com/cpp/linklist/doublist.htm

implementation of doubly Link List

class Link {
public int iData;
public Link next;
public Link previous;

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

public String toString() {
return "{" + iData + "} ";
}
}

class DoublyLinkedList {
private Link first;
private Link last;

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

public boolean isEmpty() {
return first == null;
}
//insertion
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;
}
//deletion
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 method
public class MainClass {
public static void main(String[] args) {
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(lovely);
theList.insertFirst(matet);
theList.insertFirst(tina);

theList.insertLast(nemz);
theList.insertLast(nellen);
theList.insertLast(jeany);

System.out.println(theList);

theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(nemz);

System.out.println(theList);

theList.insertAfter(lovely, jerrold);
theList.insertAfter(nellen, baste);

System.out.println(theList);
}
}

reference:

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

Stack(Data Stucture)

Concept

According to wikipedia

- a stack is an abstack data type and its based on the principle of Last In First Out(LIFO).
-stacks are used to run a Java Virtual Machine.
-it is ubiquitous
a stack-based computer system
-one that stores temporary information

history of stack
-it was first proposed on 1995 and the patented in 1957 by Friedrich L. Bauer.

as an Abstact data Type
-the stack is a container of nodes and has basic operations.

Basic Operations
Push-adds a given node to the top and leaving previous nodes below.
Pop- removes and returns the current top node of the stack.
top(peek)- can return the current top element without removing it from the stack.

a typical stack is an area of a computer memory with a fixed origin and a variable size. The size of the stack is zero. A stack pointer ,usually in the form of a hardware registers.

some environments
*Dup(licate)- the top item is popped and pushed again.
*peek- the topmost item is popped, but the stack pointer is not change.
*Swap or exchange- the two topmost items on the stack exchange places.
*rotate- the topmost items are moved on the stack in a rotating fashion.

[1]
Illustration

[2]

[3]

implementation of stack using link list

class Link {
public int iData;

public Link next;

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

public String() {
return "{" + iData + "} ";
}
}

class LinkList {
private Link first;

public LinkList() {
first = null;
}

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

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

public int deleteFirst() {
Link temp = first;
first = first.next;
return temp.iData;
}

public String toString() {
String str="";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}

class LinkStack {
private LinkList theList;

public LinkStack() {
theList = new LinkList();
}

public void push(int j) {
theList.insertFirst(j);
}

public double pop() {
return theList.deleteFirst();
}

public boolean isEmpty() {
return (theList.isEmpty());
}

public String toString() {
return theList.toString();
}
}
//main method
public class Stack{
public static void main(String[] args) {
LinkStack theStack = new LinkStack();

theStack.push(me);
theStack.push(you);

System.out.println(theStack);

theStack.push(and you);
theStack.push(they);

System.out.println(theStack);

theStack.pop();
theStack.pop();

System.out.println(theStack);
}
}

[4]
reference::

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

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

[3]http://en.wikipedia.org/wiki/Stack_(data_structure)
[4]http://www.java2s.com/Tutorial/Java/0140__Collections/Demonstratingastackimplementedasalist.htm