使用Java的DSA - 堆栈内存溢出

---

概述

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

堆栈表示

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

基本操作

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

• Push - 将一个元素压入栈顶。

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

以下是堆栈支持的更多操作。

• Peek - 获取堆栈顶部的元素。

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

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

推送操作

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

// push item on the top of the stack 
public void push(int data) {

   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   }else{
      System.out.println("Cannot add data. Stack is full.");
   }      
}

流行操作

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

// pop item from the top of the stack 
public int pop() {
   // retrieve data and decrement the top by 1 
   return intArray[top--];        
}

堆栈实现

堆栈.java

package com.tutorialspoint.datastructure;

public class Stack {
   private int size;           // size of the stack
   private int[] intArray;     // stack storage
   private int top;            // top of the stack

   // Constructor 
   public Stack(int size){
      this.size = size;           
      intArray = new int[size];   //initialize array
      top = -1;                   //stack is initially empty
   }

   // Operation : Push
   // push item on the top of the stack 
   public void push(int data) {

      if(!isFull()){
         // increment top by 1 and insert data 
         intArray[++top] = data;
      }else{
         System.out.println("Cannot add data. Stack is full.");
      }      
   }

   // Operation : Pop
   // pop item from the top of the stack 
   public int pop() {
      //retrieve data and decrement the top by 1
      return intArray[top--];        
   }

   // Operation : Peek
   // view the data at top of the stack    
   public int peek() {       
      //retrieve data from the top
      return intArray[top];
   }

   // Operation : isFull
   // return true if stack is full 
   public boolean isFull(){
      return (top == size-1);
   }
   
   // Operation : isEmpty
   // return true if stack is empty 
   public boolean isEmpty(){
      return (top == -1);
   }
}

演示程序

StackDemo.java

package com.tutorialspoint.datastructure;

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

      // make a new stack
      Stack stack = new Stack(10);

      // push items on to the stack
      stack.push(3);
      stack.push(5);
      stack.push(9);
      stack.push(1);
      stack.push(12);
      stack.push(15);

      System.out.println("Element at top of the stack: " + stack.peek());
      System.out.println("Elements: ");
	  
      // print stack data 
      while(!stack.isEmpty()){
         int data = stack.pop();
         System.out.println(data);
      }
	         
      System.out.println("Stack full: " + stack.isFull());
      System.out.println("Stack empty: " + stack.isEmpty());
   }
}

如果我们编译并运行上面的程序，那么它将产生以下结果 -

Element at top of the stack: 15
Elements: 
15
12
1
9
5
3
Stack full: false
Stack empty: true