是一种数据结构，能够实现后进先出的一种业务场景。即栈中的元素被处理时，按后进先出的顺序进行。所以栈又叫做后进先出表（LIFO）;
例子：生活中的叠放在厨房桌子上的碗就是一种栈结构。放的时候只能把碗放在最上面，取的时候只能从最上面开始取。
例图：
栈结构的应用有 表达式求值，函数调用及递归实现，深度优先算法，回溯算法等等….
类型名称：堆栈（Stack）
数据对象集：一个有0个或多个元素组成的有穷线性表。
操作集：长度为MaxSize的堆栈S∈Stack, 堆栈元素Item∈ElementType
1.Stack CreakStack(int MaxSize); 生成空堆栈，其最大长度为MaxSize;
2.int IsFull(Stack S,Int MaxSize)； 判断堆栈是否已满。
3.void Push(Stack S,ElementType item); 将元素压入堆栈
4.int isEmpty(Stack S); 判断堆栈是否为空
5.ElementType pop(Stack s); 删除并返回栈顶元素
栈的顺序存储实现：
package com.simon.datastructure.javadatastructure;
/**
* auther: Simon zhang
* Emaill:18292967668@163.com
*
* 基于数组的Stack的实现
*/
public class ArrayStack<E>{
/**
* 用于存储栈元素的数组
*/
Object[] elements;
/**
* 用于表示栈顶元素的下表
*/
int top;
/**
* 用于表示栈的容量
*/
int maxSize;
/**
* 生成空堆栈，其最大长度为MaxSize
* @param maxSize
*/
public ArrayStack(int maxSize) {
if(maxSize<0){
throw new IllegalArgumentException("stack size must more than zero..");
}
this.maxSize = maxSize;
this.top=-1;
this.elements=new Object[maxSize];
}
/**
* 判断堆栈是否已满
*/
public boolean isFull() {
return top==(maxSize-1);
}
/**
* 将元素压入堆栈
* @param e
*/
public void push(E e){
if(isFull()){
System.out.println("stack is full now..");
}else{
elements[++top]=e;
}
}
/**
* 删除并返回栈顶元素
*/
@SuppressWarnings("unchecked")
public E pop(){
if(isEmpty()){
System.out.println("stack is empty now..");
return null;
}else{
//这个unchecked cast异常怎么解决？
E popE=(E) elements[top];
elements[top]=null;
top--;
return popE;
}
}
/**
* 将元素压入堆栈
*/
public boolean isEmpty(){
return top==-1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 0; i <top+1; i++) {
sb.append(elements[i].toString());
if(i!=top){
sb.append(',');
}
}
sb.append(']').toString();
return sb.toString();
}
}
栈的链式存储实现：
package com.simon.datastructure.javadatastructure;
/**
* auther: Simon zhang
* Emaill:18292967668@163.com
*
* 栈结构的链式存储方式实现
*/
public class LinkedStack<E>{
/**
* 头节点
*/
Node<E> header;
/**
* 栈的容量
*/
int maxSize;
/**
* 当前节点数量
*/
private int size;
public LinkedStack(int maxSize) {
this.maxSize = maxSize;
}
/**
* 判断堆栈是否已满
*/
public boolean isFull() {
return size==maxSize;
}
/**
* 将元素压入堆栈
* @param e
*/
public void push(E e){
if(isFull()){
System.out.println("stack is full now..");
}else{
Node<E> insertNode = new Node(e);
insertNode.first=header;
header=insertNode;
size++;
}
}
/**
* 删除并返回栈顶元素
*/
@SuppressWarnings("unchecked")
public E pop(){
if(isEmpty()){
System.out.println("stack is empty now..");
return null;
}else{
E item= header.item;
header=header.first;
size--;
return item;
}
}
/**
* 将元素压入堆栈
*/
public boolean isEmpty(){
return size==0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
Node temp=header;
while (temp.first!=null){
sb.append(temp.item.toString());
sb.append(',');
temp=temp.first;
}
sb.append(temp.item.toString());
sb.append(']').toString();
return sb.toString();
}
class Node<E>{
E item;
Node first;
public Node(E item) {
this.item = item;
}
public void addFirst(Node next) {
this.first = next;
}
}
}
堆栈知识总结：
栈结构实现的方式相对比较简单，但是这种数据结构在软件开发过程中有很多的应用场景，值得我们认真学习掌握。
参考：
1.中国大学数据结构课程（浙江大学）
2. http://blog.csdn.net/chenleixing/article/details/42392283