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

清疚 2021-09-10 14:22 285阅读 0赞

一、栈

栈的定义  
栈（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、接口类

package com.lin.stack;
    
    /**
     * 功能概要：栈的接口类
     * 
     * @author linbingwen
     * @since  2015年8月29日 
     */
    public interface MyStack<T> {
    	
    	/**
    	 * 判断栈是否为空 
    	 * @author linbingwen
    	 * @since  2015年8月29日 
    	 * @return
    	 */
        boolean isEmpty();  
        
        /**
         * 清空栈 
         * @author linbingwen
         * @since  2015年8月29日
         */
        void clear();  
     
        /**
         * 栈的长度 
         * @author linbingwen
         * @since  2015年8月29日 
         * @return
         */
        int length();  
       
        /**
         * 数据入栈 
         * @author linbingwen
         * @since  2015年8月29日 
         * @param data
         * @return
         */
        boolean push(T data);  
     
        /**
         * 数据出栈 ，栈中删除
         * @author linbingwen
         * @since  2015年8月29日 
         * @return
         */
        T pop();  
        
        /**
         * 数据出栈 ,栈中不删除
         * @author linbingwen
         * @since  2015年8月29日 
         * @return
         */
        T peek();
        
    }

2、数组实现栈

package com.lin.stack;
    
    /**
     * 功能概要：数组实现栈
     * 
     * @author linbingwen
     * @since  2015年8月29日 
     */
    public class MyArrayStack<T> implements MyStack<T> {
    	
    	private Object[] objs = new Object[16];  
    	
    	private int size;
    
    	@Override
    	public boolean isEmpty() {
    		return size == 0;
    	}
    
    	@Override
    	public void clear() {
    	    for (int i = 0; i < objs.length; i++) {			
    			objs[i] = null;
    	    	size--;
    		}		
    	}
    
    	@Override
    	public int length() {
    		return size;
    	}
    
    	@Override
    	public boolean push(T data) {
    		if(size == (objs.length-1)){
    			Object[] temp = new Object[objs.length*2];
    			 for (int i = 0; i < objs.length; i++) {			
    				    temp[i]=objs[i];
    				}		
    			 objs= temp;
    		}
    		objs[size++]=data;
    		return true;
    	}
    
    	@Override
    	@SuppressWarnings("unchecked")  
    	public T pop() {		
    		return size == 0?null:(T) objs[(size--)-1];
    	}
    
    	@Override
    	@SuppressWarnings("unchecked")  
    	public T peek() {
    		return size == 0?null:(T) objs[size];
    	}
    
    }

3、链表实现栈

package com.lin.stack;
    
    /**
     * 功能概要：
     * 
     * @author linbingwen
     * @since  2015年8月29日 
     */
    public class MyListStack<T> implements MyStack<T>{
    	
    	private int size;
    	
    	private Node top;
    	
    	class Node{
    		T data;
    		Node pre;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		return size == 0;
    	}
    
    	@Override
    	public void clear() {
    		top = null;
    		
    	}
    
    	@Override
    	public int length() {
    		return size;
    	}
    
    	@Override
    	public boolean push(T data) {
    		Node node = new Node();
    		node.data=data;
    		if( null == top){
    			top = node;
    		}else {
    			node.pre = top;
    			top =node;
    		}
    		size++;
    		return true;
    	}
    
    	@Override
    	public T pop() {
    		if(size == 0){
    			return null;
    		}
    		T data = top.data;
    		top = top.pre;
    		size--;
    		return data;
    	}
    
    	@Override
    	public T peek() {
    		if(size == 0){
    			return null;
    		}
    		T data = top.data;
    		return data;
    	}
    
    }

4、测试

package com.lin.stack;
    
    /**
     * 功能概要：
     * 
     * @author linbingwen
     * @since  2015年8月29日 
     */
    public class StackTest {
    
    	/**
    	 * @author linbingwen
    	 * @since  2015年8月29日 
    	 * @param args    
    	 */
    	public static void main(String[] args) {
    		MyStack<Integer> myStack1 = new MyArrayStack<Integer>();
    		MyStack<Integer> myStack2 = new MyListStack<Integer>();
    		for(int i =0;i<30;i++){
    			myStack1.push(i);
    			myStack2.push(i);
    		}
    		System.out.println("数组实现的栈输出如下 ");
    		for(int j =0;j<30;j++){
    			
    			System.out.print(myStack1.pop()+"  ");
    		}
    		System.out.println();
    		System.out.println("链表实现的栈输出如下 ");
    		for(int k =0;k<30;k++){
    			System.out.print(myStack2.pop()+"  ");
    		}
    		
    	}
    
    }

输出结果如下：

![20150829174616134][]

或者 看这里：

**数组实现的栈输出如下   
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  **

[20150829174616134]: /images/20210811/8ac3cc9c1aba4519965fa3b3ca8dafe5.png