使用java设计实现顺序栈的基本结构，输入一个字符串来判断()以及[]是否匹配
基本栈结构介绍
顺序栈是一种FILO的结构，根据顺序栈的特性可以通过数组来实现顺序栈的相关操作。
使用一个头指针来作为数组存储元素的标识，当存入元素时头指针++既实现压栈操作。
当取出一个元素时，直接返回当前头指针所对应的元素，并将头指针指为空，指针–既实现出栈操作。
获取栈顶元素时直接返回当前指针所指向的元素。
当然，在压栈时得判断栈是否满，否则会出现上溢的情况；与此同时出栈以及获取栈顶元素时得判断栈是否为空，否则会出现下溢的情况。
实现思路
利用一个泛型数组来存储指定泛型类型的数据，并且使用一个头指针来对所存元素的位置进行指向，读取元素时想应的头指针都应变化。
代码实现
首先先来编写一个栈的接口，声明对于的操作函数：
interface IStack<T>{
// 出栈
public T pop();
// 入栈
public void push(T element)throws Exception;
// 获取栈顶元素
public T top()throws Exception;
// 栈判空
public boolean isEmpty();
// 栈判溢
public boolean isFull();
// 获取当前栈中所存元素的长度
public int getLength();
// 清空栈
public void setEmpty();
}定义顺序栈类实现定义的栈接口：
class ArrayStack<T> implements IStack{
// 栈默认大小
private final int DEFAULT_SIZE = 3;
// 栈最大值
private int max_size;
// 栈数组
private T[] arrayObj;
// 栈顶指针，初试默认指向-1
private int top = -1;
/** * 默认构造函数 */
public ArrayStack(){
this.max_size = DEFAULT_SIZE;
this.arrayObj = (T[])new Object[this.max_size];
top = -1;
}
/** * 带初始值的构造函数 * @param size */
public ArrayStack(int size) {
this.max_size = size;
this.arrayObj = (T[])new Object[this.max_size];
top = -1;
}
/** * 出栈 * 首先判断栈是否为空，不为空则将top指针下的元素返回，并且将该位置清空，top指针-- */
@Override
public Object pop() {
// TODO Auto-generated method stub
if(isEmpty()) {
System.out.println("栈为空！");
return null;
}
T result = (T)arrayObj[top];
arrayObj[top] = null;
top--;
return result;
}
/** * 入栈，首先判断入栈的元素是否为空，不为空则入栈成功 * 在判断栈是否满，栈满则无法入栈（也可实现为栈满则扩展栈空间），栈不满的情况下将元素存入数组，top++ */
@Override
public void push(Object element) throws Exception{
// TODO Auto-generated method stub
if(null == element) {
throw new Exception("入栈的元素不能为空");
}
if(isFull()) {
System.out.println("栈满了！");
}else {
this.arrayObj[++top] = (T)element;
}
}
/** * 获取栈顶元素，首先判断栈是否为空，栈为空的话则抛出异常 * 栈不为空的话则返回当前top指针下的内容 */
@Override
public Object top() throws Exception{
// TODO Auto-generated method stub
if(isEmpty()) {
System.out.println("栈为空！");
return null;
}else {
return this.arrayObj[top];
}
}
/** * 栈判空 */
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
if(top == -1) {
return true;
}
return false;
}
/** * 栈判溢 */
@Override
public boolean isFull() {
// TODO Auto-generated method stub
if(top == arrayObj.length-1) {
return true;
}
return false;
}
/** * 获取当前栈中所存元素的长度 */
@Override
public int getLength() {
// TODO Auto-generated method stub
return this.top;
}
/** * 清空栈 */
@Override
public void setEmpty() {
// 将数组置空
Arrays.fill(arrayObj, null);
// 指针归位
this.top = -1;
this.max_size = this.DEFAULT_SIZE;
this.arrayObj = (T[])new Object[max_size];
}
}此时，栈结构已经定义好了，接下来利用自定义的栈结构来实现括号的匹配判断
括号匹配思路
对输入的字符串的单个字符进行判断：
如果栈为空则入栈，
如果栈不为空则判断栈顶元素是否与当前元素匹配，
匹配则栈顶元素出栈，不匹配则入栈
最后栈为空则小括号匹配，栈不为空则不匹配
代码
public class Question8 {
public static void main(String[] args) throws Exception {
ArrayStack<Character> stack =null;
// 使用Scanner获取用户输入
Scanner scanner = new Scanner(System.in);
// 获取用户输入的内容
String str = scanner.next();
// 关闭输入流
scanner.close();
if(null == str||str.equals("")) {
System.out.println("输入错误!!!");
}else {
// 如果输入的是奇数则证明不匹配
if(str.length()%2 == 1) {
System.out.println("不匹配");
}else {
// 创建自定义的栈对象
stack = new ArrayStack<Character>(100);
// 对字符串中的单个字符进行判断
for(int i=0;i<str.length();i++) {
// 当栈为空时，将当前字符压入栈中
if(stack.isEmpty()) {
stack.push(str.charAt(i));
}else {
// 栈不空时，获取栈顶元素并与当前字符进行匹配，匹配成功则当前执行出栈，匹配不成功则入栈
if((char)(stack.top())=='('&&str.charAt(i)==')'||(char)(stack.top())=='['&&str.charAt(i)==']') {
stack.pop();
}else {
stack.push(str.charAt(i));
}
}
}
}
}
if(stack.isEmpty()) {
System.out.println("匹配成功");
}else {
System.out.println("匹配失败");
}
}
}