使用 Java 的 DSA -堆栈

概述

Stack 堆栈是一种数据结构，它只允许在一端对数据进行操作。它只允许访问最后插入的数据。Stack 也称为 LIFO(后进先出)数据结构，Push 和 Pop 操作以这样的方式相关:只有最后推送(添加到堆栈)的项目才能弹出(从堆栈中删除)。

Stack 表示

我们将在本文中使用数组实现 Stack。

基本操作

以下是堆栈的两个主要操作。

• Push −将元素推送到堆栈顶部。

• Pop − 从堆栈顶部弹出一个元素。

堆栈支持以下几个操作。

• Peek − 获取堆栈顶部元素。

• isFull − 检查堆栈是否已满。

• isEmpty − 检查堆栈是否为空。

推送操作

每当将元素推送到堆栈时，堆栈都会将该元素存储在存储的顶部并增加顶部索引以供以后使用。如果存储已满，通常会显示错误消息。

// 将项目推送到堆栈顶部 
public void push(int data) {

   if(!isFull()){
      // 将 top 加 1 并插入数据
      intArray[++top] = data;
   }else{
      System.out.println("Cannot add data. Stack is full.");
   }      
}

弹出操作

每当要从堆栈中弹出一个元素时，堆栈都会从存储顶部检索该元素并减少顶部索引以供以后使用。

// 从堆栈顶部弹出项目
public int pop() {
    // 检索数据并将顶部减少 1
    return intArray[top--];
}

堆栈实现

Stack.java

package com.tutorialspoint.datastructure;

public class Stack {
    private int size; // 堆栈的大小
    private int[] intArray; // 堆栈存储
    private int top; // 堆栈顶部
    
    // 构造函数
    public Stack(int size){
        this.size = size;
        intArray = new int[size]; //初始化数组
        top = -1; //堆栈最初为空
    }
    
    // 操作:推送
    // 将项目推送到堆栈顶部
    public void push(int data) {
    
        if(!isFull()){
            // 将顶部增加 1 并插入数据
            intArray[++top] = data;
        }else{
            System.out.println("无法添加数据。堆栈已满。");
        }
    }
    
    // 操作:弹出
    // 从堆栈顶部弹出项目
    public int pop() {
        //检索数据并将顶部减少 1
        return intArray[top--];
    }
    
    // 操作:Peek
    // 查看堆栈顶部的数据
    public int peek() {
        // 从顶部检索数据
        return intArray[top];
    }
    
    // 操作:isFull
    // 如果堆栈已满，则返回 true
    public boolean isFull(){
        return (top == size-1);
    }
    
    // 操作:isEmpty
    // 如果堆栈为空，则返回 true
    public boolean isEmpty(){
        return (top == -1);
    }
}

演示程序

StackDemo.java

package com.tutorialspoint.datastructure;

public class StackDemo {
   public static void main (String[] args){

        // 创建新堆栈
        Stack stack = new Stack(10);
        
        // 将项目推送到堆栈上
        stack.push(3);
        stack.push(5);
        stack.push(9);
        stack.push(1);
        stack.push(12);
        stack.push(15);
        
        System.out.println("堆栈顶部的元素:" + stack.peek());
        System.out.println("元素:");
        
        // 打印堆栈数据
        while(!stack.isEmpty()){
         int data = stack.pop();
         System.out.println(data);
        }
             
        System.out.println("堆栈已满: " + stack.isFull());
        System.out.println("堆栈为空: " + stack.isEmpty());
   }
}

如果我们编译并运行上述程序，则会产生以下结果 −

堆栈顶部的元素:15
元素:
15
12
1
9
5
3
堆栈已满:false
堆栈为空:true