（Java数据结构和算法）栈-----栈本质原理实现+ArrayDeque类实现自定义栈ArrayDeque类实现栈操作

68 阅读 0 评论 45 点赞

我是靠谱客的博主悦耳月光，最近开发中收集的这篇文章主要介绍（Java数据结构和算法）栈-----栈本质原理实现+ArrayDeque类实现自定义栈ArrayDeque类实现栈操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

自定义栈

class MyStack{
	private int[] a;
	private int size;
	private int top;
	
	private final int ERROR = -1;//假设其他元素不会出现负数的前提下

	public MyStack(int size){
		this.size = size;
		a = new int[size];
		top = 0;//栈顶是几，就说栈中有几个元素
	}
	public boolean isFull(){
		return (top == size);
	}
	public boolean isEmpty(){
		return (top == 0);
	}
	public boolean push(int e){
		if(isFull()){
			return false;
		}else{
			a[top++] = e;
			return true;
		}
	}
	public boolean pop(){
		if(isEmpty()){
			return false;
		}else{
			top--;
			return true;
		}
	}
	public int peek(){
		if(!isEmpty()){
			return a[top-1];
		}else{
			return ERROR;//栈已经空，应该返回错误
		}
	}

	public void print(){
		for(int i = 0; i < top; i++){
			System.out.print(a[i] +" ");
		}
		System.out.println();
	}
}

public class Main{

	//测试
	public static void main(String[] args){
		MyStack stack = new MyStack(10);
		System.out.println("入栈：");
		stack.push(1);
		stack.print();
		stack.push(2);
		stack.print();
		stack.push(3);
		stack.print();
		stack.push(4);
		stack.print();
		stack.push(5);
		stack.print();
		System.out.println();	

		System.out.println("栈顶元素： "+stack.peek());
		System.out.println("出栈：");
		while(!stack.isEmpty()){
			stack.print();
			stack.pop();
		}
		System.out.println("栈空吗？"+stack.isEmpty());
	}
}

在这里插入图片描述

ArrayDeque类实现栈操作

import java.util.ArrayDeque;
import java.util.Iterator;

public class Main{
	
	public static void print(ArrayDeque stack){
		Iterator<ArrayDeque> it = stack.iterator();
		while(it.hasNext()){
			System.out.print(it.next()+" ");
		}
		System.out.println();
	}
	
	//测试
	public static void main(String[] args){
		ArrayDeque<Integer> stack = new ArrayDeque<>(10);
		System.out.println("入栈：");
		stack.push(1);
		print(stack);
		stack.push(2);
		print(stack);
		stack.push(3);
		print(stack);
		stack.push(4);
		print(stack);
		stack.push(5);
		print(stack);
		System.out.println();	

		System.out.println("栈顶元素： "+stack.peek());
		System.out.println("出栈：");
		while(!stack.isEmpty()){
			
			stack.pop();
			print(stack);
		}
		System.out.println("栈空吗？"+stack.isEmpty());
	}
}

【实例】字符串逆序

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main{
	
	//测试
	public static void main(String[] args){
		ArrayDeque<Character> stack = new ArrayDeque<>(10);
		System.out.println("请输入一字符串： ");
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();
		for(int i = 0; i < str.length(); i++){
			stack.push(str.charAt(i));
		}
		while(!stack.isEmpty()){
			System.out.print(stack.peek());
			stack.pop();
		}
	}
}

在这里插入图片描述

另外，字符串逆序可以直接调用StringBuffer的reverse方法即可：

import java.util.Scanner;

public class Main{
	
	//测试
	public static void main(String[] args){
		System.out.println("请输入一字符串： ");
		Scanner scan = new Scanner(System.in);
		StringBuffer str = new StringBuffer(scan.next());
		System.out.println(str.reverse());
	}
}

【实例】括号匹配问题

/*
	用栈来解决括号匹配问题：
	
	针对字符串中的每个字符，
	（1）如果是(,[,{入栈；
	（2）如果是非括号，不入栈；
	（3）如果是),],}，取出栈顶元素，比较栈顶元素和当前字符是否匹配，如果不匹配，可得出结论：不匹配；
	（4）如果所有字符已经完成栈操作，栈中仍然有剩余的元素，可得出结论：不匹配；
	（5）除了以上不匹配情况外，得出结论：匹配。

*/

import java.util.Scanner;
import java.util.ArrayDeque;

public class Main{
	
	//测试
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		
		ArrayDeque<Character> stack = new ArrayDeque<>();
		
		String str = null;
		System.out.println("请输入一字符串： ");
		while(scan.hasNextLine()){
			stack.clear();
			str = scan.nextLine();
			boolean flag = true;
			for(int i = 0; i < str.length(); i++){
				Character c = str.charAt(i);
				Character top = stack.peek();
				
				switch(c){
					case '[': 
					case '(':
					case '{': 
						stack.push(c);
						break;
					case ')': 
						if(top != null && top == '('){
							stack.pop();
						}else{
							flag = false;
						}
						break;
					case ']': 
						if(top != null && top == '['){
							stack.pop();
						}else{
							flag = false;
						}
						break;
					case '}': 
						if(top != null && top == '{'){
							stack.pop();
						}else{
							flag = false;
						}
						break;
					default:	break;
				}
				if(!flag){
					break;
				}
			}
			if(!stack.isEmpty() || !flag){
				System.out.println("not correct");
			}else{
				System.out.println("correct");
			}
			System.out.println("请输入一字符串： ");
		}
	}
}