StacksQueues/Java - Revision history

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

2019-10-09T03:53:31Z

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

← Older revision		Revision as of 03:53, 9 October 2019
Line 60:		Line 60:
	Wiki notes: [[StacksQueues/Java/ArrayStack]] and Wiki notes: [[StacksQueues/Java/ArrayStackFS]]		Wiki notes: [[StacksQueues/Java/ArrayStack]] and Wiki notes: [[StacksQueues/Java/ArrayStackFS]]

	Array-based stack implementation: https://charlesreid1.com~~:3000~~/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java		Array-based stack implementation: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java

	===Array-based Queue Implementation===		===Array-based Queue Implementation===

	The first array-based queue implementation is a data structure that uses a dynamically allocated array size to store data. ArrayQueue class: https://charlesreid1.com~~:3000~~/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java		The first array-based queue implementation is a data structure that uses a dynamically allocated array size to store data. ArrayQueue class: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java

	The second aray-based queue implementation is a data structure that uses a fixed array size, and throws a Full exception when full. ArrayQueueFS class: https://charlesreid1.com~~:3000~~/cs/java/src/master/stacks-queues-deques/queues/ArrayQueueFS.java		The second aray-based queue implementation is a data structure that uses a fixed array size, and throws a Full exception when full. ArrayQueueFS class: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueueFS.java

	<pre>		<pre>
Line 80:		Line 80:
	The linked queue class uses a circular linked list to conserve memory for linked lists with high throughput.		The linked queue class uses a circular linked list to conserve memory for linked lists with high throughput.

	See LinkedQueue class: https://charlesreid1.com~~:3000~~/cs/java/src/master/stacks-queues-deques/queues/LinkedQueue.java		See LinkedQueue class: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/LinkedQueue.java

	=Flags=		=Flags=

Admin: /* Goodrich Java Chapter 6 */

2017-06-04T09:01:13Z

Goodrich Java Chapter 6

@@ Line 6: / Line 6: @@
 Chapter 6 of Goodrich covers stacks and queues. These data structures can be implemented using array-based or link-based data structures. Thus, when covering data structures it's useful to start by covering array-based data structures that are dynamic, and their big-O cost of operations.
 Queue - singly-linked list implementation - single head pointer - allows us to:
@@ Line 12: / Line 24: @@
 Removing is O(n) because in a singly-linked list, we need the thing that links to tail.
 =Implementations=

Admin: /* Array-based Stack Implementation */

2017-06-04T05:47:57Z

Array-based Stack Implementation

← Older revision		Revision as of 05:47, 4 June 2017
Line 39:		Line 39:

	implementation of a stack using a fixed or variable size array.		implementation of a stack using a fixed or variable size array.

			Wiki notes: [[StacksQueues/Java/ArrayStack]] and Wiki notes: [[StacksQueues/Java/ArrayStackFS]]

	Array-based stack implementation: https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java		Array-based stack implementation: https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java

Admin: /* Stack interfaces */

2017-06-04T05:46:26Z

Stack interfaces

← Older revision		Revision as of 05:46, 4 June 2017
Line 26:		Line 26:
	==Stack interfaces==		==Stack interfaces==

	Interfaces in Java provide programmers with "inheritance lite" - in the form of a set of virtual methods that a class is required to implement~~, but with no additional restrictions or behaviors imposed~~.		Interfaces in Java provide programmers with "inheritance lite" - in the form of a set of virtual methods that a class is required to implement.

	These allow a uniform interface to be imposed for data collections objects. ~~As an example, here~~ is a Stack class ~~interface~~ that adheres to ~~some of~~ the ~~methods~~ described ~~above~~:		These allow a uniform interface to be imposed for data collections objects.

			Here is a Java interface for a Stack class that adheres to the Stack interface described at the [[Abstract Data Types]] page:

	[[StacksQueues/Java/Stack Interface]]		[[StacksQueues/Java/Stack Interface]]

Admin: /* Stack interfaces */

2017-06-04T05:45:31Z

Stack interfaces

← Older revision		Revision as of 05:45, 4 June 2017
Line 25:		Line 25:

	==Stack interfaces==		==Stack interfaces==

			Interfaces in Java provide programmers with "inheritance lite" - in the form of a set of virtual methods that a class is required to implement, but with no additional restrictions or behaviors imposed.

			These allow a uniform interface to be imposed for data collections objects. As an example, here is a Stack class interface that adheres to some of the methods described above:

	[[StacksQueues/Java/Stack Interface]]		[[StacksQueues/Java/Stack Interface]]

Admin: /* Stack interfaces */

2017-06-04T05:40:56Z

Stack interfaces

← Older revision		Revision as of 05:40, 4 June 2017
Line 26:		Line 26:
	==Stack interfaces==		==Stack interfaces==

	[[StacksQueues/Java/Stack ~~interface~~]]		[[StacksQueues/Java/Stack Interface]]

	==Stack classes==		==Stack classes==

Admin: /* Implementations */

2017-06-04T05:40:46Z

Implementations

← Older revision		Revision as of 05:40, 4 June 2017
Line 24:		Line 24:
	* inputs X, outputs Y, with timing/profiling.		* inputs X, outputs Y, with timing/profiling.

	==Array-based Stack Implementation==		==Stack interfaces==

			[[StacksQueues/Java/Stack interface]]

			==Stack classes==

			===Array-based Stack Implementation===

	implementation of a stack using a fixed or variable size array.		implementation of a stack using a fixed or variable size array.
Line 30:		Line 36:
	Array-based stack implementation: https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java		Array-based stack implementation: https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java

	==Array-based Queue Implementation==		===Array-based Queue Implementation===

	The first array-based queue implementation is a data structure that uses a dynamically allocated array size to store data. ArrayQueue class: https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java		The first array-based queue implementation is a data structure that uses a dynamically allocated array size to store data. ArrayQueue class: https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java
Line 44:		Line 50:
	</pre>		</pre>

	==Linked List-based Queue Implementation==		===Linked List-based Queue Implementation===

	The linked queue class uses a circular linked list to conserve memory for linked lists with high throughput.		The linked queue class uses a circular linked list to conserve memory for linked lists with high throughput.

Admin: /* Implementations */

2017-06-04T05:36:46Z

Implementations

@@ Line 24: / Line 24: @@
 * inputs X, outputs Y, with timing/profiling.
-==ArrayStack==
+==Array-based Stack Implementation==
 implementation of a stack using a fixed or variable size array.
 =Flags=

Admin: /* Goodrich Chapter 6 */

2017-06-04T04:25:18Z

Goodrich Chapter 6

← Older revision		Revision as of 04:25, 4 June 2017
Line 3:		Line 3:
	Stacks and Queues in Java are implemented as part of the Collections library. Also implemented are Deques and priority queues.		Stacks and Queues in Java are implemented as part of the Collections library. Also implemented are Deques and priority queues.

	==Goodrich Chapter 6==		==Goodrich Java Chapter 6==

			Chapter 6 of Goodrich covers stacks and queues. These data structures can be implemented using array-based or link-based data structures. Thus, when covering data structures it's useful to start by covering array-based data structures that are dynamic, and their big-O cost of operations.

			Queue - singly-linked list implementation - single head pointer - allows us to:
			* insert/remove at the head with O(1)
			* insert/remove at the tail with O(n)

			Removing is O(n) because in a singly-linked list, we need the thing that links to tail.

	=Implementations=		=Implementations=

Admin: /* Implementations */

2017-06-03T07:31:52Z

Implementations

← Older revision		Revision as of 07:31, 3 June 2017
Line 15:		Line 15:
	measurement/profiling of Java code for memory and performance, timing, etc.		measurement/profiling of Java code for memory and performance, timing, etc.
	* inputs X, outputs Y, with timing/profiling.		* inputs X, outputs Y, with timing/profiling.

			==ArrayStack==

			implementation of a stack using a fixed or variable size array.

	=Flags=		=Flags=