StacksQueues/Python/ArrayStack - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:55:21Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:55, 9 October 2019
Line 18:		Line 18:
	The ArrayStack class implements the above abstraction using an array-based structure (a list).		The ArrayStack class implements the above abstraction using an array-based structure (a list).

	Link: https://charlesreid1.com~~:3000~~/cs/python/src/master/stacks-queues-deques/stacks/ArrayStack.py		Link: https://git.charlesreid1.com/cs/python/src/master/stacks-queues-deques/stacks/ArrayStack.py

	==Class test==		==Class test==

Admin at 17:06, 9 September 2017

2017-09-09T17:06:52Z

← Older revision		Revision as of 17:06, 9 September 2017
Line 131:		Line 131:

	=Flags=		=Flags=

			{{StacksQueuesFlag}}

	[[Category:Stacks]]		[[Category:Stacks]]
Line 137:		Line 139:
	[[Category:Python Stacks]]		[[Category:Python Stacks]]
	[[Category:Python Arrays]]		[[Category:Python Arrays]]
	~~{{DataStructuresFlag}}~~

Admin at 23:42, 6 June 2017

2017-06-06T23:42:29Z

← Older revision		Revision as of 23:42, 6 June 2017
Line 1:		Line 1:
	Array-Based Stack Implementation.		Array-Based Stack Implementation.

			This utilizes the built-in Python list type, and wraps it with a Stack ADT interface.

	==Class description==		==Class description==

Admin: /* Class implementation */

2017-05-30T06:14:59Z

Class implementation

← Older revision		Revision as of 06:14, 30 May 2017
Line 128:		Line 128:


			=Flags=

	[[Category:Stacks]]		[[Category:Stacks]]
Line 134:		Line 135:
	[[Category:Python Stacks]]		[[Category:Python Stacks]]
	[[Category:Python Arrays]]		[[Category:Python Arrays]]
	{{~~DataStructureFlag~~}}		{{DataStructuresFlag}}

Admin at 06:14, 30 May 2017

2017-05-30T06:14:42Z

← Older revision		Revision as of 06:14, 30 May 2017
Line 126:		Line 126:
	This is an adapter pattern for the list class.		This is an adapter pattern for the list class.

	~~{{PythonArraysFlag}}~~


	[[Category:Stacks]]		[[Category:Stacks]]
	[[Category:Lists]]		[[Category:Lists]]

			[[Category:Python Stacks]]
			[[Category:Python Arrays]]
			{{DataStructureFlag}}

Admin: /* Class implementation */

2017-05-30T05:42:15Z

Class implementation

← Older revision		Revision as of 05:42, 30 May 2017
Line 126:		Line 126:
	This is an adapter pattern for the list class.		This is an adapter pattern for the list class.

	{{~~PythonArrays~~}}		{{PythonArraysFlag}}
	[[Category:Stacks]]		[[Category:Stacks]]
	[[Category:Lists]]		[[Category:Lists]]

Admin at 05:41, 30 May 2017

2017-05-30T05:41:49Z

← Older revision		Revision as of 05:41, 30 May 2017
Line 125:		Line 125:

	This is an adapter pattern for the list class.		This is an adapter pattern for the list class.

			{{PythonArrays}}
			[[Category:Stacks]]
			[[Category:Lists]]

Admin: /* Class implementation */

2017-05-30T05:38:10Z

Class implementation

← Older revision		Revision as of 05:38, 30 May 2017
Line 122:		Line 122:

	</pre>		</pre>


			This is an adapter pattern for the list class.

Admin: Created page with "Array-Based Stack Implementation. ==Class description== Recap: Definition of stack abstract data type (Stack ADT): A stack is an abstract data type (ADT) such that an insta..."

2017-05-30T05:37:46Z

Created page with "Array-Based Stack Implementation. ==Class description== Recap: Definition of stack abstract data type (Stack ADT): A stack is an abstract data type (ADT) such that an insta..."

New page

Array-Based Stack Implementation.

==Class description==

Recap: Definition of stack abstract data type (Stack ADT):

A stack is an abstract data type (ADT) such that an instance S supports the following two methods:
* S.push(e): add element e to the top of the stack S
* S.pop: remove and return the top element from the stack S; an error occurs if the stack is empty.

Additionally, accessor methods for convenience:
* S.peek(): get reference to top element without removing it; an error occurs if the stack is empty.
* S.is_empty(): return True if stack S contains no elements
* len(S): implemented via builtin __len__

The ArrayStack class implements the above abstraction using an array-based structure (a list).

Link: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/stacks/ArrayStack.py

==Class test==

Taking a look first at our test, we should be able to run the following code after implementing the above methods:

<pre>
if __name__=="__main__":
a = ArrayStack()
a.push(5)
a.push(15)
a.push(17)
a.push(28)
print("Peeking: {0}".format(a.peek()))
print("Length of stack: {0}".format(len(a)))
a.pop()
a.pop()
a.push(100)
a.push(200)
a.push(300)
a.push(400)
while(not a.is_empty()):
a.pop()
print("Popping... {0}".format(len(a)))
print("Done testing ArrayStack.")
</pre>

==Exceptions and error handling==

The specification of the ADT mentions two cases where errors should be thrown - both occurring if the stack is empty.

Create our own Empty exception:

<pre>
class Empty(Exception):
pass
</pre>

==Class implementation==

<pre>

"""
Stack ADT: ArrayStack

This class implements the following methods:
S.push(e)
S.pop()
S.peek()
S.is_empty()
len(S)

This class utilizes an array-based data structure,
a list, to store its data under the hood.
It only needs to keep track of that list.

This makes it an adapter class for the list,
since it adheres to the Stack ADT but does not change
the implementation of the underlying list type.
"""

class ArrayStack:
"""
Implement the Stack ADT using an array-based data structure (list).
"""
def __init__(self):
self._data = []

def __len__(self):
return len(self._data)

def __str__(self):
return str(self._data)

def is_empty(self):
"""
Check if empty. Don't bother calling our own __len__.
Just do what is sensible.
"""
return (len(self._data)==0)

def push(self,o):
"""
Add an element to the top of the stack
"""
self._data.append(o)

def pop(self):
"""
Pop the next item.
This should handle an empty stack.
"""
if( self.is_empty() ):
raise Empty("Stack is empty")
return self._data.pop()

def peek(self):
"""
Peek at the next item.
This should handle an empty stack.
"""
if( self.is_empty() ):
raise Empty("Stack is empty")
return self._data[-1]

</pre>