Java栈的实例-数组和链表两种方法（转）

一、栈

栈的定义 
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。 
(1)通常称插入、删除的这一端为栈顶 （Top），另一端称为栈底 （Bottom）。 
(2)当表中没有元素时称为空栈。 
(3)栈为后进先出（Last In First Out）的线性表，简称为 LIFO 表。 
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中" 
最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部， 
要到最后才能删除。 

2、栈的基本运算 

（1） 判断栈是否为空 
    boolean isEmpty();      
（2）清空栈 
    void clear();  
（3）栈的长度 
    int length();     
（4）数据入栈 
    boolean push(T data);   
 （5）数据出栈 ，栈中删除
    T pop();     
 （6）数据出栈 ,栈中不删除

    T peek();

二、代码编写

1、接口类

[java] view plain copy
 
  1. package com.lin.stack;  
  2.   
  3. /** 
  4.  * 功能概要：栈的接口类 
  5.  *  
  6.  * @author linbingwen 
  7.  * @since  2015年8月29日  
  8.  */  
  9. public interface MyStack<T> {  
  10.       
  11.     /** 
  12.      * 判断栈是否为空  
  13.      * @author linbingwen 
  14.      * @since  2015年8月29日  
  15.      * @return 
  16.      */  
  17.     boolean isEmpty();    
  18.       
  19.     /** 
  20.      * 清空栈  
  21.      * @author linbingwen 
  22.      * @since  2015年8月29日 
  23.      */  
  24.     void clear();    
  25.    
  26.     /** 
  27.      * 栈的长度  
  28.      * @author linbingwen 
  29.      * @since  2015年8月29日  
  30.      * @return 
  31.      */  
  32.     int length();    
  33.      
  34.     /** 
  35.      * 数据入栈  
  36.      * @author linbingwen 
  37.      * @since  2015年8月29日  
  38.      * @param data 
  39.      * @return 
  40.      */  
  41.     boolean push(T data);    
  42.    
  43.     /** 
  44.      * 数据出栈 ，栈中删除 
  45.      * @author linbingwen 
  46.      * @since  2015年8月29日  
  47.      * @return 
  48.      */  
  49.     T pop();    
  50.       
  51.     /** 
  52.      * 数据出栈 ,栈中不删除 
  53.      * @author linbingwen 
  54.      * @since  2015年8月29日  
  55.      * @return 
  56.      */  
  57.     T peek();  
  58.       
  59. }  




2、数组实现栈

[java] view plain copy
 
  1. package com.lin.stack;  
  2.   
  3. /** 
  4.  * 功能概要：数组实现栈 
  5.  *  
  6.  * @author linbingwen 
  7.  * @since  2015年8月29日  
  8.  */  
  9. public class MyArrayStack<T> implements MyStack<T> {  
  10.       
  11.     private Object[] objs = new Object[16];    
  12.       
  13.     private int size;  
  14.   
  15.     @Override  
  16.     public boolean isEmpty() {  
  17.         return size == 0;  
  18.     }  
  19.   
  20.     @Override  
  21.     public void clear() {  
  22.         for (int i = 0; i < objs.length; i++) {            
  23.             objs[i] = null;  
  24.             size--;  
  25.         }         
  26.     }  
  27.   
  28.     @Override  
  29.     public int length() {  
  30.         return size;  
  31.     }  
  32.   
  33.     @Override  
  34.     public boolean push(T data) {  
  35.         if(size == (objs.length-1)){  
  36.             Object[] temp = new Object[objs.length*2];  
  37.              for (int i = 0; i < objs.length; i++) {           
  38.                     temp[i]=objs[i];  
  39.                 }         
  40.              objs= temp;  
  41.         }  
  42.         objs[size++]=data;  
  43.         return true;  
  44.     }  
  45.   
  46.     @Override  
  47.     @SuppressWarnings("unchecked")    
  48.     public T pop() {          
  49.         return size == 0?null:(T) objs[(size--)-1];  
  50.     }  
  51.   
  52.     @Override  
  53.     @SuppressWarnings("unchecked")    
  54.     public T peek() {  
  55.         return size == 0?null:(T) objs[size];  
  56.     }  
  57.   
  58. }  

3、链表实现栈

[java] view plain copy
 
  1. package com.lin.stack;  
  2.   
  3. /** 
  4.  * 功能概要： 
  5.  *  
  6.  * @author linbingwen 
  7.  * @since  2015年8月29日  
  8.  */  
  9. public class MyListStack<T> implements MyStack<T>{  
  10.       
  11.     private int size;  
  12.       
  13.     private Node top;  
  14.       
  15.     class Node{  
  16.         T data;  
  17.         Node pre;  
  18.     }  
  19.   
  20.     @Override  
  21.     public boolean isEmpty() {  
  22.         return size == 0;  
  23.     }  
  24.   
  25.     @Override  
  26.     public void clear() {  
  27.         top = null;  
  28.           
  29.     }  
  30.   
  31.     @Override  
  32.     public int length() {  
  33.         return size;  
  34.     }  
  35.   
  36.     @Override  
  37.     public boolean push(T data) {  
  38.         Node node = new Node();  
  39.         node.data=data;  
  40.         if( null == top){  
  41.             top = node;  
  42.         }else {  
  43.             node.pre = top;  
  44.             top =node;  
  45.         }  
  46.         size++;  
  47.         return true;  
  48.     }  
  49.   
  50.     @Override  
  51.     public T pop() {  
  52.         if(size == 0){  
  53.             return null;  
  54.         }  
  55.         T data = top.data;  
  56.         top = top.pre;  
  57.         size--;  
  58.         return data;  
  59.     }  
  60.   
  61.     @Override  
  62.     public T peek() {  
  63.         if(size == 0){  
  64.             return null;  
  65.         }  
  66.         T data = top.data;  
  67.         return data;  
  68.     }  
  69.   
  70. }  


4、测试

[java] view plain copy
 
  1. package com.lin.stack;  
  2.   
  3. /** 
  4.  * 功能概要： 
  5.  *  
  6.  * @author linbingwen 
  7.  * @since  2015年8月29日  
  8.  */  
  9. public class StackTest {  
  10.   
  11.     /** 
  12.      * @author linbingwen 
  13.      * @since  2015年8月29日  
  14.      * @param args     
  15.      */  
  16.     public static void main(String[] args) {  
  17.         MyStack<Integer> myStack1 = new MyArrayStack<Integer>();  
  18.         MyStack<Integer> myStack2 = new MyListStack<Integer>();  
  19.         for(int i =0;i<30;i++){  
  20.             myStack1.push(i);  
  21.             myStack2.push(i);  
  22.         }  
  23.         System.out.println("数组实现的栈输出如下 ");  
  24.         for(int j =0;j<30;j++){  
  25.               
  26.             System.out.print(myStack1.pop()+"  ");  
  27.         }  
  28.         System.out.println();  
  29.         System.out.println("链表实现的栈输出如下 ");  
  30.         for(int k =0;k<30;k++){  
  31.             System.out.print(myStack2.pop()+"  ");  
  32.         }  
  33.           
  34.     }  
  35.   
  36. }  

输出结果如下：

或者 看这里：

数组实现的栈输出如下 
29  28  27  26  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10  9  8  7  6  5  4  3  2  1  0  
链表实现的栈输出如下 
29  28  27  26  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10  9  8  7  6  5  4  3  2  1  0 

http://blog.csdn.net/evankaka/article/details/48088983

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/softidea/p/5271874.html