Stack Implementation

//a class
class Link{
public int iData=0;


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

}

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

//the classfor operations on the stack
class StackList{
private Link first;

public StackList(){ //declaring as empty or null
first=null;

}

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

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

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

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

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

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

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

theList.insertFirst(116);//show the insertion of items
theList.insertFirst(82);
theList.insertFirst(34);

theList.deleteFirst();//show the delete item/element

theList.displayList();
}
}

Doubly-Linked List

//this is the implementation of
//Doubly-Linked List

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) { //method for insertFirst
Link newLink = new Link(id,dd);
if (isEmpty ())
last = newLink;
newLink.next = first;
first = newLink;
}
public void insertLast(int id,double dd) { //method for insertLast
Link newLink = new Link(id,dd);
if (isEmpty()
first = newLink;
else
last.next = newLink;
last = newLink;
}
public Link deleteFirst(int id,double dd) { //method for deletion
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 FirstLastApps{ //for application
public static void main(String[] args) {
FirstLastList theList = new FirstLastList();

theList.insertFirst(16,3.89);
theList.insertFirst(56,6.45);
theList.insertLast(26,5.00);
theList.insertLast(86,6,90);


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

Double-ended link list

• list with first and last references

• allow for insertions in the front or in the back of the list
• Double-ended, single-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.

  Nodes have only forward pointers, so the natural traversal is forward, and nodes may be inserted or removed after any node.

• Double-ended, double-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.

  Nodes have both forward and backward pointers, so both traversals are natural, and nodes may be inserted or removed before or after any node.

//code for double-ended

class Link { //a class of methods
public int iData;
public double dData:
public Link next;

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

dData=dd;
}
//display elements
public void displayLink(){

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

//another class of methods

class DoubleEndList {
private Link first;
private Link last;


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

//insertion method at first
public void insertFirst(int id,double dd) {
Link newLink = new Link(id,dd);

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

first = newLink;
}
//insertion method at last
public void insertLast(int id,double dd) {
Link newLink = new Link(id,dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}


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

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

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

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

//the main class

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

DoubleEndList theList = new DoubleEndList();

//application of the insertion methods on the first and the last
theList.insertFirst(44,87);
theList.insertFirst(56,09);
theList.insertLast(07,85);
theList.insertLast(788,02);

System.out.println(theList);

//for deletion
theList.deleteFirst();
theList.deleteFirst();
System.out.println(theList);
}
}
references:

my.safaribooksonline.com/
www-personal.umich.edu/~williams/archive/forth/lists/index.html

STACK

Definition:

• is an abstract data type and data structure based on the principle of Last In First out (LIFO).
• are used extensively at every level of a modern computer system.
• s a container of 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.  [1.] [en.wikipedia.org/wiki/Stack_(data_structure)]

      The key methods of the Stack class are push(), peek(), pop(), empty() and search():
            push() - adds an element to the top of the stack.
            peek() - returns the first element from the top of the stack without removing it from the                                stack.
            pop() - as peek() but removes it from the stack.
            empty() - checks wheter there are elements in the stack or not

            search() - returns the position of an element in the stack. [2.] http://www.javadb.com/using-                                 a-stack

Illustration:

This figure is a representation of stack from [1.] http://en.wikipedia.org/wiki/Stack_(data_structure)

references:

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

[2.] http://www.javadb.com/using-a-stack