StacksQueues: Difference between revisions
From charlesreid1
(Created page with "Why stacks and queues? If you follow the abstract data type interface, all operations to access stacks and queues are O(1). Stacks - last-in, first-out data structure where t...") |
|||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Why stacks and queues? If you follow the abstract data type interface, all operations to access stacks and queues are O(1). | =Notes= | ||
==Stacks and Queues - why== | |||
Why stacks and queues? If you follow the abstract data type interface, all operations to access stacks and queues are O(1). (See [[Abstract Data Types]] page for a comparison table.) | |||
Stacks - last-in, first-out data structure where things are added and removed from the top. | Stacks - last-in, first-out data structure where things are added and removed from the top. | ||
| Line 6: | Line 10: | ||
[[StacksQueues/Python]] | [[StacksQueues/Python]] | ||
[[StacksQueues/Java]] | |||
==Goodrich Chapter 6== | |||
===Stacks=== | |||
Stacks are LIFO objects that provide the following methods: | |||
* push | |||
* pop | |||
You can implement other convenience methods, but that's the basic concept. | |||
* top or peek | |||
* size | |||
* isEmpty | |||
The stack class in Java Collections framework provides a built-in object that's fully functional and very fast. | |||
Two implementations guided by Goodrich book: | |||
* [[StacksQueues/Java/ArrayStack]] - array-based data structure (dynamically-resized array) implementation of Stack | |||
* [[StacksQueues/Java/LinkedStack]] - link-based data structure (singly-linked list) implementation of Stack | |||
==Skiena Chapter 3== | |||
===Basics of stacks and queues=== | |||
Stacks and queues provide a container that permits storage and retrieval of data items ''independent of content.'' | |||
This contrasts with [[Dictionaries]], a data structure where data retrieval happens based on key values or content. | |||
If a container permits storage and retrieval independent of content, its defining characteristic is the order of retrieval that they support. | |||
'''Stacks''' implement LIFO (last in first out) order. | |||
'''Queues''' implement FIFO (first in first out) order. | |||
Stacks: | |||
* push(x,s) - insert item x at top of stack s | |||
* pop(s) - return and remove the top item of stack s | |||
Queues: | |||
* enqueue(x,q) - insert item x at the back of queue q | |||
* dequeue(q) - return and remove the front item from queue q | |||
Queues are the fundamental data structure for controlling breadth-first searches in graphs. | |||
These can be implemented using arrays or linked lists, with or without an upper bound. | |||
===Priority queues=== | |||
See [[Priority Queues]] | |||
=Flags= | |||
{{CSFlag}} | |||
Latest revision as of 09:12, 5 September 2017
Notes
Stacks and Queues - why
Why stacks and queues? If you follow the abstract data type interface, all operations to access stacks and queues are O(1). (See Abstract Data Types page for a comparison table.)
Stacks - last-in, first-out data structure where things are added and removed from the top.
Queues - first-in, first-out data structure where things are removed from the front and added to the back.
Goodrich Chapter 6
Stacks
Stacks are LIFO objects that provide the following methods:
- push
- pop
You can implement other convenience methods, but that's the basic concept.
- top or peek
- size
- isEmpty
The stack class in Java Collections framework provides a built-in object that's fully functional and very fast.
Two implementations guided by Goodrich book:
- StacksQueues/Java/ArrayStack - array-based data structure (dynamically-resized array) implementation of Stack
- StacksQueues/Java/LinkedStack - link-based data structure (singly-linked list) implementation of Stack
Skiena Chapter 3
Basics of stacks and queues
Stacks and queues provide a container that permits storage and retrieval of data items independent of content.
This contrasts with Dictionaries, a data structure where data retrieval happens based on key values or content.
If a container permits storage and retrieval independent of content, its defining characteristic is the order of retrieval that they support.
Stacks implement LIFO (last in first out) order.
Queues implement FIFO (first in first out) order.
Stacks:
- push(x,s) - insert item x at top of stack s
- pop(s) - return and remove the top item of stack s
Queues:
- enqueue(x,q) - insert item x at the back of queue q
- dequeue(q) - return and remove the front item from queue q
Queues are the fundamental data structure for controlling breadth-first searches in graphs.
These can be implemented using arrays or linked lists, with or without an upper bound.
Priority queues
See Priority Queues
Flags
 |
Computer Science notes on computer science topics on the wiki, for educational and learning purposes
Part of the 2017 CS Study Plan.
Python/Exceptions · Python/Assertions · Python/Decorators Python/Os (os module) · Python/Strings Python/Splat · Python/Iterators · Python/Generators Python/Comparators · Python/Lambdas
Builtin features of Java: Java/Exceptions · Java/Assertions · Java/Memory · Java/Interfaces Java/Generics · Java/Decorators · Java/Diamond Notation Java/Iterators · Java/Iterable · Iterators vs Iterable Java/Comparators · Java/Comparable · Comparators vs Comparable Java/Numeric · Java/TypeChecking · Java/Testing · Java/Timing · Java/Profiling Documentation: Javadocs · Java/Documentation Tools and functionality: Java/URLs · Java/CSV External libraries: Guava · Fastutil · Eclipse Collections OOP: OOP Checklist · Java/Abstract Class · Java/Encapsulation · Java/Generics
|
See also: