Answer Happy

Review Figure 3.1 on page 64. Describe the depicted operations. Associate the operations with both a queue and a stack. Why do additions and removals at the tail pose additional complexities? (p 64) Open Data Structures in Java, section 3.1

$3.1 Linked Lists head tail head 十十十, 中中中中中。 tail add(x) head tail remove() head +++ {de- tail pop() head tail push(y) 中中中中 Figure 3.1: A sequence of Queue (add(x) and remove()) and Stack (push(x) and pop() operations on an SLList. SLList | class Node { Tx; Node next; For efficiency, an SLList uses variables head and tail to keep track of the first and last node in the sequence, as well as an integer n to keep track of the length of the sequence: SLList Node head; Node Lail; int n; A sequence of Stack and Queue operations on an SLList is illustrated in Figure 3.1. An SLList can efficiently implement the Stack operations push() and pop() by adding and removing elements at the head of the sequence. The push() operation simply creates a new node u with data value x, sets u.next to the old head of the list and makes u the new head of the list. Finally, it increments n since the size of the SLList has increased by one: