计算机专业英语（第二版）孙建忠电子教案 Chapter4.ppt

Computer English Chapter 4 Elementary Data Structures * * Key points:  useful terms and definitions of data structureDifficult points:  Stack, queue, tree Requirements: The properties of Stack, Queue, and Linked lists 掌握常用英汉互译技巧 New Words Expressions: stack n. 栈，堆栈 queue n. 队列 attribute n. 属性，性质 underflow n. 下溢 overflow n. 上溢 pseudocode n. 伪码 4.1 Stacks and queues Abbreviations: LIFO（last in first out）后进先出 FIFO（fisrt in first out）先进先出 4.1 Stacks and queues Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is prespecified. In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy. Similarly, in a queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first out, or FIFO, policy. There are several efficient ways to implement stacks and queues on a computer. In this section we show how to use a simple array to implement each. 栈和队列都是动态的集合，其中的元素由预先定义的删除操作可将其去除。在栈中，最近被插入的元素最先被删除，即栈是按后进先出(LIFO)的原则进行的；类似的，在队列里，被删除的元素是最早进入队列的，即队列是以先进先出(FIFO)的原则进行的。在计算机上，对于栈和队列有几种有效的实现方法，这一节我们给出如何用简单的数组来实现它们。 4.1 Stacks and queues 4.1.1 Stacks The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP. These names are allusions to physical stacks, such as the spring-loaded stacks of plates used in cafeterias. The order in which plates are popped from the stack is the reverse of the order in which they were pushed onto the stack, since only the top plate is accessible. 栈中插入元素的操作通常称为入栈(PUSH)，删除操作称为出栈(POP)，这里不考虑删除的那个元素。这些名字来源于实际的堆栈，就像餐厅里使用的带有弹簧座的一叠盘子：因为只有顶部的盘子是方便取用，所以盘子从这一叠中取出的顺序与其被放入的顺序是相反的。 4.1 Stacks and queues 4.1.2 Queues We call the INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE; like the stack operation POP, DEQUEUE takes no element argument. The FIFO