The data types arrays and records are native to many programming languages．By using the pointer data type and dynamic memory allocation，many programming languages also provide the facilities for constructing linked structures．Arrays，records，and linked structures provide the building blocks for implementing what we might call higher-level abstractions．The first two higher-level abstract data types that we take up-stacks and queues-are extremely important to computing． A stack is a data type whose major attributes are determined by the rules governing the insertion and deletion of its elements．The only element that can be 0deleted or removed is the one that was inserted most recently．Such a structure is said to have a“last in，first out”（LIFO）behavior，or protocol．The simplicity of the data type stack belies [1] its importance．Many computer systems have stacks built [2] into their circuitry and have machine-level instructions to operate the hardware stack．The sequencing of calls to and returns from subroutines follows a stack protocol．Arithmetic expressions are often evaluated by a sequence of operations on a stack．Many handheld calculators use a stack mode of operation．In studying computer science，you can expect to see many examples of stacks． Queues occur frequently in everyday life and are therefore familiar to us． The line of people waiting for [3] service at a bank or for tickets at a movie theater and the line of autos at a traffic light are examples of queues．The main feature of queues is that they follow a“first come，first served”rule．Contrary to a stack，in which the latest element inserted is the first removed or served，in queues the earliest element inserted is the first served．In social settings，the rule appeals to our sense of equality and fairness． There are many applications of the FIFO protocol of queues in computing．For example，the line of input/output（I/O）requests waiting for access to a disk drive in a multiuser time-sharing system might be a queue．The line of computing jobs waiting to be run on a computer system might also be a queue．The jobs and I/O requests are serviced in order of their arrival，that is，the first in is the first out． There is a second kind of queue that is important．An everyday example can be seen in an emergency room of a hospital．In large emergencies it is common to first treat the worst injured patients who are likely to survive．In certain societies in which 1ess emphasis is placed on equality，people with higher social standing may be treated first． In computer systems，events that demand the attention of the computer are often handled according to a“most-important-event served-first”，or“highest-priority in／first-out”（HPIFO），rule．Such queues are called priority queues，in this type of queue service is not in order of time of arrival but rather in order of some measure of priority．