This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Implement a stack with push, pop, peek, and is_empty methods using a linked list.

Constraints
Test Cases
Algorithm
Code
Unit Test
Pythonic-Code

Constraints

None

Test Cases

Push

Push to empty stack
Push to non-empty stack

Pop

Pop on empty stack
Pop on single element stack
Pop on multiple element stack

Peek

Peek on empty stack
Peek on one or more element stack

Is Empty

Is empty on empty stack
Is empty on one or more element stack

Algorithm

Push

Create new node with value
Set node's next to top
Set top to node

Complexity:

Time: O(1)
Space: O(1)

Pop

If stack is empty, return None
Else
- Save top's value
- Set top to top.next
- Return saved value

Complexity:

Time: O(1)
Space: O(1)

Peek

If stack is empty, return None
Else return top's value

Complexity:

Time: O(1)
Space: O(1)

Is Empty

If peek has a value, return False
Else return True

Complexity:

Time: O(1)
Space: O(1)

Code



In [1]:

    
%%writefile stack.py
class Node(object):

    def __init__(self, data):
        self.data = data
        self.next = None


class Stack(object):

    def __init__(self, top=None):
        self.top = top

    def push(self, data):
        node = Node(data)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.top is not None:
            data = self.top.data
            self.top = self.top.next
            return data
        return None

    def peek(self):
        if self.top is not None:
            return self.top.data
        return None

    def is_empty(self):
        return self.peek() is None









    



Overwriting stack.py



In [2]:

    
%run stack.py

Unit Test



In [3]:

    
%%writefile test_stack.py
from nose.tools import assert_equal


class TestStack(object):

    # TODO: It would be better if we had unit tests for each
    # method in addition to the following end-to-end test
    def test_end_to_end(self):
        print('Test: Empty stack')
        stack = Stack()
        assert_equal(stack.peek(), None)
        assert_equal(stack.pop(), None)

        print('Test: One element')
        top = Node(5)
        stack = Stack(top)
        assert_equal(stack.pop(), 5)
        assert_equal(stack.peek(), None)

        print('Test: More than one element')
        stack = Stack()
        stack.push(1)
        stack.push(2)
        stack.push(3)
        assert_equal(stack.pop(), 3)
        assert_equal(stack.peek(), 2)
        assert_equal(stack.pop(), 2)
        assert_equal(stack.peek(), 1)
        assert_equal(stack.is_empty(), False)
        assert_equal(stack.pop(), 1)
        assert_equal(stack.peek(), None)
        assert_equal(stack.is_empty(), True)

        print('Success: test_end_to_end')


def main():
    test = TestStack()
    test.test_end_to_end()


if __name__ == '__main__':
    main()









    



Overwriting test_stack.py



In [4]:

    
%run -i test_stack.py









    



Test: Empty stack
Test: One element
Test: More than one element
Success: test_end_to_end

Pythonic-Code

Source: https://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks

5.1.1. Using Lists as Stacks
The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved (“last-in, first-out”). To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop() without an explicit index. For example:

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