Здравствуйте, все. В сегодняшнем блоге мы увидим, что такое структуры данных и какие существуют типы структур данных, а в блоге мы сосредоточимся на стеке. Итак, начнем.
Во-первых, мы увидим, что такое структуры данных.
Структуры данных являются одним из основных компонентов факультета информатики. Структуры данных помогают вам решить данную проблему эффективным способом и помогают лучше думать о решении проблемы.
Типы структур данных: –
Линейные структуры данных: –
Линейная структура данных имеет элементы данных, связанные друг с другом таким образом, что элементы расположены последовательно, и каждый элемент связан с элементом перед ним и за ним. Таким образом, структуру можно обойти за один проход.
Нелинейные структуры данных: –
Структуры данных, в которых элементы данных расположены не последовательно или линейно, называются нелинейными структурами данных. В нелинейной структуре данных один уровень не задействован. Следовательно, мы не можем обойти все элементы только за один проход.
Теперь давайте погрузимся в первый тип линейной структуры данных.
(i) Стек
Стек — это список LIFO, что означает, что он работает по принципу «последним пришел — первым вышел». Означает, что элемент, который находится на вершине стека, является первым элементом, удаляемым из стека.
В стеке вставка элемента называется Push, а удаление элемента называется Pop. В структурах данных «Стек», «Очередь» и «Связанный список» являются «Абстрактными типами данных». .
Теперь давайте посмотрим, что такое Абстрактные типы данных.
Абстрактные типы данных просто показывают, какие типы операций реализуются в типе данных, но как реализовать, не является частью определения.
Реализация стеков двух типов в обзоре языка программирования C.
Мы также можем сказать, что стек — это список с указателем, известным как «Вершина стека». Каждая операция в стеке выполняется на вершине стека.
Теперь давайте углубимся в реализацию стека с помощью массива.
Реализация стека в массиве: -
Всякий раз, когда есть операция Push, мы увеличиваем Top. Всякий раз, когда есть операция Pop, мы уменьшаем вершину.
Сложность isFull() равна O(1).
Переполнение стека. Когда наш стек заполнен, и мы также хотим отправить элемент в стек, возникает состояние, известное как «Переполнение стека».
Сложность isEmpty() равна O(1).
Стек поддерживает четыре типа функций:
(i) Полный
(ii) Пусто
(iii) Толчок
(iv)Поп
(v) Пеп
Операция добавления и извлечения в стеке –
Теперь мы увидим некоторые вопросы, связанные со стеком.
Вопрос-1. Можете ли вы найти элемент, который находится внизу стека?
Ответ-1 Да, можно сказать, что мы реализуем стек с помощью массива. Но на практике это невозможно, потому что стек поддерживает только пять операций.
Вопрос-2. Если мы реализуем стек с помощью массива так, что вершина всегда находится в нулевом индексе? В чем сложность Push и Pop, чем ?
Ответ -2 Давайте рассмотрим пример, чтобы понять этот вопрос.
Если Top находится в нулевом индексе, нам всегда нужно сдвигать элементы перед помещением элементов в стек. Например, у нас есть элементы 10 и 20 в стеке, и теперь мы хотим отправить 30 в стек, поэтому перед отправкой 30 нам нужно сначала сдвинуть 10 и 20.
Итак, в этих условиях сложность Толка и Попа становится -
Толкать
Лучший случай = O(1) — — → Когда стек пуст
Наихудший случай = O(n) — — —› Нам нужно пройти через стек.
Поп
Лучший случай = O(1) — — → мы получаем элемент только на вершине стека
Наихудший случай = O(n) — — —› Нам нужно пройти через стек.
Вот и все, что касается этого блога, в следующем блоге мы увидим применение стека. Спасибо, что читаете мой блог, увидимся в следующем блоге.
