forked from phuang07/python_algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstack.py
More file actions
129 lines (104 loc) · 3.83 KB
/
Copy pathstack.py
File metadata and controls
129 lines (104 loc) · 3.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""This module implements a linked list based stack data structure.
A stack is a data structure to hold a collection of items in which operations
such as the addition of an item (*push*) and removal of an item (*pop*) can
be performed. The items are always pushed or popped from the so called *top*
of the data structure which is the last item added or first item to be removed.
The stack can be also viewed as a Last-In-First-Out(*LIFO*) data structure. In
a LIFO data structure, the last item added to the structure must be the first
item one to be removed. Apart from those two operations, *peek* operation can
also be implemented, returning the value of the top item without removing it.
The particular implementation of stack in this module is based on linked list,
as array based stack implementation is already supported in python's list. In
the linked list based implementation, the stack object need to keep track of
only the head node. Each node contains an item and a link to the next node.
.. note:: For most practical purposes, the python's list suffices as a stack
object. Use append method instead of push and pop method as it is for
stack operations in a list.
Complexity:
* push -- O(1)
* pop -- O(1)
* peek -- O(1)
"""
class _Node(object):
"""An internal class that represents a node with a single item
and a link to the next node.
"""
def __init__(self, item):
self.item = item
self.next = None
class Stack(object):
"""An implementation of a simple stack with linked list."""
def __init__(self):
"""Initialize an empty stack."""
self._head = None
self._size = 0
@property
def size(self):
"""The number of items in the stack."""
return self._size
def isEmpty(self):
"""Check if the stack is empty.
Returns:
True if the stack is empty.
False otherwise.
"""
return self._size == 0
def push(self, item):
"""Insert an item to the stack."""
n = _Node(item)
n.next = self._head
self._head = n
self._size += 1
def pop(self):
"""Remove and return the last added item from the stack.
Returns:
The last item added to the stack.
Raises:
IndexError: If the stack is empty.
"""
if self.isEmpty():
raise IndexError("pop from empty stack")
n = self._head
self._head = self._head.next
self._size -= 1
return n.item
def peek(self):
"""Return the last added item from the stack.
Returns:
The last item added to the stack.
Raises:
IndexError: If the stack is empty.
"""
if self.isEmpty():
raise IndexError("pop from empty stack")
return self._head.item
def __iter__(self):
"""Return iterator for the stack."""
current = self._head
while current:
yield current.item
current = current.next
def __str__(self):
"""String representation of the stack."""
return " ".join(reversed([str(item) for item in self]))
def __repr__(self):
"""Representation of the stack."""
return "Stack(" + str(self) + ")"
if __name__ == "__main__":
print("Stack using linked list.")
s = Stack()
while True:
n = int(raw_input("Enter a number to enter or 0 to pop a number"
"(exit when stack empty): "))
if n:
s.push(n)
print("Pushed: " + str(s.peek()))
print("Current stack: " + str(s))
else:
if s.isEmpty():
print("Stack is empty.")
break
print("Popped: " + str(s.pop()))
print("Current stack: " + str(s))