Created
August 21, 2011 14:25
-
-
Save showsky/1160676 to your computer and use it in GitHub Desktop.
Java implement Stack use Link List DS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 實作 Stack | |
* 使用 Link List 資料結構 | |
* 1. Satck 具有 LIFO 後進先出的特性 | |
* 2. push 和 pop 都在同一端操作,且有個 top 永遠指向頂端 | |
* @author Cheng-Ting | |
* | |
*/ | |
/** | |
* Link List | |
* 節點的資料結構 | |
*/ | |
class Node { | |
private int val; | |
private Node next = null; | |
public Node(int val, Node next) { | |
this.setVal(val); | |
this.setNext(next); | |
} | |
public void setVal(int val) { | |
this.val = val; | |
} | |
public int getVal() { | |
return this.val; | |
} | |
public void setNext(Node next) { | |
this.next = next; | |
} | |
public Node getNext() { | |
return this.next; | |
} | |
public String toString() { | |
return String.valueOf(this.val); | |
} | |
} | |
/** | |
* Stack ADT 結構 | |
* @author Cheng-Ting | |
* | |
*/ | |
interface stackADT { | |
abstract public void createStack(); | |
abstract public void push(Node node); | |
abstract public Node pop(); | |
abstract public boolean isEmpty(); | |
abstract public boolean isFull(); | |
} | |
/** | |
* | |
* 實作 Stack | |
* @author Cheng-Ting | |
* | |
*/ | |
public class Stack implements stackADT { | |
private Node top = null; | |
public Stack() { | |
this.createStack(); | |
} | |
/** | |
* 建立 Stack | |
*/ | |
public void createStack() { | |
this.top = null; | |
} | |
/** | |
* 加入節點 | |
*/ | |
public void push(Node node) { | |
if(this.isEmpty()) { | |
this.top = node; | |
} else { | |
node.setNext(this.top); | |
top = node; | |
} | |
} | |
/** | |
* 取出節點 | |
*/ | |
public Node pop() { | |
Node tmp = null; | |
if(this.isEmpty()) { | |
System.out.println("statck it empty"); | |
} else { | |
tmp = this.top; | |
this.top = this.top.getNext(); | |
} | |
return tmp; | |
} | |
/** | |
* 是否為空 | |
*/ | |
public boolean isEmpty() { | |
boolean var; | |
if(this.top == null) { | |
var = true; | |
} else { | |
var = false; | |
} | |
return var; | |
} | |
/** | |
* 是否為滿,因為使用 Link List 所以空間不限 | |
*/ | |
public boolean isFull() { | |
return false; | |
} | |
/** | |
* 使用方法 | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
Stack stack = new Stack(); | |
stack.push(new Node(1, null)); | |
stack.push(new Node(2, null)); | |
stack.push(new Node(3, null)); | |
System.out.println(stack.pop()); | |
System.out.println(stack.pop()); | |
System.out.println(stack.pop()); | |
System.out.println(stack.pop()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment