Реализация стека с использованием массива в Java

java arrays algorithm performance data-structures

3625 просмотра

2 ответа

40 Репутация автора

Я пытаюсь реализовать стек, используя массив в качестве его ядра в Java. Это просто цель изучения и понимания того, как работает стек.

Моя идея состояла в том, чтобы использовать Array (не ArrayList) и попытаться имитировать структуру стека. Эта реализация будет иметь статический размер. Есть указатель, который начинается с -1, чтобы указать пустой стек. Указатель будет увеличиваться при добавлении элемента, и нам не нужно беспокоиться об удалении элемента, потому что мы переопределим значение, как только нам понадобится это пространство (индекс).

Следующее будет моим исходным кодом и сопровождается некоторыми вопросами:

import java.util.*;

public class stackUsingArray{

   private int[] myStack;
   private int pointer;

   /**
    -Constructor
   */
   public stackUsingArray()
   {
       myStack = new int[10];
       pointer = -1;//keep track of where the top element is on the stack.
   }

   /**
    -Pop method
   */
   public int pop()
  {      
      if(pointer==-1)
      {
          //throw exception here
      }
      return myStack[pointer--];
  }

  /**
  -Push when the stack is not empty.
  */

   public void push(int num)
   {
       if(pointer== myStack.size()-1)
       {
           //throw exception here
       }
       else
       {
            myStack[++pointer] = num;//add to the stack           
        }       
   }

/**
-return the top element of the stack
*/
   public void peek()
   {
       return pointer;
   }

/**
-return false if there is not more element on the stack
*/
   public boolean isEmpty()
   {
       return (pointer == -1)? true : false;
   }

   public static void main(String [] arg)
   {
       stackUsingArray newStack = new stackUsingArray();
       newStack.push(1);
       newStack.push(2);
       newStack.push(3);

       System.out.println(newStack.pop());
   }
}

В той части, где я комментирую как исключение:

public int pop()
      {      
          if(pointer==-1)
          {
              //throw exception here
          }
          return myStack[pointer--];
      }

Какое исключение вы считаете наиболее логичным? Большую часть времени я просто распечатываю на экране. Тем не менее, я хотел бы научиться бросать исключения.

Эта часть:

 public void push(int num)
   {
       if(pointer== myStack.size()-1)
       {
           //throw exception here
       }
       else
       {
            myStack[++pointer] = num;//add to the stack           
        }       
   }

Сама программа должна выполнить операцию myStack.size () -1. Интересно, лучше ли в классе иметь закрытого члена, чтобы он был размером -1? Я имею в виду эффективность.

Кроме того, если бы мы использовали ArrayList для реализации этого стека. Будет ли он работать более эффективно? Я имею в виду, ArrayList имеет много накладных расходов, таких как внутренний вызов методов.

Наконец, я знаю, что мой код не очень хорош, поэтому, пожалуйста, дайте мне несколько советов, чтобы сделать его лучше!

Автор: Sengngy Kouch Источник Размещён: 18.07.2016 12:27

Ответы (2)


1 плюс

343 Репутация автора

Решение

Я бы бросил пользовательские StackEmptyException / StackFullException, полученные из RuntimeException, чтобы они не проверялись. Если этот флажок не установлен, ваши пользователи не должны окружать каждый pop () внутри try / catch. Если вы выбрасываете проверенное исключение, им придется либо попробовать / перехватить каждое поп-сообщение, либо объявить свои собственные методы как выбрасывающее исключение. См. Это обсуждение для получения дополнительной информации: Java: проверено против объяснения непроверенного исключения

Сама программа должна выполнить операцию myStack.size () -1. Интересно, лучше ли в классе иметь закрытого члена, чтобы он был размером -1? Я имею в виду эффективность.

Это вообще не будет заметно, не делайте оптимизаций, которые только сэкономят вам один или два такта процессора, но которые уменьшают сложность алгоритма или количество операций ввода-вывода.

Кроме того, если бы мы использовали ArrayList для реализации этого стека. Будет ли он работать более эффективно? Я имею в виду, ArrayList имеет много накладных расходов, таких как внутренний вызов методов.

Он будет работать так же, как ваша собственная реализация, если вы начнете увеличивать массив внутри.

Наконец, я знаю, что мой код не очень хорош, поэтому, пожалуйста, дайте мне несколько советов, чтобы сделать его лучше! Спасибо вам большое!

Это очень хорошо для учебного проекта, продолжайте в том же духе;)

Автор: Slavcho Размещён: 18.07.2016 12:35

1 плюс

661 Репутация автора

Наиболее логичное исключение, которое выбрасывается, когда стек пуст, является дискуссионным, но я бы пошел с IllegalStateException.

throw new IllegalStateException("An empty stack cannot be popped.");

Я бы также использовал ArrayList, а не массив. С массивами вы должны сами позаботиться о переполнении индекса, тогда как ArrayList справится с этим внутренне довольно эффективно. Каждый раз, когда вы добавляете что-то в ArrayList, и он выходит за пределы размера массива, он копирует данные в новый массив, который в два раза больше старого. Это по-прежнему дает амортизированное время добавления O (1) из-за относительной редкости события.

Если вы используете ArrayList, вы можете избавиться от счетчика стека, так как вы можете проверить размер ArrayList. Вы можете потерять преимущество отсутствия необходимости удалять записи из выталкивающего стека (я не помню, оптимизирует ли ArrayList это самостоятельно).

Что касается стиля кода, то в Java принято использовать заглавные имена классов, поэтому вы должны переименовать свой класс в соответствии с соглашением.

Ваш метод peek объявлен как void и должен возвращать myStack [pointer]. Также в методе push вы вызываете myStack.size (), который не подходит для массивов. Используйте myStack.length, если вы не переключаетесь на использование ArrayList.

Автор: jvalli Размещён: 18.07.2016 12:39
Вопросы из категории :
32x32