栈（Stack源码分析）
2017-06-28 本文已影响0人
曾大稳丶
栈(stack)
- 从数据结构的角度理解：是一组数据的存放方式，特点为LIFO，即后进先出（Last in, first out）。在这种数据结构中，数据像积木那样一层层堆起来，后面加入的数据就放在最上层。使用的时候，最上层的数据第一个被用掉，这就叫做"后进先出"。
- 从代码运行方式角度理解：是调用栈，表示函数或子例程像堆积木一样存放，以实现层层调用。程序运行的时候，总是先完成最上层的调用，然后将它的值返回到下一层调用，直至完成整个调用栈，返回最后的结果。
- 从内存区域的角度上理解：是存放数据的一种内存区域。程序运行的时候，需要内存空间存放数据。一般来说，系统会划分出两种不同的内存空间：一种叫做
stack（栈），另一种叫做heap（堆）。
参考链接:Stack的三种含义
(图片均来源于网络)
本文所述是站在数据结构的角度。
栈可以通过链表和数组实现，先看通过数组实现的方式。
可以通过查看Stack源码学习
可以看到Stack是Vector的子类，Vector本身是一个可增长的线程安全的对象数组（ a growable array of objects）
里面主要是如下方法
E push(E item)
把项压入堆栈顶部。
E pop()
移除堆栈顶部的对象，并作为此函数的值返回该对象。
E peek()
查看堆栈顶部的对象，但不从堆栈中移除它。
boolean empty()
测试堆栈是否为空。
int search(Object o)
返回对象在堆栈中的位置，以 1 为基数。
push
/**
* 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;
}
就是调用了Vector的addElement
/**
* Adds the specified component to the end of this vector,
* increasing its size by one. The capacity of this vector is
* increased if its size becomes greater than its capacity.
*
* <p>This method is identical in functionality to the
* {@link #add(Object) add(E)}
* method (which is part of the {@link List} interface).
*
* @param obj the component to be added
*/
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
/**
* This implements the unsynchronized semantics of ensureCapacity.
* Synchronized methods in this class can internally call this
* method for ensuring capacity without incurring the cost of an
* extra synchronization.
*
* @see #ensureCapacity(int)
*/
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
就是判断是否扩容，然后赋值即可
pop和peek
/**
* 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);
}
Vector中
/**
* Deletes the component at the specified index. Each component in
* this vector with an index greater or equal to the specified
* {@code index} is shifted downward to have an index one
* smaller than the value it had previously. The size of this vector
* is decreased by {@code 1}.
*
* <p>The index must be a value greater than or equal to {@code 0}
* and less than the current size of the vector.
*
* <p>This method is identical in functionality to the {@link #remove(int)}
* method (which is part of the {@link List} interface). Note that the
* {@code remove} method returns the old value that was stored at the
* specified position.
*
* @param index the index of the object to remove
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
*/
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 */
}
/**
* Returns the component at the specified index.
*
* <p>This method is identical in functionality to the {@link #get(int)}
* method (which is part of the {@link List} interface).
*
* @param index an index into this vector
* @return the component at the specified index
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
*/
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
先调用peek()得到需要出栈的对象，也就是数组顶部的对象，在调用Vector的removeElementAt移除。
empty
/**
* 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;
}
search
/**
* 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;
}
参考链接:
java.util.Stack类简介
接下来看看使用链式的方式实现
链式结构
代码表示:
private Node top = null;
private int number = 0;
class Node {
public T Item;
public Node Next;
}
入栈
入栈：将
top的指向换为入栈的对象，然后将这个入栈的对象指向上一个入栈的对象即可。
代码表示:
public void push(T node) {
Node oldFirst = top;
top = new Node();
top.Item = node;
top.Next = oldFirst;
number++;
}
出栈
出栈：根据出栈的对象得到
next，然后top指向即可。代码表示:
public T pop() {
T item = top.Item;
top = top.Next;
number--;
return item;
}
一个伪代码类表示:
/**
* Created by zzw on 2017/6/27.
* Version:
* Des:
*/
public class StackLinkedList<T> {
private Node top = null;
private int number = 0;
class Node {
public T Item;
public Node Next;
}
public void push(T node) {
Node oldFirst = top;
top = new Node();
top.Item = node;
top.Next = oldFirst;
number++;
}
public T pop() {
T item = top.Item;
top = top.Next;
number--;
return item;
}
}
参考连接:
浅谈算法和数据结构: 一 栈和队列
水平有限，文中有什么不对或者有什么建议希望大家能够指出，谢谢！
