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

Question

У меня недавно был урок в структуре данных, и первое, чему учили, - это реализовать стек в массиве. Я мог понять, как была выполнена реализация стека, но я не понимаю, почему это делается. Я имею в виду, что массивы более полезны и практичны и гибки по сравнению со стеками. Я не могу сказать ничего о преимуществах стека по сравнению с массивами, которые приводят к необходимости создания стека из массива. Можете ли вы помочь мне понять мои идеи об этой концепции?

Answer 1

Я думаю, вы путаете основные преимущества стека и массива. Стек может быть реализован через массив, но на самом базовом уровне массив - это инструмент, а стек - это способ, которым вы можете использовать этот инструмент в своих интересах.

Другими словами, массив может использовать для реализации стека, но подумайте о массиве как инструменте для хранения данных. Вы можете использовать массив для реализации кучи, стека или даже очереди - все дело в том, как вы используете массив для выполнения конкретной задачи.

Важно то, что вы узнаете, когда вам нужно использовать стек, кучу, очередь и т. Д., А также то, что «инструменты» (массив, связанный список и т. Д.) Вы имеете в своем распоряжении для реализации таких данных структур.

Answer 2

Концептуально вы используете операции Push и Pop на стеке: вы нажимаете на стек и выталкиваете стек. Стек отслеживает порядок поступления элементов, последний из которых является первым (LIFO). Вы работаете только с элементом в верхней части стека, либо выталкиваете верхний элемент из стека, либо нажимаете на него новый элемент. Если один компонент подталкивает 4 вещи в стек, другой компонент может вытащить их из стека и знает порядок, который использовался компонентом «pushing».

Обычно вы используете массив путем либо итерации через каждый член списка, либо путем доступа к элементу в любом месте массива индексом. Обычно вы используете массив, когда вам действительно не нужен порядок LIFO, вы просто хотите получить доступ к любому элементу для какой-либо другой цели или хотите выполнить операцию над каждым элементом и не заботитесь о порядке LIFO.

Answer 3

Если мы хотим понять, почему существует абстракция программирования, ответ не заключается в объяснении его деталей реализации (как и Джонс в своих ответах). Вам нужно искать аналогии в реальном мире, после чего мы что-то смоделировали. Существует так много. Стеки вокруг нас.

• держатель монет в машине
• пластины Ikea тележки
• 9 мм пистолет
• сложенных товаров в магазинах по всему миру (Thats, вероятно, наиболее распространенным стеком в человеческом мире)
• и т.д. ..

Вы говорите о преимуществе стека над массивом. Его преимущество заключается в том, что это подходит для целей, когда бизнес-логика моделирует проблему реального мира, которая представляет собой стек.

Answer 4

Я могу предоставить вам Java версию того же: /** * */ пакет com.base.stack;

/** * @author kamals1986 * Данные, которые поступают в стек. */ общественного класса Item {

int value; 

public Item(int value) { 
    this.value = value; 
} 

@Override 
public String toString() { 
    return "Item [value=" + value + "]"; 
} 

}

Фактический класс в настоящее время:

упаковка com.base.stack;

импорт java.util.Arrays;

/** * @author kamals1986 * */ общественного класса MyStack {

private static int INITIAL_SIZE = 5; 
protected Item[] items = new Item[INITIAL_SIZE]; 
int top = -1; 

@Override 
public String toString() { 
    return "MyStack [items=" + Arrays.toString(items) + "]\n"; 
} 

public void push(Item i) { 
    if (top == -1 || stackNotFull()) { 
     System.out.println("Not resizing"); 
     top = top + 1; 
     items[top] = i; 
    } else { 
     System.out.println("Stack is full , I am resizing it by 2 more"); 
     int newCapacity = items.length + 2; 
     top = items.length - 1; 
     items = Arrays.copyOf(items, newCapacity); 
     top++; 
     items[top] = i; 
    } 
} 

public void displayContents() { 
    System.out.println(this); 

} 

public Item pop() { 
    if (top == -1) { 
     throw new RuntimeException("Stack is empty"); 
    } else { 
     Item i = items[top]; 
     items[top] = null; 
     top--; 
     return i; 
    } 
} 

private boolean stackNotFull() { 
    return top < items.length - 1; 
} 

}