Stacks, Queues, and DequesSlide 2Array implementation of stacksPushing and poppingAfter poppingSharing spaceError checkingPointers and referencesCreating referencesCreating links in JavaLinked-list implementation of stacksLinked-list implementation detailsArray implementation of queuesSlide 14Circular arraysFull and empty queuesFull and empty queues: solutionsLinked-list implementation of queuesSLL implementation of queuesEnqueueing a nodeDequeueing a nodeQueue implementation detailsDequesStack ADTA queue ADTjava.util Interface Queue<E>A deque ADTUsing ArrayListsjava.util Interface Deque<E>The EndStacks, Queues, and Deques2Stacks, Queues, and DequesA stack is a last in, first out (LIFO) data structureItems are removed from a stack in the reverse order from the way they were insertedA queue is a first in, first out (FIFO) data structureItems are removed from a queue in the same order as they were insertedA deque is a double-ended queue—items can be inserted and removed at either end3Array implementation of stacksTo implement a stack, items are inserted and removed at the same end (called the top)Efficient array implementation requires that the top of the stack be towards the center of the array, not fixed at one endTo use an array to implement a stack, you need both the array itself and an integerThe integer tells you either:Which location is currently the top of the stack, orHow many elements are in the stack4Pushing and poppingIf the bottom of the stack is at location 0, then an empty stack is represented by top = -1 or count = 0To add (push) an element, either:Increment top and store the element in stk[top], orStore the element in stk[count] and increment countTo remove (pop) an element, either:Get the element from stk[top] and decrement top, orDecrement count and get the element in stk[count]top = 3 or count = 40 1 2 3 4 5 6 7 8 917 23 97 44stk:5After poppingWhen you pop an element, do you just leave the “deleted” element sitting in the array?The surprising answer is, “it depends”If this is an array of primitives, or if you are programming in C or C++, then doing anything more is just a waste of timeIf you are programming in Java, and the array contains objects, you should set the “deleted” array element to nullWhy? To allow it to be garbage collected!top = 2 or count = 30 1 2 3 4 5 6 7 8 917 23 97 44stk:6Sharing spaceOf course, the bottom of the stack could be at the other endtop = 6or count = 4172397440 1 2 3 4 5 6 7 8 9stk:Sometimes this is done to allow two stacks to share the same storage areatopStk2 = 61723974449 57 30 1 2 3 4 5 6 7 8 9stks:topStk1 = 27Error checkingThere are two stack errors that can occur:Underflow: trying to pop (or peek at) an empty stackOverflow: trying to push onto an already full stackFor underflow, you should throw an exceptionIf you don’t catch it yourself, Java will throw an ArrayIndexOutOfBounds exceptionYou could create your own, more informative exceptionFor overflow, you could do the same thingsOr, you could check for the problem, and copy everything into a new, larger array8Pointers and referencesIn C and C++ we have “pointers,” while in Java we have “references”These are essentially the same thingThe difference is that C and C++ allow you to modify pointers in arbitrary ways, and to point to anythingIn Java, a reference is more of a “black box,” or ADTAvailable operations are:dereference (“follow”)copycompare for equalityThere are constraints on what kind of thing is referenced: for example, a reference to an array of int can only refer to an array of int9Creating referencesThe keyword new creates a new object, but also returns a reference to that objectFor example, Person p = new Person("John")new Person("John") creates the object and returns a reference to itWe can assign this reference to p, or use it in other ways10Creating links in Javaclass Cell { int value; Cell next;Cell (int v, Cell n) { value = v; next = n; }}Cell temp = new Cell(17, null);temp = new Cell(23, temp);temp = new Cell(97, temp);Cell myStack = new Cell(44, temp);44 97 23 17myStack:11Linked-list implementation of stacksSince all the action happens at the top of a stack, a singly-linked list (SLL) is a fine way to implement itThe header of the list points to the top of the stack44 97 23 17myStack:Pushing is inserting an element at the front of the listPopping is removing an element from the front of the list12Linked-list implementation detailsWith a linked-list representation, overflow will not happen (unless you exhaust memory, which is another kind of problem)Underflow can happen, and should be handled the same way as for an array implementationWhen a node is popped from a list, and the node references an object, the reference (the pointer in the node) does not need to be set to nullUnlike an array implementation, it really is removed--you can no longer get to it from the linked listHence, garbage collection can occur as appropriate13Array implementation of queuesA queue is a first in, first out (FIFO) data structureThis is accomplished by inserting at one end (the rear) and deleting from the other (the front)To insert: put new element in location 4, and set rear to 4To delete: take element from location 0, and set front to 1 17 23 97 440 1 2 3 4 5 6 7myQueue:rear = 3front = 014Array implementation of queuesNotice how the array contents “crawl” to the right as elements are inserted and deletedThis will be a problem after a while!17 23 97 44 333After insertion:23 97 44 333After deletion:rear = 4front = 117 23 97 44Initial queue:rear = 3front = 015Circular arraysWe can treat the array holding the queue elements as circular (joined at the ends)44 55 11 22 330 1 2 3 4 5 6 7myQueue:rear = 1front = 5Elements were added to this queue in the order 11, 22, 33, 44, 55, and will be removed in the same orderUse: front = (front + 1) % myQueue.length;and: rear = (rear + 1) % myQueue.length;16Full and empty queuesIf the queue were to become completely full, it would look like this:If we were then to remove
View Full Document
Unlocking...