Lists – Part IADTsThe List ADTListsAccess(L,i)Length(L)Concat(L1,L2)MakeEmptyList()IsEmptyList(L)Special Types of ListsStacksSlide 12Stack ADTTop(L)Pop(L)Push(x,L)MakeEmptyStack()IsEmptyStack(L)UML for Stack ClassQueue ADTQueue ExampleSlide 22Enqueue(x,L)Dequeue(L)Front(L)MakeEmptyQueue()IsEmptyQueue(L)UML for Queue classList representationsSeptember 05September 05KraemerKraemerUGA/CSCI 2720UGA/CSCI 2720Lists – Part ILists – Part ICSCI 2720CSCI 2720Eileen KraemerEileen KraemerThe University of GeorgiaThe University of GeorgiaADTsADTsADT = abstract data typeADT = abstract data typea mathematical specification of a set of a mathematical specification of a set of data and the set of operations that can be data and the set of operations that can be performed on the data. performed on the data. the focus is on the definitions of the the focus is on the definitions of the constructor that returns an abstract handle constructor that returns an abstract handle that represents the data, and the various that represents the data, and the various operations with their arguments.operations with their arguments. actual implementation is not definedactual implementation is not definedThe List ADTThe List ADTList = ordered sequence of elements List = ordered sequence of elements <x<x00, …, x, …, xn-1n-1>.>.Length of the list: |L| Length of the list: |L| –Read “cardinality of L”Read “cardinality of L”–| <x| <x00, …, x, …, xn-1n-1>| = n>| = n–Can be any non-negative numberCan be any non-negative numberL[i]L[i]–ith element of list L, ith element of list L, provided 0 <= i <= |L|provided 0 <= i <= |L|ListsListsWe’ll define several types of lists, We’ll define several types of lists, each with their own ADTeach with their own ADTCommon operations:Common operations:–Access(L,i)Access(L,i)–Length(L)Length(L)–Concat(LConcat(L11,L,L22))–MakeEmptyList()MakeEmptyList()–IsEmptyList(L)IsEmptyList(L)Access(L,i)Access(L,i)Return L[i]Return L[i]–Return error if i out of rangeReturn error if i out of range i < 0i < 0i > |L| - 1i > |L| - 1Length(L)Length(L)return | L |return | L |Concat(LConcat(L11,L,L22))Return the result of concatenating LReturn the result of concatenating L11 with Lwith L22If LIf L11 = <x = <x00, …, x, …, xn-1n-1> and L> and L22 = <y = <y00, …, , …, yym-1m-1>, then Concat (L>, then Concat (L1, 1, LL22) returns the ) returns the combined listcombined list<x<x00, …, x, …, xn-1,n-1,yy00, …, y, …, ym-1m-1>>MakeEmptyList()MakeEmptyList()Returns the empty list <>Returns the empty list <>IsEmptyList(L)IsEmptyList(L)Returns Returns truetrue if |l| == 0 if |l| == 0Otherwise returns Otherwise returns falsefalseSpecial Types of ListsSpecial Types of ListsStackStack–Can be modified only by adding and Can be modified only by adding and removing items at one endremoving items at one endQueueQueue–Can be modified only by adding items at Can be modified only by adding items at one end and removing them at the otherone end and removing them at the otherStacksStacksA Stack Applet exampleA Stack Applet exampleStacksStacksPush – add new item at the topPush – add new item at the topPop – remove item from the topPop – remove item from the topTop – peek at item on the top, but Top – peek at item on the top, but don’t remove itdon’t remove itLIFO lists – last in, first outLIFO lists – last in, first outused to implement recursion, used to implement recursion, reversing of strings, bracket-checking, reversing of strings, bracket-checking, moremoreStack ADTStack ADTTop(L)Top(L)Pop(L)Pop(L)Push(x,L)Push(x,L)MakeEmptyStack()MakeEmptyStack()IsEmptyStack(L)IsEmptyStack(L)Top(L)Top(L)Return last element of LReturn last element of LSame as Access(L, |L| -1)Same as Access(L, |L| -1)Error results if L is emptyError results if L is emptyPop(L)Pop(L)Remove and return last element of LRemove and return last element of LReturn Top(L) and replace L with Return Top(L) and replace L with <L[0], ….L[|L| -2]><L[0], ….L[|L| -2]>Error results if L is emptyError results if L is emptyPush(x,L)Push(x,L)Add x at the end of LAdd x at the end of LReplace L by Concat(L,<x>)Replace L by Concat(L,<x>)MakeEmptyStack()MakeEmptyStack()Return the empty list <>Return the empty list <>O(1)O(1)IsEmptyStack(L)IsEmptyStack(L)Return Return truetrue if |L| == 0 if |L| == 0Otherwise return Otherwise return falsefalseUML for Stack ClassUML for Stack ClassQueue ADTQueue ADTsimilar to stack, except that the first item to be similar to stack, except that the first item to be inserted is the first one to be removed.inserted is the first one to be removed.This mechanism is called First-In-First-Out (FIFO). This mechanism is called First-In-First-Out (FIFO). Placing an item in a queue is called “insertion or Placing an item in a queue is called “insertion or enqueue”, which is done at the end of the queue enqueue”, which is done at the end of the queue called “rear”.called “rear”.Removing an item from a queue is called Removing an item from a queue is called “deletion or dequeue”, which is done at the other “deletion or dequeue”, which is done at the other end of the queue called “front”.end of the queue called “front”.Some of the applications are : printer queue, Some of the applications are : printer queue, keystroke queue, etc.keystroke queue, etc.Queue ExampleQueue ExampleA queue appletA queue appletQueue ADTQueue ADTEnqueue(x,L)Enqueue(x,L)Dequeue(L)Dequeue(L)Front(L)Front(L)MakeEmptyQueue()MakeEmptyQueue()IsEmptyQueue(L)IsEmptyQueue(L)Enqueue(x,L)Enqueue(x,L)Add x at the end of LAdd x at the end of LReplace L by Concat(L,<x>)Replace L by Concat(L,<x>)O(1)O(1)Dequeue(L)Dequeue(L)Remove and return the first element Remove and return the first element of Lof LReplace L by <L[1] … L[|L|-1]> and Replace L by <L[1] … L[|L|-1]> and return L[0]return L[0]Error results if L is emptyError results if L is emptyFront(L)Front(L)Return the first element of LReturn the first element of LReturn L[0]Return L[0]Error results if L is emptyError results if L is emptyMakeEmptyQueue()MakeEmptyQueue()Return the empty list <>Return the empty list <>IsEmptyQueue(L)IsEmptyQueue(L)Return Return truetrue if |L| ==0 if |L| ==0Otherwise return Otherwise return