Chapter 6: Stack Implementations

This set of flashcards covers key terms and definitions related to stack implementations in data structures, particularly focusing on linked, array-based, and vector-based stacks.

Linked Stack

A stack implementation where entries are stored in a chain of nodes.

push()

A method that adds a new entry to the top of the stack.

pop()

A method that removes and returns the top entry from the stack.

peek()

A method that returns the top entry without removing it from the stack.

isEmpty()

A method that checks if the stack is empty.

clear()

A method that removes all entries from the stack.

Node

A data structure that contains an entry and a reference to the next node.

topNode

A reference to the first node in the linked stack.

EmptyStackException

An exception thrown when an operation is attempted on an empty stack.

Array-Based Stack

A stack implementation where entries are stored in a dynamic array.

integrityOK

A boolean flag indicating the integrity of a stack.

DEFAULT_CAPACITY

The default initial capacity of the stack.

MAX_CAPACITY

The maximum capacity allowed for the stack.

topIndex

The index of the top entry of the stack in an array-based implementation.

ensureCapacity()

A method to double the size of the array if it is full.

stack[]

An array that holds the entries in an array-based stack.

checkIntegrity()

A method to verify the integrity of the stack.

Vector

A class that behaves like a high-level array, resizing as needed.

VectorStack

A stack implementation where entries are stored in a vector.

lastElement()

A method that returns the last entry in a vector.

add()

A method to add an entry to the vector-based stack.

remove()

A method to remove and return an entry from the vector by index.

clear() (in VectorStack)

A method that clears all entries in the vector.

checkCapacity()

A method to verify and adjust the capacity of the stack.

push() (in VectorStack)

Method to add an entry to the top of a vector-based stack.

pop() (in VectorStack)

Method to remove the last entry from a vector-based stack.

Node Class

A nested class used to represent each node in a linked stack.

LinkedStack

A generic class for a linked stack implementation.

ArrayStack

A generic class for an array-based stack implementation.

Data Structure

A way to organize and store data for efficient access and modification.

ADT (Abstract Data Type)

A model for data structures defined by their behavior from the point of view of a user.

O(1) operation

An operation that takes constant time, regardless of the size of the data structure.

push operation complexity

The complexity of the push operation is generally O(1) in both linked and array-based stacks.