数据结构复习之【栈】
栈：先进后出的线性表；
栈也可以通过顺序存储和链式存储的方式实现；
一、顺序存储实现
数组的尾端作为栈顶；
代码实现：
package org.xiazdong.list;
public class MyArrayStack<T> {
private static final int DEFAULT_LENGTH = 10;
private T[]t;
private int length;
private int top;
public MyArrayStack(){
t = (T[])new Object[DEFAULT_LENGTH];
length = 0;
top = -1;
}
public void push(T e){
if((top+1)>=t.length){
larger(t.length*2);
}
top++;
if(top>=t.length){
}
t[top]=e;
}
public T top(){
return t[top];
}
public T pop(){
if(top<0){
throw new ArrayIndexOutOfBoundsException();
}
T tmp = t[top];
top--;
return tmp;
}
public int getSize(){
return top+1;
}
private void larger(int len){
T[]tmp = (T[])new Object[len];
for(int i=0;i<t.length;i++){
tmp[i] = t[i];
}
t = tmp;
}
}
二、链式存储实现
链表的头端作为栈顶；
代码实现如下：
package org.xiazdong.list;
import org.xiazdong.list.MyLinkedList.Node;
public class MyLinkedStack <T>{
private Node top;
private int count;
public MyLinkedStack(){
count = 0;
top = null;
}
public T pop(){
if(top==null){
throw new ArrayIndexOutOfBoundsException();
}
T elem = top.elem;
top = top.next;
return elem;
}
public T top(){
return top.elem;
}
public void push(T e){
Node n = new Node();
n.elem = e;
n.next = top;
top = n;
}
class Node{
private T elem;
Node next;
public Node(){
elem = null;
next = null;
}
public Node(T elem,Node next){
this.elem = elem;
this.next = next;
}
}
}
三、比较
| 顺序存储 | 链式存储 | |
| 优点 | 访问快、增加删除都为O(1) | 增加删除都为O(1)，对于空间没有限制 |
| 缺点 | 浪费空间，容易溢出 | 指针需要空间 |
四、栈的应用
1.递归
我们这里以斐波那契数为例；fib(n) = fib(n-1)+fib(n-2),fib(2) = fib(1) = 1;
递归和栈是密不可分的，递归的实现就是通过栈来完成的；
2.后缀表达式
我们在做计算器应用时肯定会用到后缀表达式，中缀表达式转换到后缀表达式，后缀表达式求出值都是通过栈实现的；
后缀表达式的讲解在：http://blog.****.net/xiazdong/article/details/7272693