자바 데이터 구조 기초:스 택

준비 작업
도구:idea+jdk 8
기술 요구:자바 기초 문법
부호화 고리
우선,우 리 는 먼저 어떤 데이터 로 창고 의 조작 을 모 의 하 는 지 확인 해 야 한다.하나의 원소 가 창고 안에 들 어 있 기 때문에 우 리 는 수조 로 실현 하 는 것 을 고려 할 수 있다.

이상 은 자바 공식 문서 의 스 택 정의 입 니 다.우 리 는 세 가지 방법 만 실현 해 야 합 니 다.스 택 의 맨 끝 에 있 는 대상 을 제거 하고 요 소 를 추가 하 는 것 입 니 다.
그래서 우 리 는 사전에 하나의 배열 을 정의 해 야 한다.

Objects[] arr;

배열 이 정 의 된 후에 우 리 는 어떻게 스 택 의 끝 이나 스 택 의 첫 번 째 요 소 를 얻 을 수 있 는 지 생각해 보 세 요.배열 의 색인 을 기억 하 십 니까?색인 으로 창고 의 지침 을 가정 할 수 있다.그래서 우 리 는 스 택 의 요소 갯 수 와 스 택 의 기본 길이 와 기본 지침 을 정의 해 야 합 니 다.

private int stackLength = 4; //        
private int size; //           
private int index = -1; //            

왜 여기 가 가리 키 는 게-1 일 까요?배열 의 첫 번 째 요 소 는 색인 이 0 이라는 것 을 알 고 있 습 니 다.그러면-1 은 어떤 요소 도 가리 키 지 않 는 다 는 뜻 입 니 다.이따가 우리 가 쓸 때 다시 그 를 가리 키 자.
그리고 나 서 우 리 는 배열 의 초기 화 를 정의 해 야 한다.초기 화 된 길이 입 니 다.공식 문서 의 작성 방법 을 참고 하여 스 택 의 길이 가 가득 찬 후에 우 리 는 스 택 의 길 이 를 1.5 배 확대 할 것 이다.우 리 는 단독으로 하나의 방법 을 추출 하여 놓 을 것 이다.

/**
 *         1.5        
 */
private void capacity() {
    //      
    if (this.arr == null) {
        this.arr = new Object[this.stackLength];
    }
    //  1.5      
    if (this.size - (this.stackLength - 1) >= 0) { //                           
        this.stackLength = this.stackLength + (this.stackLength >> 1); //    ，        1/2
        this.arr = Arrays.copyOf(this.arr, this.stackLength); //         ，       
    }
}

push 방법
어떻게 창고 에 원 소 를 추가 합 니까?우리 가 고려 해 야 할 부분:지침 이 오른쪽으로 한 분 이동 하 는 것,즉 지침 이+1 이 어야 한 다 는 것 이다.그 다음으로 요 소 를 추가 한 후에 스 택 요소 의 길이 가 바 뀌 었 습 니 다.size+1.

public E push(E item){
    //       
    this.capacity();
    //     
    this.arr[++index] = item;
    //         
    this.size++;
    return item;
}

pop 방법
pop 방법 은 주로 스 택 지붕 의 요 소 를 제거 하 는 데 사 용 됩 니 다.
먼저 사고방식 을 분석 해 보 자.우 리 는 index 로 창고 꼭대기 의 요 소 를 가리 키 려 면 어떻게 지정 해 야 합 니까?
삭제 후 대응 하 는 size 길 이 는 어떻게 바 꿔 야 합 니까?
우 리 는 요소 가 추 가 된 후에 index 가 달라 질 것 이라는 것 을 알 고 있 습 니 다.그러면 우리 가 세 개의 요 소 를 추가 한 것 과 같 습 니 다.이때 index 는 가리 키 는 2 일 것 입 니 다.그럼 됐어.
제거 할 때 우 리 는 indexc 로 조작 하면 문 제 를 해결 할 수 있 습 니 다.코드 보기:

/**
 *       
 *
 * @return
 */
public E pop() {
    //                
    if (this.index == -1) {
        throw new EmptyStackException();
    }
    //       
    this.size--;
    //       
    System.out.println("           ："+index);
    return (E) this.arr[index--];
}

empty 방법
창고 가 비어 있 는 지 아 닌 지 를 판단 하 는 것 은 매우 간단 하 다.현재 size 가 0 인지 아 닌 지 직접 판단 하면 해결 할 수 있 습 니 다.

public boolean empty(){
	return this.index==0?true:false;
}

모든 코드

package com.zxy;
import java.util.Arrays;
import java.util.EmptyStackException;
/**
 * @Author Zxy
 * @Date 2021/2/2 20:24
 * @Version 1.0
 *         
 */
public class MyStack<E> {
    private Object[] arr; //          
    private int stackLength = 4; //        
    private int size; //           
    private int index = -1; //            
    /**
     *          
     */
    public boolean empty() {
        return this.size == 0 ? true : false;
    }
    /**
     *       
     *
     * @return
     */
    public E pop() {
        //                
        if (this.index == -1) {
            throw new EmptyStackException();
        }
        //       
        this.size--;
        //       
        System.out.println("           ："+index);
        return (E) this.arr[index--];
    }

    /**
     *        
     *
     * @param item
     * @return
     */
    public E push(E item) {
        //      
        this.capacity();
        //         
        System.out.println("         ："+index);
        this.arr[++index] = item;
        System.out.println("         ："+index);
        //       
        this.size++;
        return item;
    }
    /**
     *         1.5        
     */
    private void capacity() {
        //      
        if (this.arr == null) {
            this.arr = new Object[this.stackLength];
        }
        //  1.5      
        if (this.size - (this.stackLength - 1) >= 0) { //                           
            this.stackLength = this.stackLength + (this.stackLength >> 1); //    ，        1/2
            this.arr = Arrays.copyOf(this.arr, this.stackLength); //         ，       
        }
    }
    public static void main(String[] args) {
        MyStack<String> stack = new MyStack<>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        System.out.println(stack.size);
        System.out.println("      ："+stack.pop());
        /*System.out.println(stack.pop());
        System.out.println(stack.pop());*/
    }
}

총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 질 수 있 기 를 바 랍 니 다!