1、The List, Stack, and Queue ADTs Abstract data type (ADT): An ADT is a set of objects together with a set operations to be performed on these objects.An ADT corresponds to (one or more) classes in an OO language such as C+ and Java.There may be more than one implementation for the same ADT, with diff
2、erent advantages in terms of efficiency, ease of use, ease of implementation. We will review the ADTs for lists, stacks, and queues, mainly based on array or linked list implementations. We will also study some typical applications of these ADTs to learn when to use them.,The List ADT:A list of obje
3、cts A1, A2, , An, where n is the size of the list. Some typical operations include find, insert, remove, findKth, printList, makeEmpty.An array implementation requires (n) time for insert and remove operations in the worst case.A linked list implementation offers the flexibility of dynamically growi
4、ng the list and of O(1) time insert and remove operations (assuming the position in the list is known).,remove,insert,Programming Details in Linked List Implementation:Use three classes for the List ADT:(1) ListNode (for the individual nodes, or objects, in the list); (2) LinkedList (for the list ob
5、ject itself consisting of the nodes); and (3) LinkedListItr (for the current location in a LinkedList object, in a particular application).Each class consists of one or more constructor functions.The ListNode class contains two member variables: element for the “data” field and next for the link fie
6、ld lining to the next node in the list.,Linked List Implementation (contd):The LinkedListItr class contains functions isPastEnd, retrieve, advance; and contains a member variable current for the current location in a LinkedList object.The LinkedList class may use a dummy header node to be the first
7、node in the list which somewhat simplifies the insert function (thus, an “empty” list contains the header node as the only node in the list). The functions included in the class are find, remove, findPrevious, and insert. Variations of linked list implementations includedoubly linked lists each node
8、 uses two link fields to link to the two neighboring nodes in the list, respectively; andcircular linked lists the last node in the list is linked to the front of the list, eliminating the header node.,Two Applications of Linked Lists: Polynomials (in a single variable x) use nodes to represent the
9、non-zero terms arranged in decreasing order of the exponents; typical operations include: constructor (initialize the zero polynomial in constant time); add (in O(m + n) time for two polynomials of m and n terms, respectively); and multiply (in O(mn(min(m,n) time for two polynomials of m and n terms
10、, respectively). Radix sort sort n numbers in the range of 0m1, where m bp for some constant p (of moderate size), based on a multi-pass bucket sort technique, resulting in O(p(n + b) time using O(b+ n) space; this is a linear time O(n) algorithm when p is a constant and b = O(n). For example, m = 2
11、32 for 32-bit unsigned integers. Choose b = 211 = 2048, then m b3 and n numbers can be sorted in O(3(n + 211) = O(n) time.,Algorithm for adding two polynomials in linked lists p, q:set p, q to point to the two first nodes (no headers) initialize a linked list r for a zero polynomial while p != null
12、and q != null if p.exp q.exp create a node storing p.coeff and p.exp, then insert at the end of list r; advance p else if q.exp p.exp create a node storing q.coeff and q.exp, then insert at the end of list r; advance q else if p.exp = q.exp if p.coeff + q.coeff != 0 create a node storing p.coeff + q
13、.coeff and p.exp, then insert at the end of list r advance p, q if p != null copy the remaining terms of p to end of r else if q != null copy the remaining terms of q to end of r Each iteration of the while loop takes O(1) time, moving at least one of the two pointers p and q one position over. Any
14、remaining terms will be copied after the loop. Thus the total time is O(m+n) because there are a total of m+n terms in the two polynomials.,Algorithm for multiplying two polynomials in linked lists p, q:set p to the first node (no header) of one polynomial initialize a linked list r for a zero polyn
15、omial while p != null copy list q to a new list t multiply the term pointed by p to each term of t by set t.exp += p.exp set t.coeff *= p.coeff add polynomial t to polynomial r (then discard t) advance p If polynomial p, q have m, n terms, respectively, the while loop runs m iterations. In each iter
16、ation, producing the polynomial t (copy and multiply) costs O(n) time since the length of t is O(n). Adding polynomial t to r runs in time O(n + length of r). Since the length of r in the beginning of iteration k is O(k 1)n), so the total time of the algorithm is The choice of m and n is arbitrary,
17、so we can achieve O(mn(min(m,n) time.,An Example demonstrating Radix Sort: Given n = 10 numbers: 64, 8, 216, 512, 27, 729, 0, 1, 343, 125. Use b = 10 buckets and sort the numbers using the least significant digits in the first pass (i.e., distribute the numbers into10 buckets based on the last digit
18、s), then sort the list of numbers resulting from the first pass using the next significant digits; finally, sort the list (of pass two) using the most significant digits.,0 1 2 3 4 5 6 7 8 9 000 001 512 343 064 125 216 027 008 729,008 729 001 216 027 000 512 125 343 064,10 buckets,list after first p
19、ass,list after second pass,064 027 008 001 000 125 216 343 512 729,list after the third pass,The Stack ADT:A stack is a list with two operations insert and delete, such that the most recently inserted item is deleted first (hence the name LIFO, for a last-in-first-out structure).A stack is typically
20、 pictured as a “stack of items” arranged vertically where the insertion and deletion take place at the “top”The stack ADT supports operations isFull, isEmpty, makeEmpty, push, pop, top.,top,push (insert),pop (delete),Application of Stacks: Expressions from Infix to Postfix. An infix expression is wh
21、at we typically use in arithmetic (or algebra), where an operator (+, , *, etc.) is written between the two neighboring operands (for binary operators). For example, a + b, or a + b * c (multiply first before add due to higher precedence), (a + b) * c (use parentheses to alter precedence). As much a
22、s we are used to infix expressions, they are harder for the computer to process and evaluate. A postfix expression (also known as Polish notation since it was invented by a Polish logician in the 1920s), uses a different convention for writing arithmetic expressions, totally doing away the parenthes
23、es and making the expressions more efficient to evaluate by computers. The idea is to write each operator after the two corresponding operands. For example, ab+, abc*+, ab+c*, respectively, are the postfix expressions corresponding to the preceding examples.,The idea of converting infix to postfix u
24、sing a stack: Example. Convert infix a + b * c to postfix abc*+. We scan the input stream left to right, output each operand as they are scanned. The main idea is that when encountering an operator, it is pushed onto the stack if the stack is empty, or if it has a higher precedence than that of the
25、stack top. Thus, the following chart demonstrates the snapshots of the input stream vs. the stack and the output during the conversion process:,next token stack output comments (Initially) empty none a empty a always output operand + + a push when stack empty b + a b always output operand * + * a b
26、push if higher precedence c + * a b c always output operand (at end) empty a b c * + pop everything off stack,Another example: Convert infix a*(b + c)/d to postfix abc+*d/. next token stack output comments (Initially) empty none a empty a output operand * * a push operator if stack empty ( *( a alwa
27、ys push ( b *( ab output operand + *(+ ab push operator if stack top ( c *(+ abc output operand ) * abc+ pop all operators until ( / / abc+* pop *, push / d / abc+*d output operand (at end) empty abc+*d/ pop everything off stack Note that the token ( is pushed onto stack when scanned; once it is in
28、the stack all operators are considered with a higher precedence against (. Also, we need to resolve operators with left or right-associative properties. For example, a+b+c means (a+b)+c but abc means a(bc).,We define the precedence levels of various operators including the parentheses, distinguishin
29、g whether the operators are currently inside the stack or they are incoming tokens. operator tokens in-stack precedence in-coming precedence (ISP) (ICP) ) (N/A) (N/A) 3 4 *, / 2 2 +, 1 1 ( 0 4 $ 1 (N/A) The idea is that when encountering an in-coming operator, pop all operators in the stack that hav
30、e a higher or equal ISP than the ICP of the new operator, then push the new operator onto the stack. The initial stack is marked with a “bottom marker” $ with a 1 precedence, which serves as a sentinel symbol.,Algorithm Converting Infix Expression E to Postfix Notation:create a stack and push the bo
31、ttom-marker $ onto stack perform the following steps forever (until exit out of it) set x = nextToken(E) if x = end-of-input pop all operators off the stack and output (except the marker $) exit out of the loop else if x = operand, output x else if x = ) pop all operators off stack and output each u
32、ntil (; pop ( off but dont output it else pop all operators off stack as long as their ISP ICP(x) push x onto stack Note that the time complexity of the algorithm is O(n), n = the number of input tokens. This algorithm assumes no input errors.,The Queue ADT:A queue is a fist-in-first-out (FIFO) stru
33、cture in which the first (oldest) object inserted will be the first to be deleted.A linked list implementation is straightforward, with a “pointer” front pointing to the fist (oldest) object and another pointer back pointing to the most recent object in the list. Insertions take place at the back of
34、 the list, deletions at the front. Both operations can be done in O(1) time.,back,After insertion,New object,front,After deletion,(deleted object),A circular (wrap-around) array implementation of queues: When a fixed sized array is used to store the list of objects in a queue, as objects come and le
35、ave, the portion of the array that contains the current objects “drifts” towards the end of the array, demonstrated in the following snapshots:A clever solution is let the array wraparound, so that its end continues to the front.,front,back,front,back,(drifting towards back),A circular array impleme
36、ntation of queues (contd):The class uses 4 private instance variables: the array (of some default size), currentSize (count of current objects), front, and back (indexes of the first and last objects in the array, respectively). Initially, front = currentSize = 0, back = 1.Some public class methods include isEmpty(), isFull(), makeEmpty(), getFront(), enqueue(), and dequeue().Queues are used for scheduler applications, as in operating systems, event processing, and graph traversals.,front,back,wrap-around,
