栈及其实现
栈的描述
栈是一中特殊的线性表,栈中的数据元素与数据元素之间的逻辑关系与线性表相同,他们的差别在于:线性表的插入和删除可以在表中任意位置,而栈的插入和删除只允许在表的尾端操作,允许插入和删除的一端叫做栈顶(top),另一端称为栈底(bottom),插入的操作称为入栈(push),删除的操作称为出栈(pop)。
栈的接口实现
public interface IStack {
void clean(); //将已经存在的栈置成空栈
boolean isEmpty(); //判断一个栈是否为空,空返回true,否则返回false
int length(); //返回栈中数据元素的个数
Object peek(); //取出栈顶元素并返回其值
void push(Object x); //将x元素压入栈顶
Object pop(); //删除并返回删除的栈顶元素
}
顺序栈以及基本操作的实现
与顺序表一样,顺序栈也是用链表来实现,假设数组名为stackElem。
由于入栈和出栈都是在栈顶操作,所以需要一个指针top时刻指向栈顶。
如下图:
public class SqStack implements IStack{
//创建数组
private Object[] stackElem;
private int top; //当栈不为空时,top指向栈顶元素的下一个存储位置
public SqStack(int maxSize){
top = 0;
stackElem = new Object[maxSize];
}
@Override
public void clean() {
top = 0;
}
@Override
public boolean isEmpty() {
return top == 0;
}
@Override
public int length() {
return top;
}
@Override
public Object peek() {
return stackElem[top-1];
}
@Override
public void push(Object x)throws Exception {
//判断栈是否满
if(top==stackElem.length)
throw new Exception("栈已满");
else
stackElem[top++] = x;
}
@Override
public Object pop()throws Exception {
//判断栈是否为空
if(isEmpty())
throw new Exception("栈为空");
else
return stackElem[--top];
}
}
链栈以及基本操作的实现
由于栈链表只能在栈顶进行,所以栈链表不需要设置头结点head。
//结点类
public class Node2 {
public Object data;
public Node2 next;
public Node2(){
this(null,null);
}
public Node2(Object data){
this(data,null);
}
public Node2(Object data, Node2 next){
this.data = data;
this.next = next;
}
}
public class LinkStack implements IStack{
public Node2 top; //栈顶元素的引用
@Override
public void clean() {
top = null;
}
@Override
public boolean isEmpty() {
return top == null;
}
@Override
public int length() {
Node2 p = top;
int length = 0;
while(p!=null){
p = p.next;
length++;
}
return length;
}
//取出栈顶元素并返回其值
@Override
public Object peek()throws Exception{
//判断栈是否为空
if(top == null)
throw new Exception("栈为空");
return top.next.data;
}
@Override
public void push(Object x) throws Exception {
Node2 p = new Node2(x);
p.next = top;
top = p;
}
@Override
public Object pop() throws Exception {
//判断是否为空栈
if(isEmpty())
throw new Exception("栈为空");
Node2 p = top;
top = p.next;
return p.data;
}
}
栈的应用
分配符匹配问题:
Java程序中有以下分隔符,圆括号" ( “和” ) “,方括号” [ “和” ] “,大括号” { “和” } “以及注释分隔符” /* “和” */ "。以下是一些正确使用分隔符的例子:
a = b + ( c + d ) * ( e - f );
s[4] = t[a[2]] + u / (( i + j ) * k);
以下是分配符不匹配的句子:
a = ( b + c / ( d * e ) * f; //左括号多余
分析:
public class Example {
private final int LEFT = 0; //记录分隔符为"左"分隔符
private final int RIGHT = 1; //记录分隔符为"右"分隔符
private final int OTHER = 2; //记录其他字符
//判断分隔符类型
public int verifyFlag(String str){
if("(".equals(str)||"[".equals(str)||"{".equals(str)||"/*".equals(str)){
return LEFT;
}
else if(")".equals(str)||"]".equals(str)||"}".equals(str)||"*/".equals(str)){
return RIGHT;
}
else
return OTHER;
}
//检验左右分隔符是否匹配
public boolean matches(String str1,String str2){
if("(".equals(str1)&&")".equals(str2)||
"[".equals(str1)&&"]".equals(str2)||
"{".equals(str1)&&"}".equals(str2)||
"/*".equals(str1)&&"*/".equals(str2))
return true;
else {
return false;
}
}
public boolean isLegal(String str)throws Exception{
//建立顺序栈
if(!"".equals(str)&&str!=null){
SqStack S = new SqStack(100);
//将str拆分
int length = str.length();
for(int i=0;i<length;i++){
char c = str.charAt(i); //指向索引处的char值
String t = String.valueOf(c);
if(i!=length){
if(('/' == c&&'*' == str.charAt(i+1))||('*' == c&&'/' == str.charAt(i+1))){
t = t.concat(String.valueOf(str.charAt(i+1))); //与后一个字符相连形成 /* 或 */
i++; //跳过一个字符
}
}
if(LEFT == verifyFlag(t)){
//左分配符,压入栈中
S.push(t);
}else if(RIGHT == verifyFlag(t)){
//右分配符,取出顶栈元素
if(S.isEmpty()||!matches(S.pop().toString(),t)){
throw new Exception("错误:Java语句不合法");
}
}
}
if(!S.isEmpty()) //栈中不为空
throw new Exception("错误:Java语句不合法");
return true;
}
else
throw new Exception("错误:Java语句为空");
}
public static void main(String[] args)throws Exception {
Example e = new Example();
System.out.println("请输入Java语句:");
Scanner sc = new Scanner(System.in);
if(e.isLegal(sc.nextLine()))
System.out.println("Java语法正确");
else
System.out.println("错误!Java语法不正确");
}
}