Java数据结构和算法-栈
1.概念
栈是一种用于存储数据的简单数据结构，有点类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈。
栈(Stack)是一种有序特殊的线性表，只能在表的一端(称为栈顶，top，总是指向栈顶元素)执行插入和删除操作，最后插入的元素将第一个被删除，因此栈也称为后进先出（FILO)的线性表。栈的基本操作创建栈，判空，入栈，出栈，获取栈顶元素等，注意栈不支持对指定位置进行删除，插入。
public interface Stack<T> {
//栈是否为空
boolean isEmpty();
//data元素入栈
void push(T data);
//返回栈顶元素,未出栈
T peek();
//出栈,返回栈顶元素,同时从栈中移除该元素
T pop();
}
2.顺序栈的设计与实现
public class SeqStack<T> implements Stack<T>,Serializable {
private static final long serialVersionUID = -5413303117698554397L;
//栈顶指针,-1代表空栈
private int top=-1;
//容量大小默认为10
private int capacity=10;
//存放元素的数组
private T[] array;
private int size;
public SeqStack(int capacity){
array = (T[]) new Object[capacity];
}
public SeqStack(){
array= (T[]) new Object[this.capacity];
}
}
//取栈顶元素，不删除
public T peek() {
if(isEmpty()){
new EmptyStackException();
}
return array[top];
}
//入栈，容量不足则扩容
public void push(T data) {
//判断容量是否充足
if(array.length==size)
ensureCapacity(size*2+1);//扩容
//从栈顶添加元素
array[++top]=data;
}
//出栈并删除
public T pop() {
if(isEmpty())
new EmptyStackException();
size--;
return array[top--];
}public class LinkedStack<T> implements Stack<T> ,Serializable{
private static final long serialVersionUID = 1911829302658328353L;
private Node<T> top;
private int size;
public LinkedStack(){
this.top=new Node<>();
}
public int size(){
return size;
}
@Override
public boolean isEmpty() {
return top==null || top.data==null;
}
@Override
public void push(T data) {
if (data==null){
throw new StackException("data can\'t be null");
}
if(this.top==null){//调用pop()后top可能为null
this.top=new Node<>(data);
}else if(this.top.data==null){
this.top.data=data;
}else {
Node<T> p=new Node<>(data,this.top);
top=p;//更新栈顶
}
size++;
}
@Override
public T peek() {
if(isEmpty()){
throw new EmptyStackException("Stack empty");
}
return top.data;
}
@Override
public T pop() {
if(isEmpty()){
throw new EmptyStackException("Stack empty");
}
T data=top.data;
top=top.next;
size--;
return data;
}
//测试
public static void main(String[] args){
LinkedStack<String> sl=new LinkedStack<>();
sl.push("A");
sl.push("B");
sl.push("C");
int length=sl.size();
for (int i = 0; i < length; i++) {
System.out.println("sl.pop->"+sl.pop());
}
}
}
3.链式栈的设计与实现
public class LinkedStack<T> implements Stack<T> ,Serializable{
private static final long serialVersionUID = 1911829302658328353L;
private Node<T> top;
private int size;
public LinkedStack(){
this.top=new Node<>();
}
public int size(){
return size;
}
@Override
public boolean isEmpty() {
return top==null || top.data==null;
}
@Override
public void push(T data) {
if (data==null){
throw new StackException("data can\'t be null");
}
if(this.top==null){//调用pop()后top可能为null
this.top=new Node<>(data);
}else if(this.top.data==null){
this.top.data=data;
}else {
Node<T> p=new Node<>(data,this.top);
top=p;//更新栈顶
}
size++;
}
@Override
public T peek() {
if(isEmpty()){
throw new EmptyStackException("Stack empty");
}
return top.data;
}
@Override
public T pop() {
if(isEmpty()){
throw new EmptyStackException("Stack empty");
}
T data=top.data;
top=top.next;
size--;
return data;
}
//测试
public static void main(String[] args){
LinkedStack<String> sl=new LinkedStack<>();
sl.push("A");
sl.push("B");
sl.push("C");
int length=sl.size();
for (int i = 0; i < length; i++) {
System.out.println("sl.pop->"+sl.pop());
}
}
}
4.栈的应用
栈是一种很重要的数据结构，在计算机中有着很广泛的应用，如下一些操作都应用到了栈。
1.符号匹配
2.中缀表达式转换为后缀表达式
3.计算后缀表达式
4.实现函数的嵌套调用
5.HTML和XML文件中的标签匹配
6.网页浏览器中已访问页面的历史记录
接下来我们分别对符合匹配，中缀表达式转换为后缀表达式进行简单的分析，以加深我们对栈的理解。
符号匹配
在编写程序的过程中，我们经常会遇到诸如圆括号“()”与花括号“{}”，这些符号都必须是左右匹配的，这就是我们所说的符合匹配类型，当然符合不仅需要个数相等，而且需要先左后右的依次出现，否则就不符合匹配规则，如“)(”，明显是错误的匹配，而“()”才是正确的匹配。有时候符合如括号还会嵌套出现，如“9-(5+(5+1))”,而嵌套的匹配原则是一个右括号与其前面最近的一个括号匹配，事实上编译器帮我检查语法错误是也是执行一样的匹配原理，而这一系列操作都需要借助栈来完成，接下来我们使用栈来实现括号”()”是否匹配的检测。
判断原则如下（str=”((5-3)*8-2)”）：
a.设置str是一个表达式字符串，从左到右依次对字符串str中的每个字符char进行语法检测，如果char是，左括号则入栈，如果char是右括号则出栈(有一对
匹配就可以去匹配一个左括号，因此可以出栈)，若此时出栈的字符char为左括号，则说明这一对括号匹配正常，如果此时栈为空或者出栈字符不为左括号，
则表示缺少与char匹配的左括号，即目前不完整。
b.重复执行a操作，直到str检测结束，如果此时栈为空，则全部括号匹配，如果栈中还有左括号，是说明缺少右括号。
栈原文：https://blog.csdn.net/javazejian/article/details/53362993
上一篇： 1261: 孪生素数
下一篇： 1250: 跑跑数