Java стек

Стекът в Java обикновено означава класа от Collection Framework, който имплементира интерфейса List. Работи на принципа на структурата на данните Stack, която се използва за организиране на един от видовете памет. Също така може да бъде част от паметта за съхраняване на данни. В тази статия ще обърнем внимание преди всичко на класа Stack , ще разгледаме неговите методи и ще дадем примери. Но ние също ще говорим за такава структура от данни като Stack и за Howво се използва.

Какво е стекова структура на данните

Първо, нека да разгледаме набързо Howво представлява стековата структура от данни. Това е линейна структура от данни, която се основава на принципа „Последен влязъл, първи излязъл“ (LIFO). Това е нещо като анти-опашка. Представете си тесте карти or купчина книги в кутия. Книгата, която поставите първа в стека, е най-отдолу, а първата, която ще извадим от кутията, е книгата, която е била най-отгоре - тоест тази, която е попаднала в кутията последна. Ето gif снимка, за да демонстрирате този принцип. Какво става тук? Имаме колба, в която може да удари само една топка наведнъж. Първата в колбата е оранжева топка, след това лилава и накрая зелена (извинявам се на тези, които знаят по-точните имена на тези цветове). Въпреки това, за да извлечем оранжева топка от нашата купчина колба, трябва първо да извлечем топката, която е попаднала там последна (зелената), след това тази, която е била предпоследната (но в момента на изваждането тя е последната един). Структурата на стековите данни в Java or другаде в програмирането има двете най-важни операции, push и pop . Операцията push вмъква елемент в стека, а операцията pop премахва елемент от върха на стека.

За Howво е структурата на данните Stack?

Едно от най-важните applications на стека е организирането на извиквания на подпрограми. Точката на повикване в стека съхранява address за връщане от подпрограмата след нейното приключване (и евентуално предадените параметри). С всяко вложено (включително рекурсивно) извикване на подпрограми към стека се добавят нови addressи за връщане. При всяка операция за връщане от подпрограмата (return), addressът за връщане се премахва от стека и управлението се прехвърля към него. Това приложение е толкова важно за програмирането, че в повечето процесори обратният стек е имплементиран хардуерно в набора от инструкции. В други случаи обаче стекът трябва да се моделира върху по-общи структури от данни.

Java Stack Class of Collection Framework

В Java Stack Class е клас от рамката на колекцията, който имплементира интерфейс List и разширява векторния клас. Той също така прилага интерфейси Collection, Iterable, Cloneable, Serializable. Както вероятно вече се досещате, този клас представлява LIFO стека от обекти. Ето извикването на конструктора на класа Stack , тоест създаването на обект от този клас.

Stack<E> stack = new Stack<E>();

Където E е типът на обекта.

Java стекови методи

Този клас има само един конструктор по подразбиране и всички методи на класа Vector . Освен това Stack има свои собствени 5 метода:

• boolean empty() методът проверява дали стекът е празен or не. Връща true , ако стекът е празен, false , ако не е.

• Object peek() методът връща елемента, който е в горната част на стека.

• Object pop() методът връща елемента, който е в горната част на стека и го премахва.

• Object push(Object element) методът добавя посочения елемент в горната част на стека.

• int search(Object element) методът търси в стека посочения елемент. Ако търсеният елемент бъде намерен, се връща неговото „разстояние“ от върха (сериен номер). Ако елементът не бъде намерен, се връща -1.

Пример за стеков code

Нека създадем примерна програма, която работи като gif снимката по-горе. Ще поставим три „топки“, оранжева, лилава и зелена, върху стека. Нека проверим стека за празнота. След това ще извадим топки от стека, докато стекът се изпразни.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Ето резултата от тази програма: Тъй като Stack е наследен от Vector Class и имплементира интерфейса List , Stack , в допълнение към класическите push и pop операции за тази структура от данни за добавяне и извличане на елементи, също има стандарт за списък структура add() и remove() операции. В нашия пример добавянето на елементи може да се реализира по същия начин с помощта на метода add() . Въпреки това можете да извлечете с помощта на remove() само с указан елемент, което няма смисъл за структурата на данните на стека.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Резултатът от работата на програмата, разбира се, ще бъде абсолютно същият.

Какво ще кажете за вашата собствена реализация на Stack?

Можете да създадете своя собствена стекова структура от данни в Java, като използвате масиви or класове от свързани списъци. В първия случай се разпределя непрекъснат масив от клетки за съхраняване на стойности в паметта, които се използват при необходимост. Във втория за всеки елемент от стека се подрежда блок памет, достатъчен за съхраняване на стойността и препратките към предишния и следващия елемент на стека. Реализацията, базирана на масив, е по-проста, по-ефективна и с по-голяма ефективност на паметта, но изисква предварително познаване на ограничението за размера на стека и може да доведе до трудни за намиране грешки. Базираното на списък изпълнение е по-стабилно, но по-малко ефективно. Нека направим проста реализация на стека, базирана на масив. Той ще включва функции.

• push — метод, който ще гарантира добавянето на елемент (в най-горната позиция)

• pop — метод, който ще осигури премахването на елемент (от най-горната позиция)

• readTop — метод, който ще върне стойността на елемента, който е в горна позиция

• sEmpty — метод, който ще проверява стека за празнота

• isFull — метод, който ще провери дали нашият масив, в който съхраняваме стека, не е пълен

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;

   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());

       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

Сега нека приложим пример с три топки на базата на нашия стак:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

Резултатът е тук: Ако погледнете внимателно, горната променлива всъщност съдържа индекса на последния елемент и препратката към обекта остава в масива. Така че това изпълнение се нуждае от известно подобрение. Помислете за най-лесния начин да направите това.

Трябва ли да използваме Java Stack?

Всъщност Java Stack , подобно на неговия родител Vector , е наследен клас. Вместо това обикновено се използва класът ArrayList . ArrayList не е синхронизиран, докато Vector е синхронизиран. Това означава, че с Vector само една нишка в даден момент има достъп до codeа, докато ArrayList може да работи с множество нишки. Освен това ArrayList е по-ефективен и по-бърз. Така че най-вероятно ще видите този клас само в наследен code. Но структурата на данните Stack се използва много често в програмирането.