数据结构之栈

男娘i 2022-08-11 03:27 177阅读 0赞

栈是一种先进后出的线性结构，只允许在一端插入删除，属于逻辑结构。

栈的定义

package com.zhiru;
    
    /*
     * 栈是一种先进后出的数据结构.
     */
    public class MyStack<E> {
    	//栈顶指针
    	private int top=-1;
    	private E[] s;
    	//栈的最大容量.
    	private int maxSize=100;
    	MyStack(E[] e){
    		s=e;
    	}
    	//压栈
    	public void push(E c){
    		s[++top]=c;
    	}
    	//弹栈
    	public E pop(){
    		return s[top--];
    	}
    	//获取栈顶元素
    	public E getTop(){
    		return s[top];
    	}
    	public boolean isEmpty(){
    		return top==-1;
    	}
    	public int getSize(){
    		return top+1;
    	}
    	public void printStack(){
    		if(!isEmpty()){
    			int i=top;
    			while(i>=0){
    				System.out.print(s[i]+" ");
    				i--;
    			}
    			System.out.print("\n");
    		}
    	}
    }

测试

package com.zhiru;
    
    public class TestStack {
    	
    //	public static int  Location(char[]x,char v){
    //		int p=0;
    //		while(p<x.length){
    //			if(v==x[p])
    //				break;
    //			else
    //				p++;
    //		}
    //		return p+1;
    //	}
    	//括号匹配。
    	public static void kuoHao(String s){
    		int len=s.length();//获取字符串长度.
    		char[]x=new char[len];
    		Integer[]s_len=new Integer[len];
    		MyStack<Integer> ms=new MyStack<Integer>(s_len);
    		for(int i=0;i<len;i++){
    			x[i]=s.charAt(i);
    		}
    		//扫描字符串数组
    		for(int j=0;j<len;j++){
    			int pos;
    			if(x[j]=='(') 
    				ms.push(j);//左括号，位置进栈
    			else if(x[j]==')'){//右括号，弹栈。
    				pos=ms.pop();
    				if(pos>=0)
    					System.out.println("第"+(pos+1)+"个左括号与第"+(j+1)+"个右括号匹配！");
    				else 
    					System.out.println("没有与第"+(j+1)+"个右括号匹配的左括号");
    			}	
    		}
    		//栈中还有左括号
    		while(ms.isEmpty()==false){
    			System.out.println("没有与第"+(ms.pop()+1)+"个左括号匹配的右括号");
    		}
    		
    	}
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Character[]a={'1','2','3','4','5'};
    		Integer[] x={2,3,4,5,6,7,8};
    		MyStack<Character> ms=new MyStack<Character>(a);
    		MyStack<Integer> ms1=new MyStack<Integer>(x);
    		for(int i=0;i<a.length;i++){
    			ms.push(a[i]);
    		}
    		for(int m=0;m<x.length;m++){
    			ms1.push(x[m]);
    		}
    		System.out.print("栈顶元素是"+ms.getTop()+"\n");
    		ms.printStack();
    		System.out.print("栈顶元素是"+ms1.getTop()+"\n");
    		ms1.printStack();
    		String s="((()))";
    		String s2="((())";
    //		String s3="(()))";
    		kuoHao(s);
    		kuoHao(s2);
    //		kuoHao(s3);
    	}
    
    }

栈顶元素是5  
5 4 3 2 1   
栈顶元素是8  
8 7 6 5 4 3 2   
第3个左括号与第4个右括号匹配！  
第2个左括号与第5个右括号匹配！  
第1个左括号与第6个右括号匹配！  
第3个左括号与第4个右括号匹配！  
第2个左括号与第5个右括号匹配！  
没有与第1个左括号匹配的右括号