자바 스택

Java에서 스택은 일반적으로 List 인터페이스를 구현하는 Collection Framework의 클래스를 의미합니다. 메모리 유형 중 하나를 구성하는 데 사용되는 스택 데이터 구조의 원리에 따라 작동합니다. 또한 데이터를 유지하는 것도 메모리의 일부일 수 있습니다. 이 기사에서는 우선 Stack 클래스 에 주목 하고 해당 메소드를 고려하고 예제를 제공합니다. 그러나 스택 과 같은 데이터 구조 와 그 용도에 대해서도 이야기할 것입니다.

스택 데이터 구조란?

먼저 스택 데이터 구조가 무엇인지 간단히 살펴보겠습니다. 후입선출(LIFO) 원칙을 기반으로 하는 선형 데이터 구조입니다. 일종의 안티 큐입니다. 카드 한 벌이나 상자 안에 있는 책 더미를 상상해 보십시오. 스택에 먼저 넣은 책은 맨 아래에 있고 상자에서 가장 먼저 꺼낼 책은 맨 위에 있던 책, 즉 마지막으로 상자에 넣은 책입니다. 이 원리를 보여주는 gif 사진이 있습니다. 자바 스택 - 1

무슨 일이야? 한 번에 하나의 공만 칠 수 있는 플라스크가 있습니다. 플라스크의 첫 번째는 주황색 공, 그 다음에는 보라색, 마지막으로 녹색입니다(이 색상의 더 정확한 이름을 아는 사람들에게 사과드립니다). 그러나 플라스크 스택에서 주황색 공을 추출하려면 먼저 마지막에 도착한 공(녹색 공)을 추출한 다음 두 번째 공(그러나 추출할 때는 마지막 공)을 추출해야 합니다. 하나). Java 또는 프로그래밍의 다른 곳에서 스택 데이터 구조에는 가장 중요한 두 가지 작업인 push 및 pop 이 있습니다 . 푸시 작업은 스택에 요소를 삽입하고 팝 작업은 스택 맨 위에서 요소를 제거합니다.

스택 데이터 구조는 무엇입니까?

스택의 가장 중요한 용도 중 하나는 서브루틴 호출을 구성하는 것입니다. 스택의 호출 지점은 서브루틴이 종료된 후(및 아마도 전달된 매개변수) 리턴 주소를 저장합니다. 중첩된(재귀 포함) 서브루틴 호출마다 새 반환 주소가 스택에 추가됩니다. 서브루틴(리턴)의 각 리턴 작업으로 리턴 주소가 스택에서 제거되고 제어가 이 주소로 전달됩니다. 이 애플리케이션은 대부분의 프로세서에서 리턴 스택이 명령어 세트의 하드웨어에서 구현되는 프로그래밍에 매우 중요합니다. 그러나 다른 경우에는 스택을 보다 일반적인 데이터 구조로 모델링해야 합니다.

컬렉션 프레임워크의 Java 스택 클래스

Java Stack Class는 List 인터페이스를 구현하고 Vector 클래스를 확장하는 Collection 프레임워크의 클래스입니다. 또한 Collection, Iterable, Cloneable, Serializable 인터페이스를 구현합니다. 이미 짐작하셨겠지만 이 클래스는 개체의 LIFO 스택을 나타냅니다. 다음은 Stack 클래스의 생성자, 즉 이 클래스의 객체 생성에 대한 호출입니다 .

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

여기서 E는 객체 유형입니다.

자바 스택 방법

이 클래스에는 단 하나의 기본 생성자와 Vector 클래스 의 모든 메서드가 있습니다 . 또한 Stack에는 5가지 방법이 있습니다.

boolean empty() 메서드는 스택이 비어 있는지 확인합니다. 스택이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
Object peek() 메서드는 스택의 맨 위에 있는 요소를 반환합니다.
Object pop() 메서드는 스택의 맨 위에 있는 요소를 반환하고 제거합니다.
객체 푸시(객체 요소) 메서드는 스택의 맨 위에 지정된 요소를 추가합니다.
int search(Object element) 메서드는 스택에서 지정된 요소를 검색합니다. 필요한 요소가 발견되면 상단에서 "거리"(일련 번호)가 반환됩니다. 요소를 찾을 수 없으면 -1이 반환됩니다.

스택 코드 예

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

다음은 이 프로그램의 출력입니다.

내 스택이 비어 있습니까? 스택의 진정한 요소: [주황색 공, 보라색 공, 녹색 공] 내 스택이 비어 있습니까? 스택의 거짓 요소: [주황색 공, 보라색 공] 내 스택이 비어 있습니까? 스택의 거짓 요소: [주황색 공] 내 스택이 비어 있습니까? false 스택의 요소: [] 내 스택이 비어 있습니까? 진실

Stack은 Vector Class 에서 상속되고 List 인터페이스를 구현하기 때문에 요소 를 추가하고 추출하기 위한 이 데이터 구조에 대한 고전적인 푸시 및 팝 작업 외에도 Stack에는 목록 구조 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());
           }
       }
   }

물론 프로그램 작업의 결과는 정확히 동일합니다.

자신의 스택 구현은 어떻습니까?

배열 또는 연결된 목록 클래스를 사용하여 Java에서 고유한 스택 데이터 구조를 만들 수 있습니다. 첫 번째 경우, 필요에 따라 사용되는 메모리에 값을 저장하기 위해 연속적인 셀 배열이 할당됩니다. 두 번째에서는 스택의 각 요소에 대해 스택의 이전 및 다음 요소에 대한 값과 참조를 저장하기에 충분한 메모리 블록이 정렬됩니다. 배열 기반 구현은 더 간단하고 효율적이며 메모리 효율적이지만 스택 크기 제한에 대한 사전 지식이 필요하고 찾기 어려운 버그로 이어질 수 있습니다. 목록 기반 구현은 더 강력하지만 덜 효율적입니다. 스택의 간단한 배열 기반 구현을 만들어 봅시다. 기능이 포함될 것입니다.

push — 요소 추가를 보장하는 방법(최상위 위치)
pop — 요소 제거를 제공하는 메서드(최상위 위치에서)
readTop — top 위치에 있는 요소의 값을 반환하는 메서드
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());
       }
   }

}

출력은 다음과 같습니다.

내 스택이 비어 있습니까? true [주황색 공, 보라색 공, 녹색 공] 스택이 비어 있습니까? false 녹색 공 제거 내 스택이 비어 있습니까? false 보라색 공 제거 내 스택이 비어 있습니까? false 주황색 공 제거 내 스택이 비어 있습니까? 진실

자세히 보면 최상위 변수에는 실제로 마지막 요소의 인덱스가 포함되어 있고 개체에 대한 참조는 배열에 남아 있습니다. 따라서 이 구현에는 약간의 개선이 필요합니다. 가장 쉬운 방법을 생각해 보십시오.

Java 스택을 사용해야 합니까?

사실 Java Stack 은 Vector 부모 와 마찬가지로 레거시 클래스입니다. 대신 ArrayList 클래스가 일반적으로 사용됩니다. Vector가 동기화되는 동안 ArrayList는 동기화되지 않습니다 . 이는 벡터를 사용하면 한 번에 하나의 스레드만 코드에 액세스할 수 있는 반면 ArrayList는 여러 스레드에서 작업할 수 있음을 의미합니다. 또한 ArrayList 가 더 효율적이고 빠릅니다. 따라서 이 클래스는 레거시 코드에서만 볼 수 있습니다. 그러나 스택 데이터 구조는 프로그래밍에서 매우 자주 사용됩니다.