Эта статья приняла участие"Проект "Звезда раскопок"", чтобы выиграть творческий подарочный пакет и бросить вызов творческим поощрительным деньгам

«Добро пожаловать для обсуждения в области комментариев, официальный представитель NuggetsПроект «Звезда раскопок»После мероприятия в комментариях будет разыграно 100 штук Наггетсов.Подробнее о лотерее читайте в статье о мероприятии».

Введение

Стек должен быть очень простой и очень полезной структурой данных. Характеристики стека: FIFO или LIFO.

По сути, структура многих виртуальных машин представляет собой стек. Потому что стек очень эффективен при реализации вызовов функций.

Сегодня давайте посмотрим на структуру и использование стека.

Состав стека

Стек — это упорядоченный линейный список, который можно вставлять или удалять только с одного конца. Этот конец называется верхним концом.

Чтобы определить стек, нам нужно реализовать две функции: одну — push, то есть складывание, и другую — pop, то есть извлечение.

Конечно, мы также можем определить некоторые другие вспомогательные функции, такие как top: получение самого верхнего узла в стеке. isEmpty: определяет, пуст ли стек. isFull: определяет, заполнен стек или нет.

Сначала посмотрите на анимацию стека:

Взгляните на поп-анимацию:

Реализация стека

Как реализован стек с такой функцией?

В общем случае стеки могут быть реализованы с помощью массивов или связанных списков.

Реализация стеков с использованием массивов

Если стек реализован с использованием массива, мы можем использовать последний узел массива в качестве головы стека. Таким образом, когда выполняются операции push и pop stack, необходимо изменить только последний узел в массиве.

Нам также нужен topIndex для хранения позиции последнего узла.

Код реализации выглядит следующим образом:

public class ArrayStack {

    //实际存储数据的数组
    private int[] array;
    //stack的容量
    private int capacity;
    //stack头部指针的位置
    private int topIndex;

    public ArrayStack(int capacity){
        this.capacity= capacity;
        array = new int[capacity];
        //默认情况下topIndex是-1，表示stack是空
        topIndex=-1;
    }

    /**
     * stack 是否为空
     * @return
     */
    public boolean isEmpty(){
        return topIndex == -1;
    }

    /**
     * stack 是否满了
     * @return
     */
    public boolean isFull(){
        return topIndex == array.length -1 ;
    }

    public void push(int data){
        if(isFull()){
            System.out.println("Stack已经满了，禁止插入");
        }else{
            array[++topIndex]=data;
        }
    }

    public int pop(){
        if(isEmpty()){
            System.out.println("Stack是空的");
            return -1;
        }else{
            return array[topIndex--];
        }
    }
}

Используйте динамические массивы для реализации стеков

В приведенном выше примере размер нашего массива фиксирован. То есть стек имеет ограниченную емкость.

Что, если мы хотим построить бесконечный стек?

Это очень просто: при проталкивании, если стек заполнен, мы можем расширить базовый массив.

Код реализации выглядит следующим образом:

public void push(int data){
        if(isFull()){
            System.out.println("Stack已经满了，stack扩容");
            expandStack();
        }
        array[++topIndex]=data;
    }

    //扩容stack，这里我们简单的使用倍增方式
    private void expandStack(){
        int[] expandedArray = new int[capacity* 2];
        System.arraycopy(array,0, expandedArray,0, capacity);
        capacity= capacity*2;
        array= expandedArray;
    }

Конечно, есть много способов расширить массив, здесь мы выбираем метод умножения.

Реализовано с использованием связанного списка

Вместо использования массивов мы также можем использовать связанные списки для создания стеков.

При использовании связанного списка нам нужно работать только с головным узлом связанного списка. И вставки, и удаления обрабатываются головными узлами.

public class LinkedListStack {

    private Node headNode;

    class Node {
        int data;
        Node next;
        //Node的构造函数
        Node(int d) {
            data = d;
        }
    }

    public void push(int data){
        if(headNode == null){
            headNode= new Node(data);
        }else{
            Node newNode= new Node(data);
            newNode.next= headNode;
            headNode= newNode;
        }
    }

    public int top(){
        if(headNode ==null){
            return -1;
        }else{
            return headNode.data;
        }
    }

    public int pop(){
        if(headNode ==null){
            System.out.println("Stack是空的");
            return -1;
        }else{
            int data= headNode.data;
            headNode= headNode.next;
            return data;
        }
    }

    public boolean isEmpty(){
        return headNode==null;
    }
}

Кодовый адрес этой статьи:

learn-algorithm

Эта статья была включена вWoohoo. Флойд press.com/10-муж или IT и…

Самая популярная интерпретация, самая глубокая галантерея, самые краткие уроки и множество трюков, о которых вы не знаете, ждут вас!

Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: «Программируйте эти вещи», разбирайтесь в технологиях, лучше поймите себя!