欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java数据结构与算法_栈

程序员文章站 2024-01-24 17:17:04
...

Java数据结构与算法_栈

一、栈简介

栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶(top)。它是后进先出(LIFO)的。对栈的基本操作只有push(进栈)和pop(出栈)两种,前者相当于插入,后者相当于删除最后的元素。
Java数据结构与算法_栈

二、栈的Java实现

/**
 * @Author: slx
 * @Date: 2019/5/9 18:37
 */
public class ShuStack {
    private int[] array;
    private int maxSize;
    private int top;

    public ShuStack(int maxSize) {
        this.maxSize = maxSize;
        array = new int[maxSize];
        top = -1;
    }

    //压入元素
    public void push(int value) {
        if (top < maxSize-1) {
            array[++top] = value;
        }
    }

    //弹出栈顶元素
    public int pop() {
        return array[top--];
    }

    //访问栈顶元素
    public int peek() {
        return array[top];
    }

    //判断栈是否为空
    public boolean isEmpty() {
        return (top == -1);
    }

    //判断栈是否满了
    public boolean isFull() {
        return (top == maxSize-1);
    }
}

测试代码:

/**
 * @Author: slx
 * @Date: 2019/5/9 18:48
 */
public class ShuStackTest {
    public static void main(String[] args) {
        ShuStack stack = new ShuStack(4);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek());
        while(!stack.isEmpty()) {
            System.out.print(stack.pop() + " " );
        }
    }
}

结果:

30
30 20 10 
Process finished with exit code 0

三、栈的应用:单词逆序

import java.util.Stack;
/**
 * @Author: slx
 * @Date: 2019/5/9 18:42
 */
public class TestStringReverse {
    public static void main(String[] args) {
        Stack stack = new Stack();
        String str = "shu push";
        char[] chars = str.toCharArray();
        for (char c : chars) {
            stack.push(c);
        }
        for (int i = 0; i < str.length(); i++) {
            System.out.print(stack.peek());
            stack.pop();
        }
    }
}

结果:

hsup uhs
Process finished with exit code 0