증강 형 스 택 에서 얻 은 시사 점

서문

감사 해 야 할 사람

주제 분석

제목 요구

제목

요구

사고 실현

데이터 스 택

순위 창고

더 블 스 택 은 어떻게 협조 합 니까

실 현 된 두 가지 방식

나의 코드 실현

수확 과 시사 점

머리말
감사 할 사람
여름 방학 이 끝 날 무렵 에 사적인 편 지 를 받 았 다.에서 오다http://blog.csdn.net/u011068702 박우 적그리고 나 에 게 좋 은 책 을 추천 했다.프로그래머 코드 면접 안내: IT 명 기업 알고리즘 과 데이터 구조 문제 가 가장 잘 풀 리 고 왼쪽 클 라 우 드 학자 들 이 문 제 를 푸 는 5 년 의 경험 결정 으로 좋 은 책 입 니 다.
여기 서 다시 한 번 감 사 드 립 니 다.http://blog.csdn.net/u011068702 박 우!
주 제 를 대충 분석 하 다.
본 고 는 주로 문제 풀이 사고의 연장 과 응용 을 배 웠 고 getMin 의 Stack 을 바탕 으로 getMax 의 Stack 을 실현 했다.그리고 이 두 가지 예 에서 저 는 어떤 사상, 같은 문 제 를 해결 하 는 방향 을 배 웠 습 니 다.
제목 요구
제목.
특수 한 스 택 을 실현 하고 스 택 의 기본 기능 을 실현 하 는 토대 에서 스 택 으로 돌아 가 는 최소 요소 의 작업 을 실현 합 니 다.
요구 하 다.
1. pop, push, getMin 작업 의 시간 복잡 도 는 모두 O (1) 2 이 고 디자인 된 스 택 유형 은 기 존의 스 택 구 조 를 사용 할 수 있 습 니 다.
사고의 방향 을 실현 하 다.
제목 과 요 구 를 다 봤 는데 똑 같이 안개 가 낀 것 같 지 않 아 요?나 자신 에 게 있어 서 내 가 먼저 생각 한 것 은 바로 다 차원 배열 을 통 해 이 루어 지 는 것 이다. push 의 순서, 횟수, 그리고 해당 하 는 값 (물론 기수 로 정렬 하거나 통 으로 정렬 하 는 사상 으로 보관 하 는 것) 을 기록 하 는 것 이다. 그러나 문 제 는 시간 복잡 도 에 대해 현저 한 요 구 를 가지 기 때문에 이것 은 힘 에 부 치 는 것 이 분명 하 다.
작가 가 실현 하 는 방식 은 매우 교묘 하 다. 그것 은 바로 부가 대가 (스 택 추가) 를 증가 하 는 방식 으로 시간 계산 상의 차원 을 낮 추어 요 구 를 만족 시 키 는 시간 복잡 도 를 실현 하 는 것 이다!
데이터 스 택
데이터 스 택 의 존 재 는 정상 적 인 스 택 을 유지 하 는 pop 과 push 작업 입 니 다.물론 이것 은 흔히 볼 수 있 는 일반적인 pop, push 조작 이 아니 라 관련 논리 적 처 리 를 거 친 것 이다.
순위 창고
순위 스 택 의 가장 핵심 적 인 역할 은 getMin 기능 을 실현 하 는 것 입 니 다. 그러나 중요 한 부분 은 상기 pop, push 에 맞 춰 데이터 의 압축 과 팝 업 을 완성 하여 순위 스 택 의 데 이 터 를 질서 있 게 하 는 것 입 니 다.
더 블 스 택 어떻게 맞 춰 요?
배합 방식 에 대해 서 는 커버 형 과 비 피복 형 이 있 지만 이번 실험의 중점 이 아니 라 이따가 코드 가 더욱 명확 한 인식 을 줄 것 이다.다음은 먼저 손 으로 그린 그림 을 간단하게 보 여 드 리 겠 습 니 다.
실현 의 두 가지 방식
지금 은 아까 의 커버 형 과 비 커버 형 문제 에 이 어 커버 되 지 않 는 것 은 pop, push 와 맞 춰 야 합 니 다.
비 덮어 쓰기 형의 실현
만약 에 value 가 더 작 거나 둘 이 같다 면 value 도 stackMin 에 눌 러 넣 습 니 다. value 에서 스 택 꼭대기 요소 가 작 으 면 stackMin 은 그 어떠한 내용 도 누 르 지 않 고 데 이 터 를 꺼 낼 때 더 블 스 택 꼭대기 요소 가 일치 할 때 더 블 스 택 pop 만 확보 해 야 합 니 다. 그렇지 않 으 면 데이터 스 택 pop 만 있 으 면 최소 요 소 는 항상 스 택 의 스 택 꼭대기 에 유지 할 수 있 습 니 다.
덮어 쓰기 형의 실현 은
눌 러 넣 을 때 와 앞의 다른 방식 은 만약 에 눌 러 넣 은 데이터 가 창고 꼭대기 요소 보다 크 면 우 리 는 여전히 창고 꼭대기 요 소 를 눌 러 넣 는 것 이다.마찬가지 로 이때 우리 pop 은 마음대로 했다.스 택 에 pop 이 나 오 는 것 은 데이터 스 택 에 저 장 된 요소 의 최소 값 이기 때 문 입 니 다.
내 코드 구현
코드 가 조금 길 지만 핵심 알고리즘 은 간단 해서 더 이상 주석 을 많이 하지 않 습 니 다.

/** * @Date 2016 9 6  * * @author     * */
package stack_and_queue;

import java.util.Map;
import java.util.Stack;

/** * @author     * */
public class BetterStack {
    public static void main(String[] args) {
        NotOverrideMinStack notors = new NotOverrideMinStack();
        notors.push(2);
        notors.push(3);
        notors.push(1);
        notors.push(7);
        notors.push(12);

        System.out.println("    ：" + (notors.getMin()));
        System.out.println("       ：" + notors.pop());
        System.out.println("    ：" + (notors.getMin()));
        System.out.println("       ：" + notors.pop());
        System.out.println("    ：" + (notors.getMin()));
        System.out.println("       ：" + notors.pop());
        System.out.println("    ：" + (notors.getMin()));
        System.out.println("       ：" + notors.pop());
        System.out.println("    ：" + (notors.getMin()));
        System.out.println("       ：" + notors.pop());

        System.out.println("-------------------     ---------------");
        OverrideMinStack ors = new OverrideMinStack();
        ors.push(2);
        ors.push(3);
        ors.push(1);
        ors.push(7);
        ors.push(12);

        System.out.println("    ：" + (ors.getMin()));
        System.out.println("       ：" + ors.pop());
        System.out.println("    ：" + (ors.getMin()));
        System.out.println("       ：" + ors.pop());
        System.out.println("    ：" + (ors.getMin()));
        System.out.println("       ：" + ors.pop());
        System.out.println("    ：" + (ors.getMin()));
        System.out.println("       ：" + ors.pop());
        System.out.println("    ：" + (ors.getMin()));
        System.out.println("       ：" + ors.pop());

        System.out.println("--------------------Min&&Max   ----------------------");
        NotOverrideMaxStack notorms = new NotOverrideMaxStack();
        notorms.push(2);
        notorms.push(1);
        notorms.push(7);
        notorms.push(3);
        notorms.push(12);

        System.out.println("    ： " + notorms.getMax());
        System.out.println("       ： " + notorms.pop());
        System.out.println("    ： " + notorms.getMax());
        System.out.println("       ： " + notorms.pop());
        System.out.println("    ： " + notorms.getMax());
        System.out.println("       ： " + notorms.pop());
        System.out.println("    ： " + notorms.getMax());
        System.out.println("       ： " + notorms.pop());
        System.out.println("    ： " + notorms.getMax());
        System.out.println("       ： " + notorms.pop());

        System.out.println("--------------------   ----------------------");
        OverrideMaxStack orms = new OverrideMaxStack();
        orms.push(2);
        orms.push(1);
        orms.push(7);
        orms.push(3);
        orms.push(12);

        System.out.println("    ： " + orms.getMax());
        System.out.println("       ： " + orms.pop());
        System.out.println("    ： " + orms.getMax());
        System.out.println("       ： " + orms.pop());
        System.out.println("    ： " + orms.getMax());
        System.out.println("       ： " + orms.pop());
        System.out.println("    ： " + orms.getMax());
        System.out.println("       ： " + orms.pop());
        System.out.println("    ： " + orms.getMax());
        System.out.println("       ： " + orms.pop());
    }

}

class NotOverrideMinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public NotOverrideMinStack() {
        this.dataStack = new Stack<Integer>();
        this.minStack = new Stack<Integer>();
    }

    public void push(int item) {
        if (this.dataStack.size() == 0) {
            this.minStack.push(item);
        } else {
            Integer stack_top_value = this.dataStack.peek();
            if (item < stack_top_value) {
                this.minStack.push(item);
            }
        }
        this.dataStack.push(item);

    }

    public Integer pop() {
        Integer stack_top_value = this.dataStack.peek();
        // if (stack_top_value == minStack.peek()) {
        if (stack_top_value == this.getMin()) {
            this.minStack.pop();
        }
        return this.dataStack.pop();
    }

    public Integer getMin() {
        if (!this.minStack.isEmpty()) {
            return this.minStack.peek();
        }
        return null;
    }
}

class OverrideMinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public OverrideMinStack() {
        this.dataStack = new Stack<Integer>();
        this.minStack = new Stack<Integer>();
    }

    public void push(int item) {
        if (this.dataStack.size() == 0) {
            this.minStack.push(item);
        } else {
            this.minStack.push(item < this.minStack.peek() ? item : this.minStack.peek());
        }
        this.dataStack.push(item);

    }

    public Integer pop() {
        if (!this.dataStack.isEmpty()) {
            this.minStack.pop();
            return this.dataStack.pop();
        } else {
            System.out.println("     ，       ！");
            return -999999;
        }
    }

    public Integer getMin() {
        if (this.minStack.size() > 0) {
            return this.minStack.peek();
        }
        System.out.println("          ！");
        return null;
    }

}

class NotOverrideMaxStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> maxStack;

    public NotOverrideMaxStack() {
        this.dataStack = new Stack<Integer>();
        this.maxStack = new Stack<Integer>();
    }

    public void push(Integer item) {
        if (this.dataStack.size() == 0) {
            this.maxStack.push(item);
        } else {
            // this.maxStack.push(this.maxStack.peek() > item ?
            // this.maxStack.peek() : item);
            if (this.maxStack.peek() < item) {
                this.maxStack.push(item);
            }
        }
        this.dataStack.push(item);
    }

    public Integer pop() {
        if (!this.maxStack.isEmpty()) {
            if (this.maxStack.peek() == this.dataStack.peek()) {
                this.maxStack.pop();
            }
            return this.dataStack.pop();
        }
        return null;
    }

    public Integer getMax() {
        return this.maxStack.peek();
    }
}

class OverrideMaxStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> maxStack;

    public OverrideMaxStack() {
        this.dataStack = new Stack<Integer>();
        this.maxStack = new Stack<Integer>();
    }

    public void push(Integer item) {
        if (this.dataStack.size() == 0) {
            this.maxStack.push(item);
        } else {
            this.maxStack.push(this.maxStack.peek() >= item ? this.maxStack.peek() : item);
        }
        this.dataStack.push(item);
    }

    public Integer pop() {
        if (!this.dataStack.isEmpty()) {
            this.maxStack.pop();
            return this.dataStack.pop();
        }
        return null;
    }

    public Integer getMax() {
        return this.maxStack.peek();
    }
}

수확 과 계시
이로써 증강 형 스 택 디자인 이 완성 되 었 다.그 중에서 작가 가 두 개의 창 고 를 사용 하여 시간의 복잡 도 를 줄 이 는 교묘 한 사고방식 은 정말 사람 에 게 일종 의 미감 을 준다.
그렇다면 이런 사고방식 을 어디 까지 활용 할 수 있 을 까?
나 는 이것 이 문제 의 통용 해법 이 될 수 있다 고 생각한다. 많은 경우 에 우리 의 사 고 는 한 가지 점 에서 경직 되 고 오랫동안 노력 했 지만 돌파 가 별로 없다.이 럴 때 는 작가 처럼 생각 을 바 꿔 도 무방 하 다.다른 '대가' 를 희생 하면 다른 수확 이 있 을 지도 모른다.
소프트웨어 개발 과정 에서 도 마찬가지 입 니 다. 한 프로젝트 를 완성 하 는 것 은 나무 에 목 을 매 죽 어야 한 다 는 것 이 아 닙 니 다. 현재 로 서 는 하나의 기능 을 완성 하 는 데 많은 언어 가 있 거나 같은 언어의 다른 방법 으로 이 루어 집 니 다. 사고 가 초점 을 맞 추 는 곳 이 돌파 점 이 없 을 때 다른 방향 을 고려 해 야 합 니 다.
이것 도 본 사례 의 '더 블 스 택 으로 스 택 을 강화 하 자' 는 포장 모델 의 좋 은 표현 이다.