前言
听着天籁，我是个音乐迷。时间充实着，会过得很快。我马上也可以到傍晚的时候去乐室吹我心爱的萨克斯。
嘟嘟嘟... 我会吹一首简单的歌咯，哈哈我想到了一个神奇的比喻，待会说。
栈ADT模型（又称LIFO表）
栈（stack）插入和删除只能在一个位置上进行的表。该位置是表的末端但是叫做栈的顶（top）。基本操作：进栈（push相当于插入）和出栈（pop相当于删除）。又称LIFO表，后进先出。
相当于
就想快速呼吸一样。先吸进来的空气，先呼出去。
你是否记住了？
栈的源码和数组实现
java.util.Stack
不得不申明下，小朽研究不深，如果大家看到了希望能指点指点我。有些时候，说错了，我马上会改正的。谢谢。先介绍类的结构图
下面是源码 java.util.Stack
/*
* Copyright (c) 1994, 2010, Oracle and/or its affiliates. All rights reserved.
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
package java.util;
/**
* The <code>Stack</code> class represents a last-in-first-out
* (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
* operations that allow a vector to be treated as a stack. The usual
* <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
* method to <tt>peek</tt> at the top item on the stack, a method to test
* for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
* the stack for an item and discover how far it is from the top.
* <p>
* When a stack is first created, it contains no items.
*
* <p>A more complete and consistent set of LIFO stack operations is
* provided by the {@link Deque} interface and its implementations, which
* should be used in preference to this class. For example:
* <pre> {@code
* Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
*
* @author Jonathan Payne
* @since JDK1.0
*/
public
class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
}
/**
* Pushes an item onto the top of this stack. This has exactly
* the same effect as:
* <blockquote><pre>
* addElement(item)</pre></blockquote>
*
* @param item the item to be pushed onto this stack.
* @return the <code>item</code> argument.
* @see java.util.Vector#addElement
*/
public E push(E item) {
addElement(item);
return item;
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
/**
* Tests if this stack is empty.
*
* @return <code>true</code> if and only if this stack contains
* no items; <code>false</code> otherwise.
*/
public boolean empty() {
return size() == 0;
}
/**
* Returns the 1-based position where an object is on this stack.
* If the object <tt>o</tt> occurs as an item in this stack, this
* method returns the distance from the top of the stack of the
* occurrence nearest the top of the stack; the topmost item on the
* stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
* method is used to compare <tt>o</tt> to the
* items in this stack.
*
* @param o the desired object.
* @return the 1-based position from the top of the stack where
* the object is located; the return value <code>-1</code>
* indicates that the object is not on the stack.
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1224463164541339165L;
}
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 */
}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);
}
④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());
}
}
}
栈的应用
四则运算，计算器编程。这些，我想原理才是重要的。
时间： 2024-09-11 10:04:31