devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java实现栈结构_栈java实现

作者：Cpp五条 | 2024-05-29 13:12:42

赞

踩

栈java实现

目录

一、栈概述

二、模拟实现栈 

1、入栈 

2、出栈 

3、取栈顶元素 

三、栈的应用

1、逆序打印链表

2、括号匹配问题 

3、逆波兰表达式求值

4、栈的压入、弹出序列

5、最小栈

一、栈概述

栈（Stack）也是数据结构的一种，属于线性数据结构，栈最大的特点是“先进后出”，就是先进入栈的元素后出来，栈只能每次弹出栈顶元素，不能弹出处在栈中间的元素。

二、模拟实现栈 

栈底层也是依据数组进行实现。

  1. private int[] data;
  2. private int usedSize;
  3. public myStack(){
  4.     this.data=new int[10];
  5. }

1、入栈 

将元素入栈首先要判断栈是否已满，如果满了就要扩容，否则就直接将元素插入到栈中，栈的长度加1。

  1. //入栈
  2.     public void push(int val){
  3.         if(isFull()){
  4.             data= Arrays.copyOf(data,2*data.length);
  5.         }
  6.         data[usedSize++]=val;
  7.     }
  8.     //判断栈是否已满
  9.     public boolean isFull(){
  10.         if(usedSize==data.length){
  11.             return false;
  12.         }else{
  13.             return true;
  14.         }
  15.     }

2、出栈 

出栈就首先需要判断栈是否为空，如果未空则无法取元素，否则就取出栈尾元素，栈长度减1。

  1. //出栈
  2.     public int pop(){
  3.         if(isEmpty()){
  4.             System.out.println("栈为空");
  5.         }
  6.        return data[--usedSize];
  7.     }
  8.     //判断栈是否为空
  9.     public boolean isEmpty(){
  10.         if(usedSize==0){
  11.             return true;
  12.         }
  13.         return false;
  14.     }

3、取栈顶元素 

与出栈不同，取栈顶元素只是拿到栈顶的元素，并不会让元素出栈，也需要判断栈是否为空。

  1. //取栈顶元素
  2.     public int peek(){
  3.         if(isEmpty()){
  4.             System.out.println("栈为空");
  5.         }
  6.         return data[usedSize-1];
  7.     }

在Java标准库中也只实现了以上方法，但是在用Stack类时却有许多方法，因为Stack类继承了Vector类，Vector类本身也实现了许多方法。 

三、栈的应用

1、逆序打印链表

由于栈是先进后出的，所以就将链表中的元素全部入栈，再接着全部出栈。

  1. //逆序打印链表
  2.     public void printList(ListNode head){
  3.         ListNode cur=head;
  4.         Stack<Object> stack = new Stack<>();
  5.         while(cur!=null){
  6.             stack.push(cur.val);
  7.             cur=cur.next;
  8.         }
  9.         while(!stack.empty()){
  10.             System.out.println(stack.pop());
  11.         }
  12.     }

此处也可以通过递归来依靠链表直接打印。 

  1. //递归实现逆序打印链表
  2.     public void printList2(ListNode head){
  3.         if(head==null){
  4.             return;
  5.         }else if(head.next==null){
  6.             System.out.println(head.val);
  7.         }else{
  8.             printList(head.next);
  9.             System.out.println(head.val);
  10.         }
  11.     }

2、括号匹配问题 

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。

解题思路：可以遍历字符串，遇到左括号则入栈，遇到右括号则取栈顶元素进行匹配，若匹配失败则直接返回false，否则继续向下遍历，如果出现栈为空但是仍有右括号或栈不为空，但是字符串已经遍历完的情况也需要返回失败。

  1.  public boolean isValid(String s) {
  2.         Stack<Character> stack=new Stack<>();
  3.         for(int i=0;i<s.length();i++){
  4.             char ch=s.charAt(i);
  5.             if(ch=='('||ch=='['||ch=='{'){
  6.                 stack.push(ch);
  7.             }else{
  8.                 if(!stack.isEmpty()){
  9.                     char ch1=stack.peek();
  10.                    if(ch1=='('&&ch==')'||ch1=='['&&ch==']'||ch1=='{'&&ch=='}'){
  11.                         stack.pop();
  12.                     }else{
  13.                         return false;
  14.                     }
  15.                 }else{
  16.                     return false;
  17.                 }
  18.             }
  19.         }
  20.         if(!stack.isEmpty()){
  21.             return false;
  22.         }
  23.         return true;
  24.     }

3、逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

逆波兰表达式也就是后缀表达式，我们通常使用的是中缀表达式，那么中缀表达式如何变成后缀表达式？

例如：

解题思路：由于本题给的就是一个后缀表达式，那么就不需要进行转换，可以通过遍历数组，如果是数字就入栈，如果是符号就弹出两个元素，分别作为左运算数和右运算数，因为-和/是要求运算顺序，然后将计算结果入栈，遍历完之后，栈中剩余的唯一元素就是表达式事务计算结果。

  1. public int evalRPN(String[] tokens) {
  2.         Stack<String > stack=new Stack<>();
  3.         for(int i=0;i<tokens.length;i++){
  4.             if(tokens[i].equals("+")||tokens[i].equals("-")||tokens[i].equals("*")||tokens[i].equals("/")
  5.                     &&!stack.isEmpty()){
  6.                 int a=Integer.parseInt(stack.pop());
  7.                 int b=Integer.parseInt(stack.pop());
  8.                 int result=0;
  9.                 switch(tokens[i]){
  10.                     case "+":
  11.                         result=b+a;
  12.                         break;
  13.                     case "-":
  14.                         result=b-a;
  15.                         break;
  16.                     case "*":
  17.                         result=b*a;
  18.                         break;
  19.                     case "/":
  20.                         result=b/a;
  21.                         break;
  22.                 }
  23.                 stack.push(String.valueOf(result));
  24.             }else{
  25.                 stack.push(tokens[i]);
  26.             }
  27.         }
  28.         return Integer.parseInt(stack.pop());
  29.     }

4、栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

解题思路：设置一个指针指向弹出序列的首个元素，将入栈序列的元素入栈，之后判断栈顶元素与指针所指的元素是否相同，若相同则指针后移，弹出栈顶元素，否则继续入栈，重复上述步骤，如果将入栈序列遍历完之后，栈不为空则返回false否则返回true。

  1. public boolean IsPopOrder(int [] pushA,int [] popA) {
  2.       Stack<Integer> stack=new Stack<>();
  3.         int j=0;
  4.         for(int i=0;i<pushA.length;i++){
  5.             stack.push(pushA[i]);
  6.             while(!stack.isEmpty()&&j<popA.length&&stack.peek().equals(popA[j])){
  7.                 stack.pop();
  8.                 j++;
  9.             }
  10.         }
  11.         if(!stack.isEmpty()){
  12.             return false;
  13.         }
  14.         return true;
  15.     }

5、最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

解题思路：在该问题中需要设置一个辅助栈minStack，

在插入元素时，如果minStack为空就直接插入，如果插入元素的值小于等于minStack的栈顶元素时就插入。

在删除栈顶元素时，如果minStack的栈顶元素与Stack的栈顶元素相同时也需要弹出。

在获取栈顶元素时，直接取Stack的栈顶元素。

在获取栈顶的最小元素时，则直接取minStack的栈顶元素。 

  1. class MinStack {
  2.     Stack<Integer> stack;
  3.     Stack<Integer> minStack;
  4.     public MinStack() {
  5.         stack=new Stack<>();
  6.         minStack=new Stack<>();
  7.     }
  8.  
  9.     public void push(int val) {
  10.         stack.push(val);
  11.         if(minStack.isEmpty()){
  12.             minStack.push(val);
  13.         }else{
  14.             if(val<=minStack.peek()){
  15.                 minStack.push(val);
  16.             }
  17.         }
  18.     }
  19.  
  20.     public void pop() {
  21.         if(!stack.isEmpty()){
  22.             if(stack.pop().equals(minStack.peek())){
  23.                 minStack.pop();
  24.             }
  25.         }
  26.     }
  27.  
  28.     public int top() {
  29.         if(!stack.isEmpty()){
  30.             return stack.peek();
  31.         }
  32.         return -1;
  33.     }
  34.  
  35.     public int getMin() {
  36.         return minStack.peek();
  37.     }
  38. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/642286
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号