java实现数据结构——栈Stack与队列Queue

栈（Stack）作为一个先进后出(FILO) 的线性结构，只支持在栈顶的插入和弹出。

队列（Queue）作为一个先进先出（FIFO） 的线性结构，支持在队首获取元素，在对尾插入元素。

栈的实现：

public class StackDemo<E> {private Object[] data = null;private int capacity;private int top;/** * 默认栈容量为10 */public StackDemo() {this(10);}/** * 初始化栈容量 *  * @param initSize */public StackDemo(int initSize) {if (initSize >= 0) {capacity = initSize;data = new Object[initSize];top = 0;} else {throw new RuntimeException("初始化栈容量大小不能小于0" + initSize);}}/** * 判断栈是否为空 *  * @return */public boolean isEmpty() {return top == 0 ? true : false;}/** * 获取栈顶元素，但是不弹出 *  */public E peek() {return (E) data[top - 1];}/** * 弹出栈顶元素 *  * @return */public E pop() {if (isEmpty()) {throw new RuntimeException("栈已空，没有元素可以弹出。");}return (E) data[--top];}/** * 向栈顶压入e *  * @param e * @return */public boolean push(E e) {ensureCapacity();data[top] = e;top++;return true;}/** * 检查存储数据数组容量，如果数组已满，则扩容否则不操作。 */private void ensureCapacity() {if (top == capacity) {capacity *= 2;Object[] newData = new Object[capacity];for (int i = 0; i < top; i++) {newData[i] = data[i];}data = newData;}}@Overridepublic String toString() {String string = "";for (int i = 0; i < top; i++) {string += (data[i] + " ");}return string;}/** * @param args */public static void main(String[] args) {// TODO 自动生成的方法存根StackDemo<Double> stackDemo = new StackDemo<>();for (int i = 0; i < 15; i++) {stackDemo.push(i+1.0);System.out.println(stackDemo.toString());}System.out.println(stackDemo.peek() + " ");for (int i = 0; i < 15; i++) {System.out.println(stackDemo.pop() + "");}}}

队列的实现

/***队列的实现*@param<E>*@author<ahref="mailto:bao.yiming@live.cn"mce_href="mailto:bao.yiming@live.cn">BaoYiming</a>*/publicclassQueue<E>{Object[]data=null;privateintcapacity;//capacity：队的容量privateinttail;//tail：队尾指针/***初始化为声明大小，则设置为10。*/Queue(){this(10);}/***初始化队列，声明保存数据的数组大小。*@paraminitialSize队列的初始化大小*/Queue(intinitialSize){if(initialSize>=0){this.capacity=initialSize;data=newObject[initialSize];tail=0;}else{thrownewRuntimeException("初始化大小不能小于0："+initialSize);}}/***判断队列是否为空*@return*/publicbooleanempty(){returntail==0?true:false;}/***在队尾插入元素*@parame待插入的元素*@return*/publicbooleanadd(Ee){ensureCapacity();data[tail]=e;++tail;returntrue;}/***获取队首的元素内容，但不将该元素出队。*@return*/publicEpeek(){return(E)data[0];}/***将队首元素出队。*@return*/publicEpoll(){Ee=(E)data[0];for(intindex=1;index<tail;++index){data[index-1]=data[index];}data[tail-1]=null;–tail;returne;}/***检查存储数据的数组容量，如果数组已经满，则扩充容量；否则不操作。*/privatevoidensureCapacity(){intindex;if(tail==capacity){capacity*=2;Object[]newData=newObject[capacity];for(index=0;index<tail;++index){newData[index]=data[index];}data=newData;}}@OverridepublicStringtoString(){Stringstr="";for(intindex=0;index<tail;++index){if(data[index]!=null){str+=(data[index]+"");}}returnstr;}}

只有一条路不能选择——那就是放弃的路;