数据结构之栈

╰半夏微凉° 2022-08-06 01:05 196阅读 0赞

1、定义：栈(stack)是限制在插入和删除只能在一个位置进行操作的一种表结构，该合位置是表的末端，称作栈顶(top)，对栈的基本操作的push()进栈和pop()出栈，一般栈都具有先进后出的特征。栈也不可能被放满。栈的结构图如下：

![Center][]

2、栈的实现方法：

a、栈的链表实现：通过在顶端插入元素实现push(),通过删除顶端元素来实现pop(),top操作表示返回到栈顶，

/*使用链结构来实现栈*/
    public class MyStack_linked {
    	private Node topOfStack;//最顶上元素
    	public MyStack_linked() {//初始化Stack
    		topOfStack=null;
    	}
    	
    	public boolean isFull(){//栈不可能满
    		return false;
    	}
    	public boolean isEmpty(){//判断是否为空
    		return topOfStack==null;
    	}
    	public void makeEmpty(){//将topOfStack为空
    		topOfStack=null;
    	}
    	public void push(Object x){//加入一个元素
    		topOfStack=new Node(x,topOfStack);
    	}
    	public Object top(){//找到最顶上的元素
    		if(isEmpty()){
    			return null;
    		}else{
    			return topOfStack.element;
    		}
    	}
    	public void pop(){//删除一个元素
    		if(!isEmpty()){
    		   topOfStack=topOfStack.next;
    		}
    	}
    	//出栈
    	public Object topAndPop(){//
    		if(isEmpty()){
    			return null;
    		}else{
    			Object topItem=topOfStack.element;
    			topOfStack=topOfStack.next;
    			return topItem;
    		}
    	}
    	//测试
    	public static void main(String[] args) {
    		MyStack_linked stack=new MyStack_linked();
    		stack.push(1);
    		stack.push(2);
    		stack.push(3);
    		stack.push(4);
    		while(!stack.isEmpty()){
    			System.out.println(stack.topAndPop());
    		}
    	}
    }

b、栈的数组实现：每个栈都有一个theArray数组和topOfStack，对于空栈它是-1（这是空栈的初始化）。为了将某一个值x压入到栈中，将topOfStack加1，然后置theArray\[topOfStack\]=x;为了将元素弹出栈，置返回值为theArray\[topOfStack\],然后将topOfStack减1;下面是java实现

/*数组实现 Stack*/
    public class MyStack_Array {
    
    	private Object [] theArray;
    	private int topOfStack;
    	static final int DEFAULT_CAPACITY=10;
    	//初始化一个栈,定义大小
    	public MyStack_Array(){
    		this(DEFAULT_CAPACITY);
    	}
    	//初始化一个栈
    	public MyStack_Array(int capacity){
    		this.theArray=new Object[capacity];
    		this.topOfStack=-1;
    	}
    	//判断是否为空
    	public boolean isEmpty(){
    		return topOfStack==-1;
    	}
    	//判断是否已经满了
    	public boolean isFull(){
    		return topOfStack==theArray.length-1;
    	}
    	//把栈置空
    	public void makeEmpty(){
    		topOfStack=-1;
    	}
    	//入栈
    	public void push(Object x){
    		//在入栈之前需要判断栈是否已经满了
    		if(isFull()){
    			try {
    				throw new Exception("The stack is Full");
    			} catch (Exception e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}else{
    			/*theArray[++topOfStack]=x;相当于
    			 * topOfStack++;
    			 * theArray[topOfStack]=x;
    			 * */
    			theArray[++topOfStack]=x;
    		}
    	}
    	//出栈
    	public void pop(){
    		//出栈前判断栈是否为空
    		if(isEmpty()){
    			try {
    				throw new Exception("The stack is Empty!");
    			} catch (Exception e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}else{
    			/*theArray[topOfStack--]=null;相当于
    			 *theArray[topOfStack]=null;
    			 *topOfStack--;
    			 * */
    			theArray[topOfStack--]=null;
    		}
    	}
    	//拿到栈顶元素并出栈
    	public Object topAndPop(){
    		if(isEmpty()){
    			return null;
    		}else{
    			Object topItem=top();
    			theArray[topOfStack--]=null;
    			return topItem;
    		}
    	}
    	//拿到栈顶元素
    	public Object top(){
    		if(isEmpty()){
    			return null;
    		}else{
    			return theArray[topOfStack];
    		}
    	}
    	
    	public static void main(String[] args) {
    		MyStack_Array stack=new MyStack_Array();
    		stack.push(1);
    		stack.push(2);
    		stack.push(3);
    		stack.push(4);
    		stack.push(5);
    		stack.push(6);
    		stack.push(7);
    		stack.push(8);
    		stack.push(9);
    		stack.push(10);
    		//stack.push(11);//大于容量会报错The stack is Full
    		//遍历栈
    		while(!stack.isEmpty())
    		System.out.println(stack.topAndPop());
    	}
    }

3、对于栈的应用

a、平衡符号：做一个空栈，读入字符直到文件尾部。如果这个字符为一个开放的符号，则入栈，如果为一个封闭的符号，则栈空时报错，否则将元素弹出，找到对应的开放符号，没有就报错。

b、后缀表达式：6 5 2 3 + 8 \* 3 + \* 实现的基本思想为：遇到数字就将数字入栈，遇到符号就弹出两个元素进行相关运算，然后入栈，直到完成。

String str="6523+8*+3+*";
            String [] strs=str.split("");
        	for(int i=0;i<strs.length;i++){
        	if(strs[i].trim().length()!=0){
        		if(strs[i].matches("\\d")){
        			//将数字入栈
        			 push(Integer.parseInt(strs[i]));
        		}else{
        			 //出栈两个数字
        			 int a=(Integer) topAndPop();
        			 int b=(Integer) topAndPop();
        			 //对数据进行运算再入栈
        			 if(strs[i].equals("*")){
        				 push(a*b);
        			 }else if(strs[i].equals("+")){
        				 push(a+b);
        			 }
        		}
        	}
        }

c、也可以进行数制转换，基本思想：将十进制数转换为二进制数，首先将目标十进制数n模以2(n%2)然后入栈，然后将目标数n置为原来的一般，再进行模以操作。

Stack stack=new Stack();
    while(n>0){
       stack.push(n%2);
       n=n/2;
    }

4、栈的pop()方法与peek()方法的区别：

pop()方法会把栈顶的元素进行删除，peek()不会改变栈的值。

[Center]: /images/20220806/4936202d1bc84c78b749ee0a4b9a7305.png