Dsa Using Java 简明教程

DSA using Java - Stack

Overview

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

Stack is kind of data structure which allows operations on data only at one end. It allows access to the last inserted data only. Stack is also called LIFO (Last In First Out) data structure and Push and Pop operations are related in such a way that only last item pushed (added to stack) can be popped (removed from the stack).

Stack Representation

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

We’re going to implement Stack using array in this article.

Basic Operations

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

Following are two primary operations of a stack which are following.

Push − push an element at the top of the stack.
Pop − pop an element from the top of the stack.

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

There is few more operations supported by stack which are following.

Peek − get the top element of the stack.
isFull − check if stack is full.
isEmpty − check if stack is empty.

Push Operation

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

Whenever an element is pushed into stack, stack stores that element at the top of the storage and increments the top index for later use. If storage is full then an error message is usually shown.

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

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

Whenever an element is to be popped from stack, stack retrives the element from the top of the storage and decrements the top index for later use.

// 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());
   }
}

如果我们编译并运行上述程序，它将生成以下结果 -

If we compile and run the above program then it would produce following result −

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