Priority Queues/Stack - Revision history

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

2019-10-09T03:44:51Z

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

← Older revision		Revision as of 03:44, 9 October 2019
Line 3:		Line 3:
	'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''		'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/UseAsStack.java		Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/UseAsStack.java

	First, we can review the [[StacksQueues\|Stacks]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.		First, we can review the [[StacksQueues\|Stacks]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.

Admin: /* Flags */

2017-06-23T10:26:22Z

Flags

← Older revision		Revision as of 10:26, 23 June 2017
Line 85:		Line 85:

	==Flags==		==Flags==

			{{PriorityQueuesFlag}}
			{{StacksQueuesFlag}}

	[[Category:Interfaces]]		[[Category:Interfaces]]
Line 93:		Line 96:
	[[Category:Queues]]		[[Category:Queues]]
	[[Category:Priority Queues]]		[[Category:Priority Queues]]
	~~{{StacksQueuesFlag}}~~

Admin at 10:11, 23 June 2017

2017-06-23T10:11:51Z

← Older revision		Revision as of 10:11, 23 June 2017
Line 2:		Line 2:

	'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''		'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''

			Link: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/UseAsStack.java

	First, we can review the [[StacksQueues\|Stacks]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.		First, we can review the [[StacksQueues\|Stacks]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.

Admin at 10:11, 23 June 2017

2017-06-23T10:11:30Z

← Older revision		Revision as of 10:11, 23 June 2017
Line 60:		Line 60:
	}		}
	</pre>		</pre>

			If we print out the stack as we are removing items from it, we see the following output:

			<pre>
			[(earth), (the), (is), (this), (world), (hello)]
			earth
			[(the), (is), (this), (world), (hello)]
			the
			[(is), (this), (world), (hello)]
			is
			[(this), (world), (hello)]
			this
			[(world), (hello)]
			world
			[(hello)]
			hello
			[]
			</pre>

Admin at 10:09, 23 June 2017

2017-06-23T10:09:44Z

← Older revision		Revision as of 10:09, 23 June 2017
Line 64:		Line 64:

	==Flags==		==Flags==

			[[Category:Interfaces]]
			[[Category:Inheritance]]
			[[Category:OOP]]

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

Admin at 10:08, 23 June 2017

2017-06-23T10:08:56Z

← Older revision		Revision as of 10:08, 23 June 2017
Line 3:		Line 3:
	'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''		'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''

	First, we can review the [[Stacks]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.		First, we can review the [[StacksQueues\|Stacks]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.

	Here is some test code for what an eventual StackPQ object should look like:		Here is some test code for what an eventual StackPQ object should look like:
Line 60:		Line 60:
	}		}
	</pre>		</pre>



			==Flags==

			[[Category:Stacks]]
			[[Category:Queues]]
			[[Category:Priority Queues]]
			{{StacksQueuesFlag}}

Admin at 10:08, 23 June 2017

2017-06-23T10:08:05Z

← Older revision		Revision as of 10:08, 23 June 2017
Line 3:		Line 3:
	'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''		'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''

	First, we can review the [[~~Stack~~]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.		First, we can review the [[Stacks]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.

	Here is some test code for what an eventual StackPQ object should look like:		Here is some test code for what an eventual StackPQ object should look like:

Admin at 10:07, 23 June 2017

2017-06-23T10:07:54Z

← Older revision		Revision as of 10:07, 23 June 2017
Line 2:		Line 2:

	'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''		'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''

			First, we can review the [[Stack]] data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.

			Here is some test code for what an eventual StackPQ object should look like:

			<pre>
			public class UseAsStack {
			public static void main(String[] args) {
			StackPQ<String> q = new StackPQ<String>();
			q.push("hello");
			q.push("world");
			q.push("this");
			q.push("is");
			q.push("the");
			q.push("earth");
			while(!q.isEmpty()) {
			System.out.println(q.pop());
			}
			}
			}
			</pre>

			Note that this should take only ONE generic type argument, not two, even though our priority queue takes two types. Note that this is because Priority Queue objects need to specify the type of both the keys and the values. Here, the user of the Stack object is only using the values. Behind the scenes, the Stack specifies details of the keys.

			To implement a stack using a priority queue, it is key to recognize that the most recent item to be added to the stack should always be the minimum. The keys should be ordered in such a way that as items are added to the stack, the keys will descend.

			This is simple to do using negative integers. The keys start at -1, and work their way down as the index of each item moves up: -1, -2, -3, -4, etc.

			When we define the StackPQ class, we have one generic type for the values (type of data) being stored in the Stack. The key types of both the priority queue interface and the concrete sorted priority queue class are hard-coded as Integer types.

			<pre>
			// NOTE: extends should go before implements
			class StackPQ<V> extends SortedPQ<Integer,V> implements PriorityQueue<Integer,V> {

			// Stack can implement a priority queue
			// by adding items and assigning keys
			// based on order of insertion.
			// Keys should be a negative counter,
			// to keep them in reverse order added.
			int counter;

			/** Start with an empty stack. */
			public StackPQ(){ counter = 0; }

			// Stack ADT methods:

			public void push(V v) {
			counter++; // start at 1
			this.insert(new Integer(-1*counter), v);
			}

			public V pop() {
			counter--;
			return removeMin();
			}

			}
			</pre>

Admin: Created page with "Goodrich Book, Chapter 9, Priority Queues '''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''"

2017-06-23T09:59:25Z

Created page with "Goodrich Book, Chapter 9, Priority Queues '''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''"

New page

Goodrich Book, Chapter 9, Priority Queues

'''Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.'''