.jpg)
Linked Lists, Stacks and Queues
Table of Contents
.png)
Session 3 (lecture): Stacks and Queues
.png)
Slides
-trans.png)
Readings
-
Data Structures and Problem Solving Using Java by Mark A. Weiss (3th edition): sections 6.3 (Queues) and 6.4 (Linked Lists); introduction to section 15.1 (Dynamic Array Implementations and section 15.1.2 (Queues); introduction to section 15.2 (Linked-list implementations) and section 15.2.2 (Queues); section 15.4 (Double-ended Queues); section 6.8 (Priority Queues).
-
Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia (1st ed.): sections 3.2 (Queues), 3.3 (Linked Lists), 3.4 (Double-Ended Queues) and 6.1 (The Priority Queue Abstract Data Type).
-
Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia (4th ed.): sections 3.2 (Singly Linked Lists), 5.2 (Queues), 5.3 (Double-Ended Queues) and 8.1 (The Priority Queue Abstract Data Type).
.png)
Homework
Recap
Review the contents of the class and read the recommended bibliography.
Question
Design a solution to the multiple-symbols balancing problem introduced in class. Focus on the design: it is not strictly necessary to program it.
Question
When implementing a stack based on a linked-list, why is it more efficient to use as top of the stack the head of the list instead of its tail?
Exercise
Program an array-based stack. When the array is full and an attempt to push a new object is done, your solution must, instead of throwing an exception, replace the array with a new array of double size. When doing it, remember to copy the data from the old array into the new one.
Question
When implementing queues using linked-lists, data objects are inserted at the tail of the list and extracted from the head. It could be done the other way around, that is, extracting data from the tail and inserting it at the head. However, it would be much less efficient. Explain why.
Exercise
Program a queue using an array.
.png)