CS210 · Annotated SlidesStacks & Queues — Stacks and Queues
Stacks & Queues · Annotated slides

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.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Presentation for use with the textbook Data Structures and Algorithms in Java, 6
Exam weight Low
    Slide 2: last in first out q
    Exam weight High
    1. Stack = last in, first out: push, pop, top, size, isEmpty.
    🎯 How this can come up · 1 question
    MCQ

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

    Slide 3: Stack Interface in Java
    Exam weight Low
      Slide 4: Example
      Exam weight Low
        Slide 5: Slide 5
        Exam weight Low
          Slide 6: Recursion and Queue
          Exam weight Low
            Slide 7: 0
            Exam weight Low
              Slide 8: know to
              Exam weight Low
                Slide 9: how match to call
                Exam weight Low
                  Slide 10: Performance and Limitations
                  Exam weight Low
                  1. Array stack: O(1) operations but fixed capacity.
                  Slide 11: Array-based Stack in Java
                  Exam weight Low
                    Slide 12: Example Use in Java
                    Exam weight Low

                      Parentheses Matching

                      • Each “(”, “{”, or “[” must be paired with a matching “)”, “}”, or “[”
                        • correct: ()[]
                        • correct: ((()[]
                        • incorrect: )()[]
                        • incorrect: ({[ ])}
                        • incorrect: (

                      © 2014 Goodrich, Tamassia, Goldwasser

                      Stacks

                      13
                      Exam weight High
                      1. Parentheses matching: push openers, pop and compare on closers; stack empty at the end = balanced.
                      🎯 How this can come up · 1 question
                      Written

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

                      Slide 14: Parenthesis Matching (Java)
                      Exam weight Low
                        Slide 15: HTML Tag Matching
                        Exam weight Low
                          Slide 16: HTML Tag Matching (Java)
                          Exam weight Low
                            Slide 17: Evaluating Arithmetic Expressions
                            Exam weight Low
                            1. Expression evaluation uses an operator stack and a value stack with precedence.
                            Slide 18: Algorithm for Evaluating Expressions
                            Exam weight Low
                              Slide 19: Array Stack Big-oh
                              Exam weight Low
                                Slide 20: Linked List Stack Big-oh
                                Exam weight Low
                                  Slide 21: Algorithm on an Example Expression
                                  Exam weight Low
                                    Slide 22: Presentation for use with the textbook Data Structures and Algorithms in Java, 6
                                    Exam weight Low
                                      Slide 23: The Queue ADT
                                      Exam weight High
                                      1. Queue = first in, first out: enqueue, dequeue, first.
                                      🎯 How this can come up · 1 question
                                      MCQ

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

                                      Slide 24: I
                                      Exam weight Low
                                        Slide 25: return
                                        Exam weight Low
                                          Slide 26: Applications of Queues
                                          Exam weight Low
                                            Slide 27: big
                                            Exam weight Low
                                              Slide 28: Queue Operations
                                              Exam weight Low
                                                Slide 29: Queue Operations (cont.)
                                                Exam weight Low
                                                  Slide 30: Queue Operations (cont.)
                                                  Exam weight Low
                                                    Slide 31: Traverse
                                                    Exam weight Low
                                                      Slide 32: Queue Interface in Java
                                                      Exam weight Low
                                                        Slide 33: Array-based Implementation
                                                        Exam weight High
                                                        1. Circular array queue: f (front index) and size; r = (f + size) mod N.
                                                        🎯 How this can come up · 1 question
                                                        MCQ

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

                                                        Slide 34: Array-based Implementation (2)
                                                        Exam weight Low
                                                          Slide 35: Comparison to java.util.Queue
                                                          Exam weight Low
                                                            Slide 36: Application: Round Robin Schedulers
                                                            Exam weight Low
                                                            1. Round robin with a queue: dequeue, serve, enqueue.
                                                            Slide 37: Array Queue Big-oh
                                                            Exam weight Low
                                                            1. Array queue and linked queue: all operations O(1).
                                                            Slide 38: DEQueue Big-oh
                                                            Exam weight Low
                                                              Slide 39: LinkedList Queue Big-oh
                                                              Exam weight Low