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 are LIFO objects that provide the following methods:
You can implement other convenience methods, but that's the basic concept.
- top or peek
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.
- push(x,s) - insert item x at top of stack s
- pop(s) - return and remove the top item of stack s
- 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.
See Priority Queues
Computer Sciencenotes on computer science topics on the wiki, for educational and learning purposes
Part of the 2017 CS Study Plan.
Flags · Template:CSFlag · e