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