Dsa Using Java 简明教程

DSA using Java - Stack

Overview

堆栈是一种数据结构，它仅允许在某一端对数据执行操作。它只允许访问最后插入的数据。堆栈也被称为 LIFO（后进先出）数据结构，入栈和出栈操作以这样的方式相关联，即只有最后入栈（添加到堆栈）的项目可以出栈（从堆栈中移除）。

Stack Representation

在本文中，我们将使用数组实现堆栈。

Basic Operations

堆栈的以下两个主要操作如下所示。

Push − 将一个元素压入堆栈的顶部。
Pop − 从堆栈的顶部弹出一个元素。

堆栈支持的更多操作如下所示。

Peek − 获取堆栈的顶部元素。
isFull − 检查堆栈是否已满。
isEmpty − 检查堆栈是否为空。

Push Operation

每当一个元素压入堆栈时，堆栈将该元素存储在存储区的顶部并增加顶部索引以备将来使用。如果存储区已满，则通常会显示一条错误消息。

// 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 Operation

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

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

Stack Implementation

Stack.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);
   }
}

Demo Program

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