CS210 · Stacks & Queues · Annotated SlidesStacks and Queues
Original
Overview

Stacks and Queues

The stack ADT (LIFO) and its array and linked implementations, parentheses and HTML tag matching, evaluating arithmetic expressions with two stacks; the queue ADT (FIFO), circular-array implementation, round robin, and the Big-O of each implementation.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 39 slides
  1. 1 Presentation for use with the textbook Data Structures and Algorithms in Java, 6
  2. 2 last in first out q
  3. 3 Stack Interface in Java
  4. 4 Example
  5. 5 Slide 5
  6. 6 Recursion and Queue
  7. 7 0
  8. 8 know to
  9. 9 how match to call
  10. 10 Performance and Limitations
  11. 11 Array-based Stack in Java
  12. 12 Example Use in Java
  13. 13 Parentheses Matching
  14. 14 Parenthesis Matching (Java)
  15. 15 HTML Tag Matching
  16. 16 HTML Tag Matching (Java)
  17. 17 Evaluating Arithmetic Expressions
  18. 18 Algorithm for Evaluating Expressions
  19. 19 Array Stack Big-oh
  20. 20 Linked List Stack Big-oh
  21. 21 Algorithm on an Example Expression
  22. 22 Presentation for use with the textbook Data Structures and Algorithms in Java, 6
  23. 23 The Queue ADT
  24. 24 I
  25. 25 return
  26. 26 Applications of Queues
  27. 27 big
  28. 28 Queue Operations
  29. 29 Queue Operations (cont.)
  30. 30 Queue Operations (cont.)
  31. 31 Traverse
  32. 32 Queue Interface in Java
  33. 33 Array-based Implementation
  34. 34 Array-based Implementation (2)
  35. 35 Comparison to java.util.Queue
  36. 36 Application: Round Robin Schedulers
  37. 37 Array Queue Big-oh
  38. 38 DEQueue Big-oh
  39. 39 LinkedList Queue Big-oh
Slide 1 / 39

Presentation for use with the textbook Data Structures and Algorithms in Java, 6

Slide 1: Presentation for use with the textbook Data Structures and Algorithms in Java, 6
Slide 2 / 39

last in first out q

Slide 2: last in first out q

Exam angle

PredictionQ1

After push(1), push(2), push(3), pop(), the top is:

Slide 3 / 39

Stack Interface in Java

Slide 3: Stack Interface in Java
Slide 4 / 39

Example

Slide 4: Example
Slide 5 / 39

Slide 5

Slide 5: Slide 5
Slide 6 / 39

Recursion and Queue

Slide 6: Recursion and Queue
Slide 7 / 39

0

Slide 7: 0
Slide 8 / 39

know to

Slide 8: know to
Slide 9 / 39

how match to call

Slide 9: how match to call
Slide 10 / 39

Performance and Limitations

Slide 10: Performance and Limitations

Notes

  1. Array stack: O(1) operations but fixed capacity.

Slide 11 / 39

Array-based Stack in Java

Slide 11: Array-based Stack in Java
Slide 12 / 39

Example Use in Java

Slide 12: Example Use in Java
Slide 13 / 39

Parentheses Matching

Slide 13: Parentheses Matching

Notes

  1. Parentheses matching: push openers, pop and compare on closers; stack empty at the end = balanced.

Exam angle

PredictionQ1

How does a stack check that ( [ { } ] ) is balanced?

Compare with the model answer

Scan left to right: push every opening symbol; on a closing symbol pop and check it matches. If a pop finds the stack empty or a mismatch, it’s unbalanced; at the end the stack must be empty.

Slide 14 / 39

Parenthesis Matching (Java)

Slide 14: Parenthesis Matching (Java)
Slide 15 / 39

HTML Tag Matching

Slide 15: HTML Tag Matching
Slide 16 / 39

HTML Tag Matching (Java)

Slide 16: HTML Tag Matching (Java)
Slide 17 / 39

Evaluating Arithmetic Expressions

Slide 17: Evaluating Arithmetic Expressions
Slide 18 / 39

Algorithm for Evaluating Expressions

Slide 18: Algorithm for Evaluating Expressions
Slide 19 / 39

Array Stack Big-oh

Slide 19: Array Stack Big-oh
Slide 20 / 39

Linked List Stack Big-oh

Slide 20: Linked List Stack Big-oh
Slide 21 / 39

Algorithm on an Example Expression

Slide 21: Algorithm on an Example Expression
Slide 22 / 39

Presentation for use with the textbook Data Structures and Algorithms in Java, 6

Slide 22: Presentation for use with the textbook Data Structures and Algorithms in Java, 6
Slide 23 / 39

The Queue ADT

Slide 23: The Queue ADT

Exam angle

PredictionQ1

enqueue(1), enqueue(2), enqueue(3), dequeue() returns:

Slide 24 / 39

I

Slide 24: I
Slide 25 / 39

return

Slide 25: return
Slide 26 / 39

Applications of Queues

Slide 26: Applications of Queues
Slide 27 / 39

big

Slide 27: big
Slide 28 / 39

Queue Operations

Slide 28: Queue Operations
Slide 29 / 39

Queue Operations (cont.)

Slide 29: Queue Operations (cont.)
Slide 30 / 39

Queue Operations (cont.)

Slide 30: Queue Operations (cont.)
Slide 31 / 39

Traverse

Slide 31: Traverse
Slide 32 / 39

Queue Interface in Java

Slide 32: Queue Interface in Java
Slide 33 / 39

Array-based Implementation

Slide 33: Array-based Implementation

Exam angle

PredictionQ1

In a circular array queue of capacity N, the index after r is:

Slide 34 / 39

Array-based Implementation (2)

Slide 34: Array-based Implementation (2)
Slide 35 / 39

Comparison to java.util.Queue

Slide 35: Comparison to java.util.Queue
Slide 36 / 39

Application: Round Robin Schedulers

Slide 36: Application: Round Robin Schedulers
Slide 37 / 39

Array Queue Big-oh

Slide 37: Array Queue Big-oh

Notes

  1. Array queue and linked queue: all operations O(1).

Slide 38 / 39

DEQueue Big-oh

Slide 38: DEQueue Big-oh
Slide 39 / 39

LinkedList Queue Big-oh

Slide 39: LinkedList Queue Big-oh