Заблуждения о стековых инструментах

Question

Первый код только две строки.

input = "hkiehs nimala"
print(input[::-1])

вывод alamin sheikh

вот другой код, но вывод такой же, как.

class Stack():
def __init__(self):
    self.items = []

def push(self, item):
    self.items.append(item)             

def pop(self):
    return self.items.pop()

def is_empty(self):
    return self.items == []

def peek(self):
    if not self.is_empty():
        return self.items[-1]
    
def get_stack(self):
    return self.items

def reverse_string(stack, input_str):
  for i in range(len(input_str)):
    stack.push(input_str[i])
    rev_str = ""
 while not stack.is_empty():
   rev_str += stack.pop()

   return rev_str

stack = Stack()
input_str = "alamin sheikh"
print(reverse_string(stack, input_str))

вывод также: такой же, как и первый код Но почему? Как здесь работает стек!

Спасибо.

Answer 1

Попробуйте это в качестве эксперимента: возьмите четыре вещи, которые вы можете складывать, например четыре разные монеты. Выровняйте их слева направо. Двигаясь слева направо, складывайте их по одной (так, чтобы самая левая монета была внизу стопки, а следующая за ней - вверху, et c). Теперь снимите их со стека и разложите слева направо, так что первое, что вы снимаете со стека, находится слева, а второе, что вы снимаете со стека, находится рядом с ним, et c. Presto - они расположены в обратном порядке по сравнению с тем, как они начинались!

Структура данных «стек» работает точно так же, поэтому она называется «стек». Каждый раз, когда вы кладете что-то в стопку, она оказывается наверху, поэтому, если вы поместите буквы A, B, C и D в стопку в указанном порядке, они получат go в этом порядке. порядок снизу вверх, с буквой D наверху:

            ->D
        ->C   C
    ->B   B   B
->A   A   A   A

Когда вы «выталкиваете» стопку, вы снимаете самый верхний элемент. Если вы вытащите каждый элемент из этого стека и добавите каждый в строку, вот что произойдет:

   "" + "D"<-D
             C
             B
             A


  "D" + "C"<-C
             B
             A


 "DC" + "B"<-B
             A


"DCB" + "A"<-A

поэтому в конце строка находится в порядке, обратном тому, в котором она начиналась, как и ваш четыре монеты!

Другое название этого типа структуры - «первым пришел, последний ушел» (FILO) - первое, что вы кладете в него, это последнее, что вы из него вынимаете, а именно как вы закончите с вещами в обратном порядке, если вы положите кучу вещей, а затем вытащите все.

Answer 2

Два обозначенных вами подхода исходят с принципиально разных точек зрения. Первый подход, использующий индексирование и нарезку списков, - это способ Pythoni c работы с итерациями, такими как списки, строки, кортежи или генераторы. В этом случае данные сохраняются в виде строки ("alamin sheikh") и возвращаются в обратном порядке через [::-1]. Из документации Python :

>>> L = range(10)
>>> L[::2] # every other element
[0, 2, 4, 6, 8]
>>> L[::-1] # reverse list
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> s='abcd'
>>> s[::2] # every other character
'ac'
>>> s[::-1] # reverse string
'dcba'

Второй подход использует структуру данных stack для хранения элементов. Интуитивно понятный способ понять стопки - это буквально представить стопку книг. Когда есть стопка книг, книги в верхней части стопки будут теми, которые были размещены последними; внизу будет книга, которая некоторое время лежала в стопке go. В терминах CS это называется LIFO или «Последний вошел, первый вышел».

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

Мы можем разобрать, что делает reverse_string, как следует:

• Сохранить input_str в объекте stack, переданном в качестве аргумента функции
• Вставлять элементы из stack до тех пор, пока stack не станет пустым

Давайте go рассмотрим пример с input_str = "alamin sheikh". Во-первых, в части кода for l oop мы перебираем входную строку и pu sh каждый символ в стеке. Когда мы закончим выталкивание, вот как будет выглядеть содержимое объекта stack.

["a", "l", "a", "m", "i", "n", " ", "s", "h", "e", "i", "k", "h"]

Теперь мы переходим к шагу 2, где мы выталкиваем элементы из стека. Напомним, что стеки придерживаются структуры LIFO. В этом случае последний символ, "h", был последним элементом, помещенным в стек. Следовательно, это будет первый элемент, который выскочит из списка.

# after first pop
rev_str = "h"
["a", "l", "a", "m", "i", "n", " ", "s", "h", "e", "i", "k"]

Если мы продолжим эти шаги для остальных элементов в stack, мы в конечном итоге получим перевернутую строку.

Answer 3

Стек работает по принципу LIFO (последний пришел первым), если вы хотите представить его, то это как колода карт, лежащая на столе, первая вставленная вами карта будет последней Один в позиции (самое нижнее) !!

Теперь, объясняя код, здесь, как вы можете видеть в своей программе стека, вы сначала l oop по всей строке и добавляете каждый символ в стек, поэтому сначала сначала добавляется символ, затем второй, затем третий ... вот так, когда стек завершается, вы получаете последний символ на самом верху точки!

Графически все ваши операции похожи на: Stack Ops

Затем вы выглядываете из-за стопки и берете ее самые верхние элементы, следовательно, перевернутая форма строки! Надеюсь, вы поняли, если есть какие-то сомнения, напишите в комментариях :)