Java数据结构之栈

布满荆棘的人生 2022-02-15 05:21 332阅读 0赞

# 栈的基本概念 #

栈是一种特殊的线性表，其插入、删除操作只能在表的尾部进行。其允许插入、删除操作的一端成为栈顶，另一端称为栈尾，插入操作叫入栈，删除操作叫出栈，具有先进后出的特点（FILO）。

# 栈的抽象数据类型描述 #

栈中的数据元素和数据间的逻辑关系与线性表相同，是由n个具有相同数据类型的数据元素构成的有限序列。

package ch03;
    
    public interface IStack {
    	public void clear();
    	public boolean isEmpty();
    	public int length();
    	public Object peek();
    	public void push(Object x) throws Exception;
    	public Object pop();
    	public void display();
    }

## 顺序栈 ##

底层数据结构为数组，用变量top来指向栈顶元素的存储位置，空栈是top=0；

package ch03;
    
    public class SqStack implements IStack{
    	private Object[] stackItem;
    	private int top;
    	private int maxSize;
    	
    	public SqStack(int maxSize) {
    		top = 0;
    		this.maxSize = maxSize;
    		stackItem = new Object[maxSize];
    	}
    	
    	//清空顺序栈
    	public void clear() {
    		top = 0;
    	}
    
    	//判断顺序栈是否为空
    	public boolean isEmpty() {
    		return top == 0;
    	}
    
    	//返回顺序栈长度
    	public int length() {
    		return top;
    	}
    
    	//返回栈顶元素
    	public Object peek() {
    		if(top==0)
    			return null;
    		else
    			return stackItem[top-1];
    	}
    
    	//入栈
    	public void push(Object x) throws Exception{
    		if(top==maxSize-1)
    			throw new Exception("栈内空间已满，无法添加元素！");
    		stackItem[top] = x;
    		top++;
    	}
    
    	//出栈
    	public Object pop() {
    		if(top==0)
    			return null;
    		top--;
    		return stackItem[top];
    	}
    }

## 链栈 ##

采用链式存储结构的栈为链栈，由于栈的插入和删除只能在栈顶进行，所以不需要设置头指针，只需要将top指向栈顶元素结点，每个结点的指针域指向其后继结点即可。

package ch03;
    
    import ch02.Node;
    
    public class LinkStack implements IStack {
    	private Node top;//指向头结点
    	public Node next;
    
    	public LinkStack() {
    		top = null;
    	}
    
    	@Override
    	public void clear() {
    		// TODO Auto-generated method stub
    		top = null;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		// TODO Auto-generated method stub
    		return top == null;
    	}
    
    	@Override
    	public int length() {
    		// TODO Auto-generated method stub
    		int length = 0;
    		if (top != null) {
    			while (top.next != null) {
    				top = top.next;
    				length++;
    			}
    		}
    		return length;
    	}
    
    	@Override
    	public Object peek() {
    		// TODO Auto-generated method stub
    		if (!isEmpty())
    			return top.data;
    		return null;
    	}
    
    	@Override
    	public void push(Object x) throws Exception {
    		// TODO Auto-generated method stub
    		Node newNode = new Node(x);
    		newNode.next = top;
    		top = newNode;
    	}
    
    	@Override
    	public Object pop() {
    		// TODO Auto-generated method stub
    		if(isEmpty()) {
    			return null;
    		}
    		Node p = top;
    		top = top.next;
    		return p.data;
    	}
    }

# 顺序栈测试 #

通过顺序栈检查输入的字符串中的括号是否匹配

package ch03;
    
    import java.util.Scanner;
    
    public class isMatched {
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		String str = sc.nextLine();
    		matched(str);
    	}
    	
    	public static void matched(String str) {
    		SqStack sqs = new SqStack(str.length());
    		for(int i=0;i<str.length();i++) {
    			if(str.charAt(i)=='(')
    				try {
    					sqs.push('(');
    				} catch (Exception e) {
    					e.printStackTrace();
    				}
    			else if(str.charAt(i)==')'&&!sqs.isEmpty())
    				sqs.pop();
    			else if(str.charAt(i)==')'&&sqs.isEmpty()) {
    				System.out.println("括号不匹配！");
    				return;
    			}
    		}
    		if(sqs.isEmpty())
    			System.out.println("括号匹配！");
    		else
    			System.out.println("括号不匹配！");
    	}
    }