②泡茶看<数据结构>，喜欢看源码-栈ADT

前言

　　听着天籁，我是个音乐迷。时间充实着，会过得很快。我马上也可以到傍晚的时候去乐室吹我心爱的萨克斯。

　　　　　　　　　　　　　　　　　　　　嘟嘟嘟... 我会吹一首简单的歌咯，哈哈我想到了一个神奇的比喻，待会说。

栈ADT模型（又称LIFO表）

　　栈（stack）插入和删除只能在一个位置上进行的表。该位置是表的末端但是叫做栈的顶（top）。基本操作：进栈（push相当于插入）和出栈（pop相当于删除）。又称LIFO表，后进先出。

　　　　　　相当于

　　　　　　　　　　　　　　　　　　　　就想快速呼吸一样。先吸进来的空气，先呼出去。

　　　　　　　　　　　　　　　　　　　　你是否记住了？

栈的源码和数组实现

　　java.util.Stack

　　 不得不申明下，小朽研究不深，如果大家看到了希望能指点指点我。有些时候，说错了，我马上会改正的。谢谢。先介绍类的结构图

　　　　下面是源码 java.util.Stack

  1 /*
  2  * Copyright (c) 1994, 2010, Oracle and/or its affiliates. All rights reserved.
  3  * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  4  *
  5  *
  6  *
  7  *
  8  *
  9  *
 10  *
 11  *
 12  *
 13  *
 14  *
 15  *
 16  *
 17  *
 18  *
 19  *
 20  *
 21  *
 22  *
 23  *
 24  */
 25 
 26 package java.util;
 27 
 28 /**
 29  * The <code>Stack</code> class represents a last-in-first-out
 30  * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 31  * operations that allow a vector to be treated as a stack. The usual
 32  * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 33  * method to <tt>peek</tt> at the top item on the stack, a method to test
 34  * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 35  * the stack for an item and discover how far it is from the top.
 36  * <p>
 37  * When a stack is first created, it contains no items.
 38  *
 39  * <p>A more complete and consistent set of LIFO stack operations is
 40  * provided by the {@link Deque} interface and its implementations, which
 41  * should be used in preference to this class.  For example:
 42  * <pre>   {@code
 43  *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 44  *
 45  * @author  Jonathan Payne
 46  * @since   JDK1.0
 47  */
 48 public
 49 class Stack<E> extends Vector<E> {
 50     /**
 51      * Creates an empty Stack.
 52      */
 53     public Stack() {
 54     }
 55 
 56     /**
 57      * Pushes an item onto the top of this stack. This has exactly
 58      * the same effect as:
 59      * <blockquote><pre>
 60      * addElement(item)</pre></blockquote>
 61      *
 62      * @param   item   the item to be pushed onto this stack.
 63      * @return  the <code>item</code> argument.
 64      * @see     java.util.Vector#addElement
 65      */
 66     public E push(E item) {
 67         addElement(item);
 68 
 69         return item;
 70     }
 71 
 72     /**
 73      * Removes the object at the top of this stack and returns that
 74      * object as the value of this function.
 75      *
 76      * @return  The object at the top of this stack (the last item
 77      *          of the <tt>Vector</tt> object).
 78      * @throws  EmptyStackException  if this stack is empty.
 79      */
 80     public synchronized E pop() {
 81         E       obj;
 82         int     len = size();
 83 
 84         obj = peek();
 85         removeElementAt(len - 1);
 86 
 87         return obj;
 88     }
 89 
 90     /**
 91      * Looks at the object at the top of this stack without removing it
 92      * from the stack.
 93      *
 94      * @return  the object at the top of this stack (the last item
 95      *          of the <tt>Vector</tt> object).
 96      * @throws  EmptyStackException  if this stack is empty.
 97      */
 98     public synchronized E peek() {
 99         int     len = size();
100 
101         if (len == 0)
102             throw new EmptyStackException();
103         return elementAt(len - 1);
104     }
105 
106     /**
107      * Tests if this stack is empty.
108      *
109      * @return  <code>true</code> if and only if this stack contains
110      *          no items; <code>false</code> otherwise.
111      */
112     public boolean empty() {
113         return size() == 0;
114     }
115 
116     /**
117      * Returns the 1-based position where an object is on this stack.
118      * If the object <tt>o</tt> occurs as an item in this stack, this
119      * method returns the distance from the top of the stack of the
120      * occurrence nearest the top of the stack; the topmost item on the
121      * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
122      * method is used to compare <tt>o</tt> to the
123      * items in this stack.
124      *
125      * @param   o   the desired object.
126      * @return  the 1-based position from the top of the stack where
127      *          the object is located; the return value <code>-1</code>
128      *          indicates that the object is not on the stack.
129      */
130     public synchronized int search(Object o) {
131         int i = lastIndexOf(o);
132 
133         if (i >= 0) {
134             return size() - i;
135         }
136         return -1;
137     }
138 
139     /** use serialVersionUID from JDK 1.0.2 for interoperability */
140     private static final long serialVersionUID = 1224463164541339165L;
141 }

java.util.Stack

　　　　①Pushes an item onto the top of this stack.

public E push(E item) {
        addElement(item);

        return item;
    }

　　　　从类的结构图可以看出,addElement是Stack父类Vector封装，用于一切其子类的封装。

　　　　　#Adds the specified component to the end of this vector

public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

　　　　②Removes the object at the top of this stack and returns the onject that object as the value of this function

public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

　　　　　同样，跟addElement一样removeElementAt存在Vector

　　　　　　　#Deletes the component at the specified index.

 public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }

View Code

　　　　　But,这个是什么 peek（），别慌它也是存在Stack类中下面我们讲这个

　　　　③Looks at the object at the top of this stack without remocing it

public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

　　　　　　跟addElement,removeElementAt一样，elementAt存在Vector

　　　　　　　　#Returns the component at the specified index.

public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }

        return elementData(index);
    }

View Code

　　　④Tests if this stack is empty

public boolean empty() {
        return size() == 0;
    }

　　　　size() 来源于Vector,用于获取大小

　　　⑤Stack中其他，就不做介绍罗列下

　　　　void　Stack()　　//create an empty stack
　　　　int　search(Object o)　　//return the 1 - based position where an obj is on this stack

　　数组实现

package sedion.jeffli.bean;

/**
 * qq 1928348753
 * blog http://www.cnblogs.com/Alandre/
 * @author Jeff Li
 */
public class myS {       
   
  Object[] data; 
   
  int maxSize;   
  int top;       
   
  public myS(int maxSize) {       
      this.maxSize = maxSize;       
      data = new Object[maxSize];       
      top = -1;       
  }       
    
  /**
   * 获取堆栈长度
   * @return 堆栈长度
   */ 
  public int getSize() 
  { 
    return maxSize; 
  } 
   
  /**
   * 返回栈中元素的个数
   * @return 栈中元素的个数
   */ 
  public int getElementCount() 
  { 
    return top; 
  } 
   
  /**
   * 判断栈空
   * @return 栈空
   */ 
  public boolean isEmpty() 
  { 
    return top == -1; 
  } 
   
  /**
   * 判断栈满
   * @return 栈满
   */ 
  public boolean isFull() 
  { 
    return top+1 == maxSize; 
  } 
   
  /**   
   * 依次加入数据   
   * @param data 加入的数据   
   * @return 添加是否成功   
   */       
  public boolean push(Object data) {       
    if(isFull())  
    {       
        System.out.println("栈已满!");       
        return false;       
    }       
    this.data[++top] = data;       
    return true;       
  }       
         
  /**   
   * 从栈中取出数据   
   * @return 取出的数据   
   */       
  public Object pop() throws Exception{       
    if(isEmpty())  
    {       
        throw new Exception("栈已空!");       
    }       
    return this.data[top--];       
  }       
   
  /**
   * 返回栈顶元素
   * @return
   */ 
  public Object peek() 
  { 
    return this.data[getElementCount()];   
  } 
 
 
  public static void main(String[] args) throws Exception {       
      myS stack=new myS(1000);       
      stack.push(new String("1"));       
      stack.push(new String("2"));       
      stack.push(new String("3"));       
      stack.push(new String("4"));       
      stack.push(new String("5"));   
      
      System.out.println("栈顶元素"+stack.peek());  
             
      while(stack.top>=0)       
      {       
          System.out.println("Position["+stack.top+"]:"+stack.pop());       
      }              
  }       
}

栈的应用

　　　　四则运算，计算器编程。这些，我想原理才是重要的。

　　　　这是一些资料共享应用　　

　　　　　　　　http://blog.sina.com.cn/s/blog_69e8f4c20101308b.html

　　　　　　　　http://justsee.iteye.com/blog/1125174　　　

寄读者，寄知识来源

　　　读者，你好！你我不相识，谢谢你们支持。我的梦想会越来越接近。keep on，共勉！

　　　知识来源　http://book.douban.com/doulist/3563883/　　

　　　　　　　　http://www.cnblogs.com/shitianzeng/articles/2336765.html