数据结构—栈
先说什么是栈：
创新互联专注于泾川网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供泾川营销型网站建设，泾川网站制作、泾川网页设计、泾川网站官网定制、微信小程序服务，打造泾川网络公司原创品牌,更为您提供泾川网站排名全网营销落地服务。
1、后进先出 2、对数据的所有操作只能在固定的一端进行操作，不能再中间或者另一端对数据进行操作。
符合以上两点的 存储数据的类（对象） 叫做栈。
需要说明的是：栈是符合以上两个特性的所有的数据结构都可以叫做栈，无论其用什么基本容器实现的。
再说如何实现:
可以使用数组或者链表实现栈，在用链表实现的时候要屏蔽掉链表的一些特性：在链表中间对数据进行操作等。
看一下jdk中自带的栈：
注意Stack(图一)中： Stack继承自Vactor Stack自己的方法种类
Vector(图二)中 ： Vector中的方法
Stack继承自Vactor，所以Stack是可以调用父类中的set(int index, E element),insertElementAt(E obj, int index)等操作的，这样的话就与栈的特性有矛盾，我对这一点还没有理解透彻，是不是第二条特性需要去掉？希望有朋友看到之后能够指教指教。感谢！
图一：Stack.java
图二：Vector.java
既然是jdk自带的有栈，我们还了解他干什么？
在一些特殊情况下，需要根据实际情况封装自己的栈。
下面给两个自己做的示例，一个使用数组实现的栈，一个是用链表实现的栈。
数组实现：
package com.datastructure;/**
* @author Perkins .Zhu
* @date:2016年7月17日 上午9:13:01
* @version :1.1
*
*/public class ArrayStack implements Stack { private int maxSize; private Object[] myStack; private int top = -1;// 指向最后入栈的对象
private final int DEFAULT_SIZE = 100; private boolean canExpendSize = true;// 是否允许扩容
private int multiple = 2;// 扩容倍数
public ArrayStack() {
myStack = new Object[DEFAULT_SIZE];
} public ArrayStack(int size, boolean canExpendSize) { if (size < 1) {
size = DEFAULT_SIZE;
}
myStack = new Object[size]; this.canExpendSize = canExpendSize;
}
@Override public void push(Object obj) { if (top == myStack.length - 1) { if (canExpendSize) {
exspandSize();
} else {
move();
}
}
myStack[++top] = obj;
} // 删除栈底元素，所有元素向后移动一位，top指向 myStack.length-2
private void move() { for (int i = 0; i < myStack.length - 1; i++) {
myStack[i] = myStack[i + 1];
}
top = myStack.length - 2;
} // 扩容
private void exspandSize() {
Object[] temp = new Object[multiple * myStack.length]; for (int i = 0; i < myStack.length; i++) {
temp[i] = myStack[i];
}
top = myStack.length - 1;
myStack = temp;
}
@Override public Object pop() { if (top == -1) return null; return myStack[top--];
}
@Override public boolean isEmpty() { return top == -1;
}
}
链表实现：(只实现了基本功能，可根据实际需要添加参数或者方法)
package com.datastructure;import java.util.LinkedList;/**
* @author Perkins .Zhu
* @date:2016年7月17日 下午1:16:26
* @version :1.1
*
*/public class LinkStack implements Stack { private Node top; private class Node { private Object obj; private Node nextNode; public Node(Object obj, Node node) { this.obj = obj; this.nextNode = node;
}
} public void push(Object obj) { if (top != null) {
top = new Node(obj, top);
} else {
top = new Node(obj, null);
}
} public Object pop() {
Node res = top;top = top.nextNode;
= top ==
再给个测试类:
package com.datastructure;import org.junit.Test;/**
* @author Perkins .Zhu
* @date:2016年7月17日 上午9:16:50
* @version :1.1
*
*/public class StackTest {
@Test public void testArrayStack() {
ArrayStack stack = new ArrayStack(100, false); int loop = 0; while (loop < 150) {
stack.push(loop++);
}
print(stack);
} public void print(Object obj) { if (obj instanceof Stack) {
Stack stack = (Stack) obj; while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
System.out.println();
}
@Test public void testLinkStack() {
LinkStack stack = new LinkStack(); int loop = 0; while (loop < 150) {
stack.push(loop++);
}
print(stack);
}
}
遇到的几个问题：
1、有没有栈的官方标准定义？
只要符合后进先出(last in first off，LIFO)的数据结构都是栈。
2、泛型 T和object有什么区别，接收参数的时候有什么不同的？？
a:约束了此容器中只能存储一种类型数据。
b:在从容器中取出对象的时候不需要进行类型强转，容器已经知道（因为在new 容器的时候在<>中已经制定了存储对象类型）你存储的是什么类型，但是object需要进行强转。
3、栈要不要实现其删除、插入、查找操作？
栈不需要这些方法，这些方法的存在没意义。画蛇添足。
4、除了使用数组和链表还有没有其他栈实现方式？
应该没有了吧？
网站标题：数据结构—栈
文章位置：http://cdiso.cn/article/jdphpo.html
