Stacks and Queues

Flashcards about Stacks and Queues.

Arrays

Length fixed at time of allocation, data stored densely, supported as Python type.

Linked Lists

Length depends on elements, data stored as pair of data and reference(s), supported as Python collection.

Stack

Examine the item most recently added; LIFO (last in first out).

Queue

Examine the item least recently added; FIFO (first in first out).

Interface

A description of data type and basic operations.

Client

Program using operations defined in interface.

Implementation

Actual code implementing operations.

Last In First Out

What does LIFO stand for?

First In First Out

What does FIFO stand for?

pop()

Remove and return the element most recently added.

push(obj: item)

Insert a new element onto the stack.

How to implement a Stack with a Singly-Linked list?

Maintain pointer first to first node in a singly-linked list to pop item from first and push new item before first.

Underflow

Throw exception if pop from an empty stack.

Loitering

Holding a reference to an object when it is no longer needed.

push() with resize by 1

Increase size of array data[ ] by 1.