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.

Explore the fundamentals of stacks and queues in CSC 1061. Understand the Last In, First Out (LIFO) principle of stacks and First In, First Out (FIFO) principle of queues. This quiz covers implementation methods, operations, and common errors associated with these data structures.