Stacks Queues Study Guide - Revision history

Admin: /* Array-based */

2017-08-28T11:27:20Z

Array-based

← Older revision		Revision as of 11:27, 28 August 2017
Line 66:		Line 66:
	* data array		* data array
	* top pointer (integer)		* top pointer (integer)
			* size (integer)

	ArrayQueue:		ArrayQueue:

Admin: /* Definitions and Variations */

2017-08-28T10:46:03Z

Definitions and Variations

← Older revision		Revision as of 10:46, 28 August 2017
Line 5:		Line 5:
	'''FIFO''' - first in, first out (queues)		'''FIFO''' - first in, first out (queues)

	'''stack''' - LIFO data structure that only provides access at ~~the ends~~		'''stack''' - LIFO data structure that only provides access at one end

	'''queue''' - FIFO data structure that provides limited access at either end		'''queue''' - FIFO data structure that provides limited access at either end

Admin: /* Definitions and Variations */

2017-08-28T10:45:22Z

Definitions and Variations

← Older revision		Revision as of 10:45, 28 August 2017
Line 13:		Line 13:
	'''adapter pattern''' - a class that adapts one type of class and matches its methods to a different but related interface/class		'''adapter pattern''' - a class that adapts one type of class and matches its methods to a different but related interface/class

	~~Variatoins~~:		Variations:
	* Linked versus array implementation		* Linked versus array implementation
	* Fixed vs variable size		* Fixed vs variable size

Admin: /* Definitions and Variations */

2017-08-28T10:45:05Z

Definitions and Variations

← Older revision		Revision as of 10:45, 28 August 2017
Line 9:		Line 9:
	'''queue''' - FIFO data structure that provides limited access at either end		'''queue''' - FIFO data structure that provides limited access at either end

	'''dequeue''' - FIFO data structure that provides limited access at ~~either~~ end		'''dequeue''' - FIFO data structure that provides limited access at both end

	~~'''dequeue''' - FIFO data structure that provides access at tboth ends~~

	'''adapter pattern''' - a class that adapts one type of class and matches its methods to a different but related interface/class		'''adapter pattern''' - a class that adapts one type of class and matches its methods to a different but related interface/class

Admin: /* Definitions and Variations */

2017-07-06T08:45:24Z

Definitions and Variations

← Older revision		Revision as of 08:45, 6 July 2017
Line 1:		Line 1:
	=Definitions and Variations=		=Definitions and Variations=

			'''LIFO''' - last in, first out (stacks)

			'''FIFO''' - first in, first out (queues)

			'''stack''' - LIFO data structure that only provides access at the ends

			'''queue''' - FIFO data structure that provides limited access at either end

			'''dequeue''' - FIFO data structure that provides limited access at either end

			'''dequeue''' - FIFO data structure that provides access at tboth ends

			'''adapter pattern''' - a class that adapts one type of class and matches its methods to a different but related interface/class

			Variatoins:
			* Linked versus array implementation
			* Fixed vs variable size
			* Sorted (priority) queues

	=ADT and Interfaces=		=ADT and Interfaces=

Admin: /* ADT and Interfaces */

2017-07-06T08:43:28Z

ADT and Interfaces

← Older revision		Revision as of 08:43, 6 July 2017
Line 2:		Line 2:

	=ADT and Interfaces=		=ADT and Interfaces=

			Stack:
			* push
			* pop
			* peek
			* size
			* empty

			Extra:
			* clear
			* clone
			* equals

			Queue:
			* enqueue
			* dequeue
			* peek
			* size
			* empty

			Extra:
			* clear
			* clone
			* equals

			Dequeue:
			* addFront
			* addBack
			* removeFront
			* removeBack
			* peekFront
			* peekBack
			* size
			* empty

			Extra:
			* clear
			* clone
			* equals

	=Implementations=		=Implementations=

Admin: /* Implementations */

2017-07-06T08:20:29Z

Implementations

← Older revision		Revision as of 08:20, 6 July 2017
Line 4:		Line 4:

	=Implementations=		=Implementations=

			==Array-based==

			ArrayStack:
			* data array
			* top pointer (integer)

			ArrayQueue:
			* data array
			* front pointer (integer)
			* size (integer)

			ArrayDeque
			* data array
			* front pointer (integer)
			* size (integer)

			==Link-based==

			LinkedStack:
			* private instance of linked list
			* adapter pattern

			LinkedQueue:
			* private instance of linked list

			Linked Circular Queue:
			* private instance of circular linked list

			Linked Deque:
			* private instance of doubly linked list

	=Algorithms for Operations=		=Algorithms for Operations=

Admin: /* Algorithms for Operations */

2017-07-06T07:55:28Z

Algorithms for Operations

← Older revision		Revision as of 07:55, 6 July 2017
Line 6:		Line 6:

	=Algorithms for Operations=		=Algorithms for Operations=

			==Linked Stack Algorithms==

			push(e) method:
			* list.addFront(e)

			pop() method:
			* list.removeFront()

			peek() method:
			* list.first()

			==Linked Queue Algorithms==

			enqueue(e):
			* list.addBack()

			dequeue():
			* list.removeFront()

			peek:
			* list.first()

			==Linked Deque==

			This uses a doubly linked list (DLL, or dll, below).

			addFront:
			* dll.addFront()

			add/addBack();
			* dll.addBack()

			removeFront()/remove():
			* dll.removeFront()

			removeBack:
			* dll.removeBack()

	=Complexity and Cost=		=Complexity and Cost=

Admin: Created page with "=Definitions and Variations= =ADT and Interfaces= =Implementations= =Algorithms for Operations= =Complexity and Cost= ==Big O Complexity Table== ===Stacks=== {| class="..."

2017-07-06T07:51:19Z

Created page with "=Definitions and Variations= =ADT and Interfaces= =Implementations= =Algorithms for Operations= =Complexity and Cost= ==Big O Complexity Table== ===Stacks=== {| class="..."

New page

=Definitions and Variations=

=ADT and Interfaces=

=Implementations=

=Algorithms for Operations=

=Complexity and Cost=

==Big O Complexity Table==

===Stacks===

{| class="wikitable" cellpadding="100" width="33%"
!colspan="2"|Big-O Complexity of Stacks
|-
|
| 
Stacks

|-
|push
|O(1)*

|-
|pop
|O(1)*

|-
|peek
|O(1)

|-
|empty
|O(1)

|-
|size
|O(1)

|}

===Queues===

{| class="wikitable" cellpadding="100" width="33%"
!colspan="2"|Big-O Complexity of Queues
|-
|
| 
Queues

|-
|enqueue
|O(1)*

|-
|dequeue
|O(1)*

|-
|peek
|O(1)

|-
|empty
|O(1)

|-
|size
|O(1)

|}

===Deque===

{| class="wikitable" cellpadding="100" width="33%"
!colspan="2"|Big-O Complexity of Deques
|-
|
| 
Deques

|-
|addFront
|O(1)*

|-
|addBack
|O(1)*

|-
|removeFront
|O(1)*

|-
|removeBack
|O(1)*

|-
|peekFront
|O(1)

|-
|peekBack
|O(1)

|-
|empty
|O(1)

|-
|size
|O(1)

|}

=OOP Principles=

* Adapter pattern - results in simple, compact, portable classes.

=Flags=

{{StacksQueuesFlag}}

[[Category:Study Guide]]