Trying to build a Stack Algoritm using an array

Question

I'm trying to do this but it is always wrong. I don't understand how Am I supose to do this... This is my code:

class WrongStack:
def __init__(self):        
    self.__items = numpy.array([])

def push(self, item): 
    numpy.concatenate(self.__items,item)

def pop(self):  
    return numpy.delete(self.__items,0,-1)

def peek(self):  
    return self.__items[len(self.__list) - 1]

def is_empty(self):            
    return len(self.__items) == 0

def size(self):                 
    return len(self.__items)


s = WrongStack()
number = input('Choose a number, 0 to finish')
while number != '0':
  s.push(numpy.array([nmr]))
  number = input('Choose a number, 0 to finish')
while not s.is_empty():
  number = s.pop()
  print(number)

The error is:

File "C:/Users/JJ/OneDrive - ISCTE-IUL/EDA/Aula 4.py", line 55, in <module>
s.push(numpy.array([nmr]))

File "C:/Users/JJ/OneDrive - ISCTE-IUL/EDA/Aula 4.py", line 38, in push
numpy.concatenate(self.__items,item)

File "<__array_function__ internals>", line 6, in concatenate
TypeError: only integer scalar arrays can be converted to a scalar index

I know this is not how to build a normal stack but I have to do this in this way.

Is there a reason you're using numpy array rather than a simple list? — DarrylG, Mar 20 '20 at 15:51
@DarrylG This is an exercise from my Data Structures and Algoritms class. I think the main goal,after implementing this algoritm, is to say if it has a good performance in comparance with the normal stack algoritm (using a list). — João Júlio, Mar 20 '20 at 15:57
I'm afraid for this purpose the performance will probably be worse than using a list. Numpy has overhead, but its worthwhile when there are computations on large amounts of data. It will probably be slower for your simple usage. — DarrylG, Mar 20 '20 at 16:02

DarrylG · Answer 1 · 2020-03-21T10:24:59.350

Made mods to your code to get it to work.

Placed 'Mod' at places where I changed the code.

Code

import numpy as np

class WrongStack:
  def __init__(self):        
      self.__items = np.array([])

  def push(self, item): 
      # Mod--concatenate takes list contains items to concatenate
      self.__items = np.concatenate([self.__items,item])

  def pop(self):  
      # Mod--np.delete returns a new array
            # also retrieve last element before delete
      last = self.__items[-1]
      self.__items = np.delete(self.__items,-1, 0)
      return last

  def peek(self):  
      return self.__items[len(self.__list) - 1]

  def is_empty(self): 
      # Mod--use function size    
      return self.size() == 0

  def size(self):                 
      return len(self.__items)

  def __str__(self):
    # Mod--added for display the array
    return str(self.__items)

s = WrongStack()
number = input('Choose a number, 0 to finish: ')
while len(number) > 0 and number != '0': #Mod done if no input or '0' entered
  # Mod--convert numer to integer
  s.push(np.array([number], dtype=np.int32)) # specify type (i.e. int32)
  number = input('Choose a number, 0 to finish: ')

# Mod--print array created
print('Array created:', s)

while not s.is_empty():
  number = s.pop()
  print('number: ', number)

Test

Choose a number, 0 to finish: 1
Choose a number, 0 to finish: 2
Choose a number, 0 to finish: 3
Choose a number, 0 to finish: 4
Choose a number, 0 to finish: 5
Choose a number, 0 to finish: 0
Array created: [1. 2. 3. 4. 5.]
number:  5.0
number:  4.0
number:  3.0
number:  2.0
number:  1.0

Alternative

Relies on Numpy fixed size array. Uses slices and range checking to insure we stay within allocated size.

import numpy as np

class WrongStack:
  def __init__(self, maxlen=100):        
      self.__items = np.array([0]*maxlen) # Fixed size Numpy array
      self._count = 0
      self._maxlen = maxlen

  def push(self, item): 
      # Mod--concatenate takes list contains items to concatenate
      if self._count < self._maxlen:
        self.__items[self._count] = item
        self._count += 1
      else:
        print('push: no more space')


  def pop(self):  
      # Mod--np.delete returns a new array
            # also retrieve last element before delete
      if self._count > 0:
        last = self.__items[self._count-1]
        self._count -= 1
        return last
      else:
        return None

  def peek(self):
      if self._count > 0:
        return self.__items[self._count-1]
      else:
        return None

  def is_empty(self): 
      # Mod--use function size    
      return self.size() == 0

  def size(self):                 
      return self._count

  def __str__(self):
    # Mod--added for display the array
    return str(self.__items[:self._count])

s = WrongStack(10) # will handle stack with up to 10 elements
number = input('Choose a number, 0 to finish: ')
while len(number) > 0 and number != '0': #Mod done if no input or '0' entered
  # Mod--convert numer to integer
  s.push(number) # specify type (i.e. int32)
  number = input('Choose a number, 0 to finish: ')

# Mod--print array created
print('Array created:', s)

while not s.is_empty():
  number = s.pop()
  print('number: ', number)

I have at least one question. In the pop function, when you write: `self.__items = np.delete(self.__items,-1, 0)`, does this creates a new array without the element that you delete or is changes the original array? I hope you understand what I'm trying to say. And does the original array becomes empty after: `while not s.is_empty(): number = s.pop() print('number: ', number)` ??? — João Júlio, Mar 20 '20 at 17:41
@DarryIG is giving me the same error as before. I don't understand why... And can you respond to the comment above please? I forgot to tag you in that comment. This is the error: `File "C:/Users/JJ/OneDrive - ISCTE-IUL/EDA/Aula 4.py", line 60, in s.push(numpy.array([number], dtype=numpy.int32)) File "C:/Users/JJ/OneDrive - ISCTE-IUL/EDA/Aula 4.py", line 38, in push self.__items = numpy.concatenate(self.__items,item) File "<__array_function__ internals>", line 6, in concatenate TypeError: only integer scalar arrays can be converted to a scalar index` — João Júlio, Mar 20 '20 at 17:57
@JoãoJúlio--according to the [documentation](https://docs.scipy.org/doc/numpy/reference/generated/numpy.delete.html) delete returns a new array. — DarrylG, Mar 20 '20 at 18:29
@JoãoJúlio--here is a [shared online version of my running code](https://repl.it/@DarrylGurganiou/HelplessWirelessDoom) you can try. — DarrylG, Mar 20 '20 at 18:34
@JoãoJúlio--to expand on my previous comment since delete returns a new array, that means that in your original pop method `return numpy.delete(self.__items,0,-1)` leaves `self.__items unchanged`. — DarrylG, Mar 20 '20 at 18:37
so in reality this is away to unefficient because our real stack ( `self.__items = np.array([])`) will always stay the same because we can't remove items from there and to "remove" we create a copy of the original stack and remove from there. Am I correct? — João Júlio, Mar 20 '20 at 18:45
@JoãoJúlio--as [this answer](https://stackoverflow.com/questions/32932866/numpy-the-best-way-to-remove-the-last-element-from-1-dimensional-array) points out Numpy arrays are fixed in size so can't be changed. So the delete operation has to create a new array. So you're right, Numpy arrays are inefficient to use as a stack since we keep creating new arrays as we add (push) and delete (pop) elements from the stack. That's why a simple [list](https://docs.python.org/3/tutorial/datastructures.html) is much better for this purpose. — DarrylG, Mar 20 '20 at 18:53
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/210029/discussion-between-joao-julio-and-darrylg). — João Júlio, Mar 20 '20 at 18:56

score 0 · Answer 2 · answered Mar 20 '20 at 15:57

0

You're trying to use a numpy array as a stack, which might not work as well as you hope. Numpy arrays are designed for mathematical computation, not as general-purpose data structures.

Instead just use a Python list to implement your stack. In fact the Python documentation even includes a section on how to do just that:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

answered Mar 20 '20 at 15:57

robbrit

17,560
4
48
68

I already did this type of stack. Now I need to build the stack using the array, and I'm getting trigered because arrays aren't supossed to this type of "jobs" and I don't know how to correct this code. @robbrit – João Júlio Mar 20 '20 at 16:06

Trying to build a Stack Algoritm using an array

2 Answers2