Chapter 4 Data Structure 4.2 Stacks The end of a stack at which entries are inserted and deleted is called the top of the stack. The other end is sometimes called the stack's base. To reflect the fact that access to a stack is restricted to the topmost entry, we use special terminology when referring to the insertion and deletion operations. The process of inserting an object on the stack is called a push operation, and the process of deleting an object is called a pop operation. Thus we speak of pushing an entry onto a stack and popping an entry off a stack 堆栈尾部可以进行插入和删除操作的记录称为堆栈的栈顶, 另一端叫做栈底。为了表示如何限制堆栈只能从栈顶访问, 我们用一种特殊的术语来表示插入和删除操作。把,个对象 插入堆栈的操作称为进栈操作,而从堆栈中删除,个对象的 操作称为出栈操作,所以我们常说将一个条目进栈或者将其 出栈。 《什第机美语 4-11
Chapter 4 Data Structure 计算机专业英语 4-11 The end of a stack at which entries are inserted and deleted is called the top of the stack. The other end is sometimes called the stack's base. To reflect the fact that access to a stack is restricted to the topmost entry, we use special terminology when referring to the insertion and deletion operations. The process of inserting an object on the stack is called a push operation, and the process of deleting an object is called a pop operation. Thus we speak of pushing an entry onto a stack and popping an entry off a stack. 堆栈尾部可以进行插入和删除操作的记录称为堆栈的栈顶， 另一端叫做栈底。为了表示如何限制堆栈只能从栈顶访问， 我们用一种特殊的术语来表示插入和删除操作。把一个对象 插入堆栈的操作称为进栈操作，而从堆栈中删除一个对象的 操作称为出栈操作，所以我们常说将一个条目进栈或者将其 出栈。 4.2 Stacks
Chapter 4 Data Structure 4.2 Stacks Backtracking A classic application of a stack involves the execution of a program involving procedures as found in our pseudocode. When the execution of a procedure is requested, the machine must transfer its attention to the procedure; yet later, when the procedure is completed. the machine must return to the original location before continuing. This means that, when the initial transfer is made, there must be a mechanism for remembering the location to which execution ultimately returns 回溯 堆栈的一个典型应用发生在一个程序单元调用一个过程的操作中。为了完 成这个调用,机器必须将它的注意力转移到这个过程上;当过程调用结束 后,机器必须返回到程序块进行调用时所处的位置。这就意味着必须有 种用来记录操作结束后返回的位置的机制。 第机专业语 4-12
Chapter 4 Data Structure 计算机专业英语 4-12 Backtracking A classic application of a stack involves the execution of a program involving procedures as found in our pseudocode. When the execution of a procedure is requested, the machine must transfer its attention to the procedure; yet later, when the procedure is completed, the machine must return to the original location before continuing. This means that, when the initial transfer is made, there must be a mechanism for remembering the location to which execution ultimately returns. 回溯 堆栈的一个典型应用发生在一个程序单元调用一个过程的操作中。为了完 成这个调用，机器必须将它的注意力转移到这个过程上；当过程调用结束 后，机器必须返回到程序块进行调用时所处的位置。这就意味着必须有一 种用来记录操作结束后返回的位置的机制。 4.2 Stacks
Chapter 4 Data Structure 4.2 Stacks The situation is complicated by the fact that the procedure may itself request the execution of another procedure, which may request still another, and so on(Figure 7.9). Consequently, the return locations being remembered begin to pile up. Later, as each of these procedures is completed, execution must be returned to the proper place within the program unit that called the completed procedure. A system is therefore needed to save the return locations and later retrieve them in the proper order 如果一个被调用的过程本身还要调用其他过程,而那些过程 同样也需要调用另外的过程,这样一来整个情形就会很复杂。 因此,返回地址的记忆就开始堆积。然后,当每一个过程都 结束后,操作必须返回到被称为完成过程的程序块中的合适 位置。因此,系统需要按照适当的顺序存储和找回返回地址。 计算机专业英语 4-13
Chapter 4 Data Structure 计算机专业英语 4-13 The situation is complicated by the fact that the procedure may itself request the execution of another procedure, which may request still another, and so on (Figure 7.9). Consequently, the return locations being remembered begin to pile up. Later, as each of these procedures is completed, execution must be returned to the proper place within the program unit that called the completed procedure. A system is therefore needed to save the return locations and later retrieve them in the proper order. 如果一个被调用的过程本身还要调用其他过程，而那些过程 同样也需要调用另外的过程，这样一来整个情形就会很复杂。 因此，返回地址的记忆就开始堆积。然后，当每一个过程都 结束后，操作必须返回到被称为完成过程的程序块中的合适 位置。因此，系统需要按照适当的顺序存储和找回返回地址。 4.2 Stacks
Chapter 4 Data Structure 4.2 Stacks A stack is an ideal structure for such a system. As each procedure is called, a pointer to the pertinent return Location is pushed on a stack, and as each procedure is completed, the top entry from the stack is extracted with the assurance of obtaining a pointer to the proper return location. This example is representative of stack applications in general in that it demonstrates the relationship between stacks and the process of backtracking. Indeed, the concept of a stack is inherent in any process that entails backing out of a system in the opposite order from which it was entered 堆栈是满足这种需要的理想结构。当一个过程被调用时,将指向返回地址 的指针进栈。然后,当一个过程完成时,将栈顶条目出栈,程序就可以准 确得到返回地址。这是应用栈的一个典型例子,它表明了栈和回溯过程的 关系。在任何可以从进入端反向返回系统的过程中,堆栈的概念是与生俱 来的。 《什第机专出美语 4-14
Chapter 4 Data Structure 计算机专业英语 4-14 A stack is an ideal structure for such a system. As each procedure is called, a pointer to the pertinent return Location is pushed on a stack, and as each procedure is completed, the top entry from the stack is extracted with the assurance of obtaining a pointer to the proper return location. This example is representative of stack applications in general in that it demonstrates the relationship between stacks and the process of backtracking. Indeed, the concept of a stack is inherent in any process that entails backing out of a system in the opposite order from which it was entered. 堆栈是满足这种需要的理想结构。当一个过程被调用时，将指向返回地址 的指针进栈。然后，当一个过程完成时，将栈顶条目出栈，程序就可以准 确得到返回地址。这是应用栈的一个典型例子，它表明了栈和回溯过程的 关系。在任何可以从进入端反向返回系统的过程中，堆栈的概念是与生俱 来的。 4.2 Stacks
Chapter 4 Data Structure 4.2 Stacks As another example of backtracking, suppose we want to print the names in a linked list in reverse order--that is last name first. Our problem is that the only way we can access the names is by following the linked structure. Thus we need a way of holding each name retrieved until all of the names that follow have been retrieved and printed. Our solution is to traverse the list from its beginning to its end while pushing the names we find onto a stack After reaching the end of the list, we print the names as we pop them off the stack 我们在来举另一个例子,假设反向输出一张链接表中的姓名,也就是把最 后一个名字第一个输出。问题是我们只能跟着链接结构访问姓名。因此, 我们需要一种方式,通过这种方式,我们可以保持每一个姓名能被检索, 直到排列在这个姓名之后的姓名被得到并输出。我们的方案是从链接表的 开始顺序遍历到结尾,与此同时把每一个姓名按照遍历顺序进栈。当到达 链接表的末尾后,我们通过出栈操作来输出姓名。 计算机专业英语 4-15
Chapter 4 Data Structure 计算机专业英语 4-15 As another example of backtracking, suppose we want to print the names in a linked list in reverse order--that is, last name first. Our problem is that the only way we can access the names is by following the linked structure. Thus we need a way of holding each name retrieved until all of the names that follow have been retrieved and printed. Our solution is to traverse the list from its beginning to its end while pushing the names we find onto a stack. After reaching the end of the list, we print the names as we pop them off the stack. 我们在来举另一个例子，假设反向输出一张链接表中的姓名，也就是把最 后一个名字第一个输出。问题是我们只能跟着链接结构访问姓名。因此， 我们需要一种方式，通过这种方式，我们可以保持每一个姓名能被检索， 直到排列在这个姓名之后的姓名被得到并输出。我们的方案是从链接表的 开始顺序遍历到结尾，与此同时把每一个姓名按照遍历顺序进栈。当到达 链接表的末尾后，我们通过出栈操作来输出姓名。 4.2 Stacks