Skip to content

Instantly share code, notes, and snippets.

@showsky
Created August 21, 2011 14:25
Show Gist options
  • Save showsky/1160676 to your computer and use it in GitHub Desktop.
Save showsky/1160676 to your computer and use it in GitHub Desktop.
Java implement Stack use Link List DS
/**
* 實作 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