CODEWITHSUNDEEP
pythonstack
Alamin Sheikh
Alamin Sheikh

Reputation: 35

Confusions about stack implements

There are first code only two lines.

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

output is alamin sheikh

here is another code but output also same as .

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))

output also: same as first code But why ? How do work stack here !

Thank you.

Upvotes: 0

Views: 156

Answers (3)

Jake Tae
Jake Tae

Reputation: 1741

The two approaches you outlined are coming from fundamentally different angles. The first approach, using list indexing and slicing, is the Pythonic way of dealing with iterables, such as lists, strings, tuples, or generators. In this case, the data is stored as a string ("alamin sheikh"), and returned in reverse order via [::-1]. From the Python documentation:

>>> 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'

The second approach uses the stack data structure to store elements. An intuitive way to understand stacks is to literally think of a stack of books. When there is a pile of books, the books at the top of the pile will be the ones that were placed the most recently; the one on the bottom will be a book that was placed in the pile a while ago. In CS terms, this is referred to as LIFO, or "Last one in, first one out."

The provided source code is a Python implementation of the stack data structure, implemented with lists. Since your question seems to specifically ask on how the reverse_string function works with the instance of the Stack class, I'll zoom in on this aspect.

We can break down what reverse_string does as follows:

  • Store input_str in the stack object passed as an argument to the function
  • Pop elements from the stack until the stack is empty

Let's go through an example with input_str = "alamin sheikh". First, in the for loop portion of the code, we iterate through the input string and push each character to the stack. When we are done pushing, this is what the contents of the stack object will look like.

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

Now we move onto step 2, where we pop elements out of the stack. Recall that stacks adhere to a LIFO structure. In this case, the last character, "h", was the last element that was pushed into the stack. Therefore, it will be the first one being popped off the list.

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

If we continue these steps for the rest of the elements in the stack, we will eventually end up with the reversed string.

Upvotes: 1

Samwise
Samwise

Reputation: 71424

Try this as an experiment: take four things that you can stack, like four different coins. Line them up in order from left to right. Going from left to right, stack them up one by one (so the leftmost coin is on the bottom of the stack, the coin after that goes on top, etc). Now take them off the stack and lay them out from left to right, so the first thing you take off the stack is on the left, the second thing you take off the stack is right next to that, etc. Presto -- they're in the opposite order from how they started!

A "stack" data structure works exactly the same way, which is why it's called a "stack". Every time you put something on a stack, it goes on the top, so if you place the letters A, B, C, and D on a stack in that order, they go in that order from bottom to top, with D on top:

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

When you "pop" a stack, you take the topmost item off. If you pop each element off that stack, and add each one to a string, here's what happens:

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


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


 "DC" + "B"<-B
             A


"DCB" + "A"<-A

so at the end, the string is in the reverse order from how it started, just like your four coins!

Another name for this type of structure is "first in, last out" (FILO) -- the first thing you put into it is the last thing you'll take out of it, which is how you end up with things in reverse order if you put a bunch of stuff in and then take it all out.

Upvotes: 1

Agent_Orange
Agent_Orange

Reputation: 351

Stack Works On Principle Of LIFO (Last In First Out), If You Want To Imagine It Then Its Like A Deck Of Cards Lying On A Table, The First Card You Insert There Will Be The Last One In Position (At Most Bottom)!!

Now explaining the code, here as you can see in your stack program, you first loop over the full string and add each character to stack, so first character is added first, then second, then third... like this when stack completes, you get last character on top most point!

Graphically All Your Operations Are Like: Stack Ops

Then you peek over the stack and pickup its top most elements, hence reversed form of string! Hope you understood, if theres any concern, write down in comments :)

Upvotes: 1

Related Questions