(堆)栈


		(堆)栈概述
栈是一种特殊的线性表，是操作受限的线性表
栈的定义和特点
•定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈
•特点：先进后出（FILO）或后进先出（LIFO）
 
栈的结构
如下图所示：
 
线性表的操作主要包括：
（1）清空(堆)栈
（2）判断是否为空
（3）元素的个数
（4）入栈
（5）出栈
（6）取栈顶元素
接口
由此，对队列的抽象数据类型定义Queue接口如下：
[java]  
package stack;  
/** 
 * (堆)栈 
 * @author Administrator 
 * 
 */  
public interface Stack {  
    /** 
     * 清空堆栈 
     */  
    public void clear();  
    /** 
     * 入栈 
     * @param obj 入栈的元素 
     */  
    public void push(Object obj);  
    /** 
     * 出栈 
     * @return 出栈的结果 
     */  
    public Object pop();  
    /** 
     * 判断是否为空 
     * @return 
     */  
    public boolean isEmpty();  
    /** 
     * 求元素的个数 
     * @return 元素的个数 
     */  
    public int size();  
    /** 
     * 取栈顶元素 
     * @return 栈顶元素 
     */  
    public Object peek();  
      
}  
 
顺序(堆)栈
 
结构模型

栈顶指针top,指向实际栈顶后的空位置，初值为0。
栈的初始空间大小为M
top=0,栈空，此时出栈，则下溢（underflow)；
top=M,栈满，此时入栈，则上溢（overflow)；
 
源代码
[java]  
package stack;  
/** 
 * 顺序(堆)栈 
 * @author Administrator 
 * 
 */  
public class ArrayStack implements Stack{  
    private static int DEFAULT_SIZE = 100;   
    private int Top;  
    Object array[];  
      
    public ArrayStack() {  
        Top = 0;  
        array = new Object[DEFAULT_SIZE];  
    }  
      
    public boolean isEmpty() {  
          
            return 0 == Top ;  
  
    }  
    public void expand() {  
        Object[] newArray = new Object[2 * array.length];  
        for(int i=0; i<array.length; i++) {  
            newArray[i] = array[i];  
        }  
        array = newArray;  
    }  
    /* 
    public void expand() { 
        try { 
            Object[] newArray = new Object[2*DEFAULT_SIZE]; 
            for(int i=0; i<array.length; i++) { 
                newArray[i] = array[i]; 
            } 
            array = newArray; 
        }catch(OutOfMemoryError e) { 
            System.out.println("error in expand of Stack class!"); 
            //e.printStackTrace(); 
        } 
         
         
        DEFAULT_SIZE = 2*DEFAULT_SIZE; 
    } 
    */  
    public void push(Object obj) {  
        if(Top == array.length) {  
            expand();  
        }     
        array[Top] =obj;  
        Top ++;  
          
    }  
      
    public Object pop() {  
        if(0 == Top) throw new IllegalStateException();  
        Object val = array[-- Top];  
        array[Top] = null;  
        return val;  
          
    }  
      
    public void clear() {  
        for(int i=0; i<array.length; i++) {  
            array[i] = null;  
            Top = 0;  
        }  
    }  
      
    public Object peek() {  
        if(0 == Top) throw new IllegalStateException();  
        return array[Top - 1];  
    }  
      
    public int size() {  
        return Top;  
    }  
      
    public String toString() {  
        String s = "[";  
        for(int i=Top-1; i>=0 ; i--) {  
            s = s + array[i];  
            s = s + ",  ";  
        }  
        s = s + "]";  
        return s;  
    }  
      
}  
 
 
链式(堆)栈
 
结构模型

源代码

补充：软件开发 , Java ,