GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — algorithms/algorithms/stack/stack.py at master · oldmonad/algorithms Expand file tree/ Copy pathstack.pyMore file actions 132 lines (109 loc) · 3.37 KB / Copy pathstack.pyFile metadata and controls132 lines (109 loc) · 3.37 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 130 131 132 """ Stack Abstract Data Type (ADT) Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack. push(item) adds a new item to the top of the stack. It needs the item and returns nothing. pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified. peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified. isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value. size() returns the number of items on the stack. It needs no parameters and returns an integer. """ from abc import ABCMeta, abstractmethod class AbstractStack(metaclass=ABCMeta): """Abstract Class for Stacks.""" def __init__(self): self._top = -1 def __len__(self): return self._top + 1 def __str__(self): result = " ".join(map(str, self)) return 'Top-> ' + result def is_empty(self): return self._top == -1 @abstractmethod def __iter__(self): pass @abstractmethod def push(self, value): pass @abstractmethod def pop(self): pass @abstractmethod def peek(self): pass class ArrayStack(AbstractStack): def __init__(self, size=10): """ Initialize python List with size of 10 or user given input. Python List type is a dynamic array, so we have to restrict its dynamic nature to make it work like a static array. """ super().__init__() self._array = [None] * size def __iter__(self): probe = self._top while True: if probe == -1: return yield self._array[probe] probe -= 1 def push(self, value): self._top += 1 if self._top == len(self._array): self._expand() self._array[self._top] = value def pop(self): if self.is_empty(): raise IndexError("stack is empty") value = self._array[self._top] self._top -= 1 return value def peek(self): """returns the current top element of the stack.""" if self.is_empty(): raise IndexError("stack is empty") return self._array[self._top] def _expand(self): """ expands size of the array. Time Complexity: O(n) """ self._array += [None] * len(self._array) # double the size of the array class StackNode: """Represents a single stack node.""" def __init__(self, value): self.value = value self.next = None class LinkedListStack(AbstractStack): def __init__(self): super().__init__() self.head = None def __iter__(self): probe = self.head while True: if probe is None: return yield probe.value probe = probe.next def push(self, value): node = StackNode(value) node.next = self.head self.head = node self._top += 1 def pop(self): if self.is_empty(): raise IndexError("Stack is empty") value = self.head.value self.head = self.head.next self._top -= 1 return value def peek(self): if self.is_empty(): raise IndexError("Stack is empty") return self.head.value |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |