Python stack simulation using list structure but not list methods

Question

How would you go about simulating a stack's push and pop functions WITHOUT using list methods?

So far I have something like this, but I am not sure as to whether this would work:

stack = []

def Push(stack, element):
    stack[len(stack)] = element

def Pop(stack):
    element = tos
    stack[len(stack) - 1] = None

    return element;

Would push work, dynamically adding to the list in this manner, and would len update appropriately?

For pop, how would you go about "deleting" from the stack without using any of the list functions?

stack[len(stack)] will always fail if stack is a list

John La Rooy
– John La Rooy

2014-03-30 23:08:54 +00:00
Commented Mar 30, 2014 at 23:08 — John La Rooy
– John La Rooy, Commented Mar 30, 2014 at 23:08

jrd1 · Accepted Answer · 2014-03-31 00:14:07Z

1

You could use something like this (warning: this is a naive implementation - it doesn't perform checks on the arguments passed):

class Stack(object):
    def __init__(self):
        self._stack = [] # Allocate an empty list

    def push(self, ele):
        self._stack += [ele] # Use list concatenation to emulate the `push` operation

    def pop(self):
        last = self._stack[-1:] # Return the last element of the list (also works for empty lists)
        self._stack = self.stack[0:-1] # Copy the elements from the beginning of the list to the last element of the list
        return last # return the last element

    # All stacks should have the `size` function to determine how many elements are
    # in the stack:
    def size(self):
        return len(self._stack)

    # Occasionally you'll want to see the contents of the stack, so we have to
    # implement the `__str__` magic method:
    def __str__(self):
        return '[%s]' % ','.join(map(str, self._stack))

NOTE: This method doesn't use any of the list methods as append and pop.

EXAMPLE:

s = Stack()

# fill the stack with values:
for i in xrange(10):
    s.push(i+1)

print s # Outputs: [1,2,3,4,5,6,7,8,9,10]

s.pop()
s.pop()

print s # Outputs: [1,2,3,4,5,6,7,8]

edited Mar 31, 2014 at 0:14

answered Mar 30, 2014 at 23:35

jrd1

10.8k4 gold badges37 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

jrd1 Over a year ago

@elykl33t: I loathe to be pedantic, but it's not necessarily sublists, but rather slicing. ;) Also: you're more than welcome and, thank you as well! :)

nickie · Accepted Answer · 2014-03-30 23:21:18Z

0

I suppose the intention of this exercise is to look at stacks as an abstract data type. You could implement them without using lists at all. If you insist on using lists, I'm not sure what you mean by "not using list methods".

A stack (as a list) is a data type with two constructors: (a) an empty stack, and (b) the result of pushing an element onto a stack. You can come up with a lot of different implementations of these two in Python. E.g., None could be the empty stack and (x, s) could be the result of pushing x on top of s. I suggest that you try to do something like this on your own, before looking for more help.

edited Mar 30, 2014 at 23:21

answered Mar 30, 2014 at 23:15

nickie

5,8282 gold badges28 silver badges40 bronze badges

Comments

Hugh Bothwell · Accepted Answer · 2014-03-30 23:55:59Z

0

You could preallocate a list:

class Stack:
    def __init__(self, max_items):
        self.data = [0] * max_items
        self.max_items = max_items
        self.top = -1

    def push(self, i):
        self.top += 1
        if self.top < self.max_items:
            self.data[self.top] = i
        else:
            self.top -= 1
            raise ValueError("stack is full")

    def pop(self):
        if self.top >= 0:
            i = self.data[self.top]
            self.top -= 1
            return i
        else:
            raise ValueError("stack is empty")

    def __len__(self):
        return self.top + 1

answered Mar 30, 2014 at 23:55

Hugh Bothwell

57k9 gold badges91 silver badges103 bronze badges

Collectives™ on Stack Overflow

Python stack simulation using list structure but not list methods

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related