CSC 1061: Stacks and Queues Overview

CSC 1061: Stacks, Queues, Graphs

• Stacks (LIFO):

  • A stack is a sequence of items where items are inserted and removed from one end, called the top.
  • Last In, First Out (LIFO)
  • Think of a stack of books; the last book placed on top is the first one you take off.
  • Operations: push (add to top), pop (remove from top), top (view top item), size (number of items), isEmpty (check if empty).
  • Error conditions: stack overflow (trying to push onto a full stack), stack underflow (trying to pop from an empty stack)
  • Implementation: Arrays (fixed size), Linked Lists (dynamic size)

• Stack Implementation (LIFO):

  • Array implementation: Simple and efficient but limited to a fixed size; memory can be wasted if the size is too large
  • Linked List implementation: Dynamic memory allocation, no size limit
  • Both implementations: Constant time efficiency (O(1)) for push and pop operations

• Queue (FIFO):

  • A queue is a sequence of items where items are added to one end (rear/tail) and removed from the other (front/head).
  • First In, First Out (FIFO).
  • Think of a line; the first person in line is the first to be served.
  • Operations: enqueue (add to rear), dequeue (remove from front), first (view front item), last (view rear item), size (number of items), isEmpty (check if empty).
  • Implementation: Linked Lists (dynamic size), Circular Arrays (fixed size)

• Queue Implementation (FIFO):

  • Linked List Implementation: No size limitation; Dynamic memory management
  • Circular Array Implementation: Simple and efficient but limited to a fixed size; memory can be wasted if the size is too large.

• Priority Queues:

  • A priority queue is a queue where some items have higher priorities than others and are serviced first.
  • Often implemented as a list of queues or a specialized data structure.

• Graphs:

  • A graph is a non-linear data structure consisting of nodes (vertices) connected by links (edges).
  • Used to represent relationships between objects.
  • Terminology: vertices, edges, directed/undirected graphs, loops, paths, simple graphs, labeled graphs, adjacency matrix, adjacency list.

• Graph Traversals:

  • Depth-first traversal uses a stack to explore a path deeply before backtracking.
  • Breadth-first traversal uses a queue to visit all neighbors before moving deeper.

• Graph Algorithms:

  • Path finding: Determines if a path between two nodes exists.
  • Shortest path: Finds the path with the lowest weighted sum between two nodes, a common use of Dijkstra's algorithm.

• Additional Information:

  • Examples/Applications: Undo/Redo operations in text editors, web browser history, function calls (call stack), solving mazes, calculators (Reverse Polish Notation), file I/O buffering, customer service phone lines, traffic flow modeling.
  • Common Data Structures used in the examples: Arrays, Linked Lists, Stack implementations.
  • Implementation Notes: Circular arrays ensure that data is stored in a circular fashion to prevent array size wastage within queues.

Additional Notes/Tasks

• Pre-work grade:

  • Post weekly discussion questions and research.
  • Complete the pre-work quiz.
  • Complete week 14 content (100%).

• Help/Support:

  • Student Office Hours: By Appointment.
  • Email: [email protected]
  • On-Campus Tutoring: https://www.rrcc.edu/learning-commons/tutoring
  • Online Tutoring: D2L > Content > Resources for Help.