java数据结构之栈
1，栈接口package pku.ss.datastructure.IStackLi;public interface IStackLi {/** * Get the size of the stack * @return size of the stack */public int getSize();/** * Judge that if the stack is full * @return true or false */public boolean isFull();/** * Judge that if the stack is empty * @return true or false */public boolean isEmpty();/** * Set the stack to be empty */public void makeEmpty();/** * Push a element x into stack, if the operation is right then return true, * else return false * @param x * @return true or false */public boolean push(Object x);/** * return the top element of the stack * @return the top element */public Object top();/** * Pop the top element from the stack, if the operation is right, then return* true, else return false * @return true or false */public boolean pop();}
2，栈的实现
package pku.ss.datastructure.StackLi;import pku.ss.datastructure.IStackLi.IStackLi;public class StackLi implements IStackLi {private int maxSize;private int size;private ListNode topOfStack;public StackLi(int maxSize) {this.maxSize = maxSize;size = 0;topOfStack = null;}@Overridepublic int getSize() {return this.size;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size > maxSize - 1;}@Overridepublic void makeEmpty() {size = 0;topOfStack = null;}@Overridepublic boolean pop() {if (isEmpty()) {System.out.println(" Atempt to pop from a empty stack!");return false;} else {topOfStack = topOfStack.next;size--;return true;}}@Overridepublic boolean push(Object x) {if (isFull()) {System.out.println(" Atempt to push into a full stack!");return false;} else {ListNode temp = new ListNode(x);temp.next = topOfStack;topOfStack = temp;size++;return true;}}@Overridepublic Object top() {if (isEmpty()) {System.out.println(" Atempt to get the top element from a empty stack!");return null;}return topOfStack.element;}}
3，节点类型
package pku.ss.datastructure.StackLi;public class ListNode {ListNode(Object theElement) {this(theElement, null);}ListNode(Object theElement, ListNode aNext) {element = theElement;next = aNext;}Object element;//节点中的元素ListNode next; //指向下一个节点}
4，测试类
package pku.ss.datastructure.Demo;import pku.ss.datastructure.StackLi.StackLi;public class StackLiDemo {/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubStackLi stack = new StackLi(5);stack.push("A");stack.push("B");stack.push("C");stack.push("D");stack.push("E");stack.push("F");stack.push("G");stack.push("H");System.out.println("**********************");System.out.println("The size of the stack is: " + stack.getSize());System.out.println("**********************");System.out.println("The top element of the stack is: " + stack.top());System.out.println("**********************");stack.makeEmpty();System.out.println("The top element of the stack is: " + stack.top());System.out.println("**********************");System.out.println("The size of the stack is: " + stack.getSize());}}
页:
[1]