数据结构——栈及其Java实现
执键写春秋 523 8

栈及其Java实现

栈(Stack)又名堆栈,是允许在同一端进行插入和删除操作的特殊线性表,采用先进后出(Last In First Out,LIFO)的数据存储方式,其中,允许进行插入和删除操作的一端叫作栈顶(Top),另一端叫作栈底(Bottom),栈底固定,每次出栈都是将栈顶的数据取出。栈中的元素个数若为0,则将其称为空栈。 入栈如下图所示: 数据结构——栈及其Java实现 出栈如下图所示: 数据结构——栈及其Java实现 关于栈应用的提示:

  • 在浏览器中存在一个后退的按钮,每次点击后退都是回到上一步的操作,实际上这就是栈的应用,采用的一个先进后出的操作。
  • 羽毛球筒就是一个栈,刚开始羽毛球筒是空的,也就是空栈,然后我们一个一个放入羽毛球,也就是一个一个push进栈,当我们需要使用羽毛球的时候,从筒里面拿,也就是pop出栈,但是第一个拿到的羽毛球是我们最后放进去的。

    1.Stack类常用的方法

    在Java中使用Stack类进行栈的操作,Stack类是Vector的子类。Stack类定义如下:
    public class Stack<E> extends Vector<E>
    Stack常用方法如下:
  • public boolean empty() //测试栈是否为空
  • public E peek() //返回当前栈顶的数据,但不删除
  • public E pop() //出栈,同时删除
  • public E push(E item) //向栈中压入一个数据,先入栈的数据在最下边
  • public int search(Object o)//在栈中查找元素位置,位置从栈顶开始往下算,栈顶为1,依次往下数到所查找元素位置,如果所查找元素在栈中不存在,则返回-1。

2.栈方法具体现实过程

package person.xsc.datamanage;
import java.util.Iterator;
import java.util.Stack;
public class StackDemo {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Stack<String> s = new Stack<String>();
        System.out.println("---------public boolean empty()----------");//测试栈是否为空
        if(s.isEmpty()==true) {
            System.out.println("这是个空栈!");
        }else {
            System.out.println("这不是个空栈!");
        }
        System.out.println("---------public E push(E item)-----------");//向栈中压入一个数据,先入栈的数据在最下边
        s.push("A");
        s.push("B");
        s.push("C");
        s.push("D");
        s.push("C");
        StackDemo.printStack(s);
        System.out.println("------------public E pop()---------------");//出栈,同时删除
        String str = s.pop();
        System.out.println(str);
        StackDemo.printStack(s);
        System.out.println("------------public E peek()--------------");//返回当前栈顶的数据,但不删除
        str = s.peek();
        System.out.println(str);
        StackDemo.printStack(s);
        System.out.println("-------public int search(Object o)-------");//在栈中查找
        int i = s.search("A");
        if(i!=-1) {
            System.out.println("此元素在栈中的位置为:"+i);
        }else {
            System.out.println("栈中没有此元素!");
        }
    }    
    public static void printStack(Stack<String> s){
        System.out.print("栈元素:");
        Iterator<String> it = s.iterator();
        while(it.hasNext()){
            System.out.print(it.next()+",");
        }
        System.out.print("\n");
    }
}

输出:
---------public boolean empty()----------
这是个空栈!
---------public E push(E item)-----------
栈元素:A,B,C,D,C,
------------public E pop()---------------
C
栈元素:A,B,C,D,
------------public E peek()--------------
D
栈元素:A,B,C,D,
-------public int search(Object o)-------
此元素在栈中的位置为:4

3.利用栈实现字符串逆序

package person.xsc.datamanage;
import java.io.IOException;
public class StackDemo1 {
     private static String input="https://www.helloworld.net/"; //反转前字符串
     private static String output="";//反转后字符串
     public StackDemo1(){} //无参构造
     public StackDemo1(String inpu) {//有参构造
        input = inpu;
     }
     public String doStr() {
        int stackSize = input.length(); //获取字符串的长度
        Stack stack = new Stack(stackSize); //根据字符串长度初始化栈,这里的长度就代表了栈的容量
        for (int i = 0; i < input.length(); i++) {//遍历字符串,将字符入栈
           char ch = input.charAt(i); 
           stack.push(ch); 
           System.out.print(ch+"入栈"+"  ");
        }
        System.out.println("");
        while (!stack.isEmpty()) {//判断栈是否为空
           char ch = stack.pop(); //字符出栈
           System.out.print(ch+"出栈"+"  ");
           output = output + ch; //字符连接
        }
        System.out.println("");
        return output;
     }
     class Stack {
            private int maxSize; //栈的容量
            private char[] data;//定义一个数组,用来存储栈中的数据 
            private int top;//栈的指针
            Stack(int initialSize) {
                if(initialSize>=0) {
                    this.maxSize = initialSize;
                    data = new char[initialSize];
                    top = -1;
                }else {
                    throw new RuntimeException("初始化大小不能小于0:"+initialSize);
                }       
            }
            public void push(char j) {
                if(top==maxSize-1) {//栈顶元素的指针从0开始计算
                    throw new RuntimeException("栈已经满了,无法将元素入栈!");
                }else {
                    data[++top] = j;
                } 
            }
            public char pop() {//数据出栈,从栈顶移除一个数据
                if(top==-1) {
                    throw new RuntimeException("栈为空!");
                }else {
                    return data[top--];
                }
            }
            public char peek() {
                if(top==-1) {
                    throw new RuntimeException("栈为空!");
                }else {
                    return data[top];
                }
            }
            public boolean isEmpty() {
               return (top == -1);
            }
         }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
              StackDemo1 sd = new StackDemo1(input);
              output = sd.doStr();//做入栈和出栈操作
              System.out.println("反转前: " + input);
              System.out.println("反转后: " + output);      
    }
}

输出:
h入栈  t入栈  t入栈  p入栈  s入栈  :入栈  /入栈  /入栈  w入栈  w入栈  w入栈  .入栈  h入栈  e入栈  l入栈  l入栈  o入栈  w入栈  o入栈  r入栈  l入栈  d入栈  .入栈  n入栈  e入栈  t入栈  /入栈  
/出栈  t出栈  e出栈  n出栈  .出栈  d出栈  l出栈  r出栈  o出栈  w出栈  o出栈  l出栈  l出栈  e出栈  h出栈  .出栈  w出栈  w出栈  w出栈  /出栈  /出栈  :出栈  s出栈  p出栈  t出栈  t出栈  h出栈  
反转前: https://www.helloworld.net/
反转后: /ten.dlrowolleh.www//:sptth

4.关于Stack的面试问题

  • 判断栈的push和pop序列是否一致:一个栈的输入序列为12345,下面哪个不可能是栈的输出序列?(B) A. 23415 B.54132 C.23145 D.15432
  • 找出栈中的最小值
    package person.xsc.datamanage;
    import java.util.Stack;
    public class MinStack {
      Stack<Integer> mainStack = new Stack<>();//主栈 stackstack
      Stack<Integer> minStack = new Stack<>();//辅助栈 minStackminStack,用于存放对应主栈不同时期的最小值。
      public void push(int element){//入栈操作
          mainStack.push(element);
          //如果辅助栈为空,或者新元素小于等于辅助栈栈顶,则将新元素压入辅助栈
          if(minStack.empty()|| element <= minStack.peek()){
              minStack.push(element);
          }
      }
      public Integer pop(){//出栈操作
          if(mainStack.peek().equals(minStack.peek())){//如果出栈元素和辅助栈栈顶元素值相等,辅助栈出栈
              minStack.pop();//辅助栈出栈,同时删除
          }
          return mainStack.pop();//返回主栈栈顶,同时删除
      }
      public int getMin() throws Exception{// 获取栈的最小元素
          if(mainStack.empty()==true){
              throw new Exception ("空栈 !");
          }
          return minStack.peek();//返回栈顶元素但不删除
      }   
      public static void main(String[] args) {
          // TODO Auto-generated method stub
          MinStack mainStack = new MinStack();
          mainStack.push(8);
          mainStack.push(11);
          mainStack.push(5);
          mainStack.push(20);
          try {
              System.out.println(mainStack.getMin());
          } catch (Exception e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
          }
      }
    }
    

输出:5

评论区

索引目录