Java 스택 및 큐를 소개하는 기사-java지도 시간-php.cn

이 글은 java에 대한 관련 지식을 제공합니다. 스택과 큐의 정의, 적용, 구현 및 작동을 포함하여 스택과 큐와 관련된 문제를 주로 정리합니다. 모두에게 도움이 되기를 바랍니다.

Java 스택 및 큐를 소개하는 기사

스택과 큐를 배우기 전에 먼저 선형 테이블이 무엇인지 이해하세요. 동일한 유형의 단일 요소를 한 번에 저장하고 여러 요소가 논리적으로 연속적입니다. 배열, 연결 목록, 문자열, 스택 및 큐와 같은
스택과 큐는 실제로 제한된 작업을 수행하는 선형 목록입니다. 배열이든 연결 목록이든 머리나 꼬리에 삽입하고 삭제할 수 있지만 스택과 큐만 가능합니다. 한쪽 끝에 삽입하고 한쪽 끝에서 삭제

1. 스택

1. 정의

요소는 한쪽 끝에서만 삽입할 수 있고, 요소는 이 끝(스택의 맨 위)에서만 삭제할 수 있다고 생각하면 됩니다. 요소는 한쪽 끝에서만 추가할 수 있고 한 부분에서만 요소를 삭제할 수 있습니다. 또한 물컵에 먼저 들어가는 물은 컵 바닥에 있고 물은 한쪽 끝에서만 가능합니다. 나중에 물컵에 들어가는 것은 컵 꼭대기에 있습니다. 물이 쏟아지면 컵 꼭대기의 물도 쏟아집니다. 스택에 밀어 넣는 요소도 마찬가지입니다. 첫 번째 요소는 스택의 맨 아래에 있고, 나중에 스택에 푸시된 요소는 스택의 맨 위에 있습니다. 따라서 먼저 스택에 푸시된 요소는 마지막으로 꺼내지고, 스택에 푸시된 요소는 스택에 추가됩니다. 마지막에 있는 스택이 먼저 꺼집니다. 이는 스택의 특성이기도 합니다. "선입선출, 후입선출" "LIFO(Last In First Out), 제거된 요소와 추가된 요소는 스택의 맨 위에만 있을 수 있습니다. 스택.
1 2 3 4 5를 한 번에 스택에 넣습니다
Java 스택 및 큐를 소개하는 기사

2. 스택 응용 프로그램

1. 어디서나 실행 취소(실행 취소) 작업

편집기에서 잘못된 내용을 입력한 후 Ctrl + z를 누르면 입력으로 돌아갑니다.
어떤 브라우저에서든 뒤로 작업을 클릭하면
Java 스택 및 큐를 소개하는 기사
이 스택 구조가 적용됩니다
1. 편집기를 사용하여 실행 취소 작업을 사용하고, 입력한 후 내용을 스택에 푸시하고, 다시 입력하려면 푸시합니다. 입력 오류가 발견되면 실행 취소 작업을 사용하여 현재 스택 상단에 오류 내용을 표시합니다. 그러면 현재 스택 상단에 있는 내용이 마지막 입력 내용이 됩니다.
2. 실제로 웹 탐색은 Baidu 열기 -> csdn 열기 -> 스택 구조를 사용하는 생성 센터 열기와 동일한 원리로 이루어집니다. 먼저 Baidu 웹 페이지를 스택에 푸시한 다음 csdn 웹 페이지가 스택에 푸시됩니다. csdn 홈 페이지로 돌아가려면 뒤로 화살표를 눌러 현재 스택 상단에 있는 생성 센터 웹 페이지를 팝업으로 표시합니다. csdn 홈페이지를 꺼내세요.

2. 운영체제 스택

프로그램이 실행되는 동안 함수 B는 함수 A에서 호출되고, 함수 C는 함수 B에서 호출됩니다. 호출이 끝나고 실행으로 돌아갈 때 어디에서 계속 실행해야 할지 어떻게 알 수 있나요? ? 그 뒤에도 스택이 있습니다 이 구조

3. 스택 구현

연결된 목록을 기반으로 구현된 스택 – 체인 스택
배열 기반으로 구현된 스택 – 순차 스택(더 일반적으로 사용됨)
동적 배열을 기반으로 구현된 스택을 정의합니다.

//基于动态数组实现的顺序栈public class MyStack<e> {
    //记录当前栈的元素个数
    private int size;
    //实际存储数据的动态数组，此时在栈中只能在数组的尾部添加和删除元素
    private List<e> data = new ArrayList();
    }</e></e>

로그인 후 복사

4. 스택 작업

1. 스택에 요소 추가
스택 상단에만 추가할 수 있습니다

 /**
     * 向当前栈中添加元素 -- >压栈操作
     * @param val
     */
    public void push(E val){
        data.add(val);
        size++;
    }

로그인 후 복사

2. 현재 스택 상단에서 요소를 팝합니다. 스택의 현재 최상위 요소이지만 팝하지는 마세요

/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @return
     */
    public E pop(){
        if (isEmpty()){
            //栈为空无法弹出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //在数组末尾删除元素
        E val = data.get(size - 1);
        data.remove(size - 1);
        size --;
        return val;
    }

로그인 후 복사

2. 대기열

1. 정의

큐: FIFO(선입선출) 데이터 구조 i. 요소는 대기열에만 추가할 수 있습니다. 대기열의 끝에서만 대기열에서 제거할 수 있으며 대기열에서 제거하는 순서와 요소의 항목 순서는 일관되게 유지됩니다.

1 2 3 4 5를 순서대로 대기열에 넣습니다

Java 스택 및 큐를 소개하는 기사 응용

실생활에서 다양한 "큐잉" 작업

3. 큐 구현

배열 구현 기반 큐 – 순차 큐

연결 리스트 기반 큐 구현 – 체인 큐

큐 제거 작업은 헤드에서만 수행 가능 배열로 구현된 큐를 사용하는 경우 요소가 대기열에서 제거될 때마다 나머지 요소를 모두 앞으로 이동해야 합니다. 단위, 이 경우 연결 목록으로 구현된 큐가 더 적합합니다. 요소를 삭제하려면 헤드 노드만 삭제하면 됩니다. 요소를 추가하려면 연결 목록 끝에

/**
     * 查看当前栈顶元素值，不弹出该元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size - 1);
    }

로그인 후 복사

를 추가하세요. 스택의 경우 FIFO 대기열

과 같은 대기열 구현의 하위 클래스가 많이 있습니다. 이중 종료 대기열
순환 대기열
우선 순위 대기열
어떤 대기열을 구현해야 합니까? 4. FIFO 대기열

1. 대기열에 요소를 추가합니다

public interface Queue<e> {
    //入队操作
    void offer(E val);
    //出队操作
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();}</e>

로그인 후 복사

3. 현재 대기열의 헤드 요소

// An highlighted blockvar foo = 'bar';

로그인 후 복사

4. 현재 대기열의 헤드 요소 보기

public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }

로그인 후 복사

5.循环队列

1.定义：基本上都是使用固定长度的数组来实现，数组在实现队时，若从数组头部删除元素需要频繁的移动后面的元素，效率比较低；出队和入队操作，使用两个引用，一个head，一个tail,添加元素在数组的尾部添加，删除元素只需要移动head引用指向的地址即可（逻辑删除）
2.应用：操作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎的redo日志
3.循环队列就是使用长度固定的数组来实现，数组头部就是队首（head），数组的尾部就是队尾（tail），数组[head…tail)时循环队列的有效元素
head永远指向循环队列的第一个元素
tai永远指向循环队列有效元素的后一个位置
Java 스택 및 큐를 소개하는 기사
此时循环队列的有效元素就为7 9 1两个元素
循环队列出队一个元素，就只用让head引用向后移动一个位置

此时循环队列的有效元素就只有9 和 1 两个元素了
再出队一个元素，但此时head引用已经走到末尾了，所谓循环队列就是当head或者tail引用走到数组末尾时，再向后移动就是返回数组头部的操作，循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作，当有新的元素添加到队列中就会覆盖掉原来的元素，就只需要将tail索引位置覆盖上新的元素，再让tail再向后移动

当队列为空时,head == tail

Java 스택 및 큐를 소개하는 기사

当队列已“满”时，head == tail

Java 스택 및 큐를 소개하는 기사
循环队列需要注意的关键点
1.因此当head 和 tail相等时，没法区分此时循环队列已满，还是为空，因此在循环队列中，若(tail + 1) % n == head就认为循环队列已满

此时循环队列就已经满了，在循环队列中就会浪费一个空间，判断队列是否已满
2.head和tail的移动不能简单的 + 1，使用取模操作，取数组长度
tail = (tail + 1) % n
head = (head + 1) % n
对数组长度取模的本质：
当head和tai走到数组最后一个索引位置时，下一次要返回数组头部，就必须用 + 1对数组长度取模
3.head == tail时，认为队列为空

6.循环队列的操作

1.定义一个循环队列

//基于整形的循环队列public class LoopQueue implements Queue<integer> {
    //定长数组
    private Integer[] data;
    //指向队首元素
    int head;
    //指向队尾元素的下一个元素
    int tail;
    public LoopQueue(int size){
        data = new Integer[size + 1];
    }}</integer>

로그인 후 복사

2.向循环队列中添加一个元素

@Override    public void offer(Integer val) {
       if (isFull()){
           throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
       }
       data[tail] = val;
       tail = (tail + 1) % data.length;
    }

로그인 후 복사

3.从循环队列中出队一个元素

 @Override    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }

로그인 후 복사

4.查看当前循环队列队首元素

 @Override    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek!");
        }
        return data[head];
    }

로그인 후 복사

5.判断当前循环队列是否为空

 @Override    public boolean isEmpty() {
        return head == tail;
    }

로그인 후 복사

6.判断当前循环队列是否已满

 public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

로그인 후 복사

7.toString方法

public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最后一个有效元素的索引
        int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lsatIndex){
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }

로그인 후 복사