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.

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

StacksQueues

From charlesreid1

Contents