Java Stack

Ang stack sa Java ay karaniwang nangangahulugang ang klase mula sa Collection Framework na nagpapatupad ng interface ng Listahan. Gumagana ito sa prinsipyo ng istraktura ng Stack data, na ginagamit upang ayusin ang isa sa mga uri ng memorya. Maaari rin itong maging bahagi ng memorya upang mapanatili ang data, Sa artikulong ito ay bibigyan natin ng pansin ang klase ng Stack , isaalang-alang ang mga pamamaraan nito at magbigay ng mga halimbawa. Ngunit pag-uusapan din natin ang tungkol sa istraktura ng data tulad ng Stack at kung para saan ito ginagamit.

Ano ang Stack Data Structure

Una sa lahat, tingnan natin kung ano ang istraktura ng data ng stack. Ito ay isang linear na istraktura ng data na batay sa prinsipyo ng Last-in-First-out (LIFO). Ito ay uri ng anti-pila. Isipin ang isang deck ng mga card o isang stack ng mga libro sa isang kahon. Ang aklat na una mong inilagay sa salansan ay nasa ibaba, at ang una nating aalisin sa kahon ay ang aklat na nasa itaas - iyon ay, ang huling nakapasok sa kahon. Narito ang isang gif na larawan upang ipakita ang prinsipyong ito. Anong nangyayari dito? Mayroon kaming isang prasko kung saan isang bola lamang ang maaaring tumama sa isang pagkakataon. Ang una sa flask ay isang orange na bola, pagkatapos ay purple, at sa wakas ay berde (humihingi ako ng paumanhin sa mga nakakaalam ng mas tumpak na mga pangalan ng mga kulay na ito). Gayunpaman upang kunin ang isang orange na bola mula sa aming flask-stack, kailangan muna naming kunin ang bola na huling nakarating doon (ang berde), pagkatapos ay ang isa na ang penultimate isa (ngunit sa oras ng pagkuha ito ang huling isa). Ang stack data structure sa Java o sa ibang lugar sa programming ay may dalawang pinakamahalagang operasyon, push at pop . Ang push operation ay naglalagay ng elemento sa stack at ang pop operation ay nag-aalis ng elemento mula sa tuktok ng stack.

Para saan ang Stack data structure?

Isa sa pinakamahalagang gamit ng stack ay ang pag-aayos ng mga subroutine na tawag. Ang call point sa stack ay nag-iimbak ng return address mula sa subroutine pagkatapos nitong magwakas (at posibleng naipasa ang mga parameter). Sa bawat nested (kabilang ang recursive) na tawag ng mga subroutine, ang mga bagong return address ay idinaragdag sa stack. Sa bawat return operation mula sa subroutine (return), ang return address ay aalisin mula sa stack at ang kontrol ay ililipat dito. Napakahalaga ng application na ito sa programming na sa karamihan ng mga processor ang return stack ay ipinapatupad sa hardware sa set ng pagtuturo. Gayunpaman, sa ibang mga kaso, ang stack ay kailangang mamodelo sa mas pangkalahatang mga istruktura ng data.

Java Stack Class of Collection Framework

Sa Java Stack Class ay isang klase mula sa Framework ng Collection na nagpapatupad ng interface ng List at nagpapalawak ng Vector class. Nagpapatupad din ito ng mga interface na Collection, Iterable, Cloneable, Serializable. Tulad ng malamang na nahulaan mo na ang klase na ito ay kumakatawan sa LIFO stack ng mga bagay. Narito ang tawag sa tagabuo ng klase ng Stack , iyon ay, ang paglikha ng isang bagay ng klase na ito.

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

Kung saan ang E ay ang uri ng Bagay.

Mga Paraan ng Java Stack

Ang klase na ito ay mayroon lamang isang default na tagabuo at lahat ng mga pamamaraan ng klase ng Vector . Dagdag pa, ang Stack ay may sariling 5 pamamaraan:

• boolean empty() sinusuri ng pamamaraan kung walang laman ang stack o wala. Nagbabalik ng true kung walang laman ang stack, false kung hindi.

• Object peek() ang pamamaraan ay nagbabalik ng elemento na nasa tuktok ng stack.

• Object pop() ibinabalik ng pamamaraan ang elemento na nasa tuktok ng stack at inaalis ito.

• Object push(Object element) ang pamamaraan ay nagdaragdag ng tinukoy na elemento sa tuktok ng stack.

• int search(Object element) ang paraan ay naghahanap sa stack para sa tinukoy na elemento. Kung natagpuan ang kinakailangang elemento, ang "distansya" nito mula sa itaas (serial number) ay ibabalik. Kung ang elemento ay hindi natagpuan, -1 ay ibinalik.

Halimbawa ng stack code

Gumawa tayo ng isang halimbawa ng programa na gumagana tulad ng gif na larawan sa itaas. Maglalagay kami ng tatlong "bola", orange, purple at berde, sa stack. Suriin natin ang stack para sa kawalan ng laman. Pagkatapos, kukuha kami ng mga bola mula sa stack hanggang sa walang laman ang stack.

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

Narito ang output ng program na ito: Dahil ang Stack ay minana mula sa Vector Class at ipinapatupad ang interface ng Listahan , ang Stack , bilang karagdagan sa mga klasikong push at pop na operasyon para sa istruktura ng data na ito para sa pagdaragdag at pag-extract ng mga elemento, ay mayroon ding pamantayan para sa mga operasyon ng list structure add() at remove() . Sa aming halimbawa, ang pagdaragdag ng mga elemento ay maaaring ipatupad sa parehong paraan gamit ang add() na paraan. Gayunpaman maaari mong i-extract gamit ang remove() lamang sa isang elementong tinukoy, na walang saysay para sa stack data structure.

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

Ang resulta ng gawain ng programa, siyempre, ay magiging eksaktong pareho.

Paano ang tungkol sa iyong sariling pagpapatupad ng Stack?

Maaari kang lumikha ng iyong sariling stack data structure sa Java gamit ang mga arrays o linked list classes. Sa unang kaso, ang isang tuluy-tuloy na hanay ng mga cell ay inilalaan upang mag-imbak ng mga halaga sa memorya, na ginagamit kung kinakailangan. Sa pangalawa, para sa bawat elemento ng stack, ang isang bloke ng memorya ay iniutos, sapat upang iimbak ang halaga at mga sanggunian sa nauna at susunod na mga elemento ng stack. Ang pagpapatupad na nakabatay sa array ay mas simple, mas mahusay, at mas mahusay sa memorya, ngunit nangangailangan ito ng paunang kaalaman sa limitasyon sa laki ng stack at maaaring humantong sa mga bug na mahirap hanapin. Ang pagpapatupad na nakabatay sa listahan ay mas matatag ngunit hindi gaanong mahusay. Gumawa tayo ng simpleng array-based na pagpapatupad ng stack. Isasama nito ang mga function.

• push — isang paraan na titiyakin ang pagdaragdag ng isang elemento (sa tuktok na posisyon)

• pop — isang paraan na magbibigay ng pag-alis ng isang elemento (mula sa tuktok na posisyon)

• readTop — isang paraan na magbabalik ng halaga ng elemento na nasa itaas ng posisyon

• sEmpty — isang paraan na susuriin ang stack para sa kawalan ng laman

• isFull — isang paraan na magsusuri kung ang aming array kung saan namin iniimbak ang stack ay hindi puno

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

Ngayon ipatupad natin ang isang halimbawa na may tatlong bola batay sa aming stack:

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

}

Ang output ay narito: Kung titingnan mong mabuti, ang nangungunang variable ay talagang naglalaman ng index ng huling elemento, at ang reference sa object ay nananatili sa array. Kaya ang pagpapatupad na ito ay nangangailangan ng ilang pagpapabuti. Isipin ang pinakamadaling paraan upang gawin ito.

Dapat ba nating gamitin ang Java Stack?

Sa katunayan, ang Java Stack , tulad ng Vector parent nito, ay isang legacy na klase. Sa halip, karaniwang ginagamit ang klase ng ArrayList . Ang ArrayList ay hindi naka-synchronize habang ang Vector ay naka-synchronize. Ibig sabihin, sa Vector , isang thread lang sa bawat pagkakataon ang makaka-access sa code, habang ang ArrayList ay maaaring gumana sa maraming thread. Gayundin, ang ArrayList ay mas mahusay at mas mabilis. Kaya malamang na makikita mo lang ang klase na ito sa legacy code. Ngunit ang Stack data structure ay madalas na ginagamit sa programming.