《计算机科学概论(第9版)lectureslide_08》由会员分享，可在线阅读，更多相关《计算机科学概论(第9版)lectureslide_08（53页珍藏版）》请在金锄头文库上搜索。
1、Data Abstraction Basic Data Structures,Chapter 8,Abstract Data Type,Abstract Data Type as a design tool Concerns only on the important concept or model No concern on implementation details. Stack & Queue is an example of ADT An array is not ADT.,What is the difference?,Stack & Queue vs. Array Arrays
2、 are data storage structures while stacks and queues are specialized DS and used as programmers tools. Stack a container that allows push and pop Queue - a container that allows enqueue and dequeue No concern on implementation details. In an array any item can be accessed, while in these data struct
3、ures access is restricted. They are more abstract than arrays.,push,pop,Stack,Queue,LIFO (Last-In-First-Out) access method,enqueue,dequeue,FIFO (First-In-First-Out) access method,Stacks and queues are used for temporary storage, but in different situations,Stacks are Used for,handling nested structu
4、res: processing directories within directories evaluating expressions within expressions handling branching processes traversing a branching tree structure planning a move in a chess game tracking the sequence of method calls in a Java program,Stacks,A stack is a data structure that only allows item
5、s to be inserted and removed at one end We call this end the top of the stack The other end is called the bottom Access to other items in the stack is not allowed A LIFO (Last In First Out) data structure,Using a Stack,What Are Stacks Used For?,Most programming languages use a “call stack” to implem
6、ent function calling When a method is called, its line number and other useful information are pushed (inserted) on the call stack When a method ends, it is popped (removed) from the call stack and execution restarts at the indicated line number in the method that is now at the top of the stack,The
7、Call Stack,This is a display of the call stack (from the Eclipse Debug window),Top of the stack: most recently called method.,Bottom of the stack: least recently called method,Call Stacks and Recursion,A call stack is what makes recursion possible Stacks are also important when traversing tree data
8、structures They enable us to “backtrack” through the tree Well see more about this later in the course,Stack Operations,A stack should implement (at least) these operations: push insert an item at the top of the stack pop remove and return the top item peek return the top item (without removing it)
9、These operations should be performed efficiently in O(1) time,Stack Implementation,The stack ADT can be implemented using a variety of data structures. We will look at two: Arrays Linked Lists Both implementations must implement all the stack operations,Queues,A queue is a data structure that only a
10、llows items to be inserted at the end and removed from the front “Queue” is the British word for a line (or line-up) Queues are FIFO (First In First Out) data structures “fair” data structures,Using a Queue,What Can You Use a Queue For?,Processing inputs and outputs to screen (console) Server reques
11、ts Instant messaging servers queue up incoming messages Database requests Print queues One printer for dozens of computers Operating systems use queues to schedule CPU jobs Simulations,Queue Operations,A queue should implement (at least) these operations: enqueue insert an item at the back of the qu
12、eue dequeue remove an item from the front peek return the item at the front of the queue without removing it Like stacks it is assumed that these operations will be implemented efficiently That is, in constant time,Queue: Array Implementation,First consider using an array as the underlying structure
13、 for a queue, one plan would be to Make the back of the queue the current size of the queue (i.e., the number of elements stored) Make the front of the queue index 0 Inserting an item can be performed in constant time But removing an item would require shifting all elements in the queue to the left
14、which is too slow! Therefore we need to find another way,Linked List,Linked lists are among the simplest and most common data structures; they provide an easy implementation for several important abstract data structures, including stacks, queues, hash tables, symbolic expressions, and skip lists. D
15、etail about linked listed ( covered later),Data Structures,What is a Data structure? Associate different types of data together under one name. What is a Class? Data structures can be extended into a conglomeration of data types and functions which form the basis of an object.,Defining a Data Struct
16、ure,When we define a data structure we are in fact creating a new data type of our own. i.e Using predefined types or previously user defined types. Such new types are then used to reference a variables type within a C/C+ program,Declaration,struct my_record int height; int weight; A simple data str
17、ucture declaration which can now be used within a C/C+ program.,Basic Use,Using our simple structure void main (void) struct my_record int height; int weight; ; struct my_record person1,person2; . / use the new variables So we have two new variables person1 & person 2 and each will have associated with it two integer variables height and weight.,
