Volume 1 / Fundamental Algorithms
`
`H Stanford University
`
`THE ART OF
`COMPUTER PROGRAMMING
`· SECOND EDITION
`
`ISHING COMPANY
`
`Reading, Massachusetts
`Menlo Park, California · London · Amsterdam · D on Mills, Ontario · Sydney
`
`ASSA ABLOY Ex. 1020 - Page 1
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`This book is in the
`ADDISON-WESLEY SERIES IN
`COMPUTER SCIENCE AND INFORMATION PROCESSING '
`
`RICHARD s. VARGA and MICHAEL A, HARRISON, Ed itors
`
`COPYRIGHT @ 1973, 1968 BY ADDISON-WESLEY PUBLI SHING COMPANY, INC. ALL RIGHTS
`RESERVED. NO PART OF" THIS PUBLICATION MAY BE REPRODUCED, STORED IN A RE·
`TRIEVAL SYSTEM, OR TRANSMITTED, I N ANY FORM OR BY ANY MEAN S, ELECTRON IC,
`MECHANICAL, PHOTOCOPYING, RECORDING, OR OTHERWI SE, WITHOUT THE PRIOR WRlT·
`TEN PERMI SSION OF THE PUBLI SHER. PRINTED I N THE UNITED STATES OF AMERICA.
`PUBLI SH ED SIMULTANEOU SLY IN CANADA. LIBRARY OF CONGRESS CATALOG CARD NO.
`73-1830.
`
`ISBN 0-20 1-03809 -9
`CDEFGH IJ-MA-79876.
`
`He
`pub/is
`recipe
`No w we ca
`if you
`
`The process of preparing
`not only because it can
`because it can be an aes
`This book is the first v<
`signed to train the reade
`The following chap1
`puter programming; th
`perience. The prerequi
`time and practice before
`puter. The reader shou:
`a) Some idea of how a
`the electronics, rath
`machine's memory a
`language will be he!
`b) An ab ility to put tr
`computer can " uncle
`t hey have not yet lE
`no more and no !es:
`first tries to use a cc
`c) Some knowledge ol
`looping (performin g
`and the u e of inde}
`d) A little knowledge o
`"bits," "float ing po
`are given brief defin
`
`* or she. Masculine pronO\
`Occasional chauvinistic com1
`
`ASSA ABLOY Ex. 1020 - Page 2
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`234
`
`I NFORMATIO N STRUCTURES
`
`2.2. LINEAR LISTS
`
`2.2 . 1. Stacks, Queues, and Deques
`Usually t here is much more stru ctural information present in t he data than ,
`actually want to represent directly in a computer. In each "playing card" n
`.
`of the preceding section, for example, we have a NEXT field to specify what card •
`beneath it in the pile, but there is no direct way to find what card, if an_
`is above a given card, or to find which pile a given card is in. Of course, there •
`much information possessed by any real deck of playing cards which has be, .
`totally suppressed from the computer representation: t he details of the de i
`on the back of t he cards, the relation of the cards to other objects in the roor:
`where the game is being played, the molecules which compose the cards, etc. I·
`is conceivable that such structural information would be relevant in certair.
`computer applications, but obviously we never want to store all of the structure
`present in every situation. Indeed, for most card-playing situations we would
`not need all of the facts retained in our earlier example; thus the TAG field, which
`tells whether a card is face up or face down, will often be unnecessary.
`It is therefore clear t hat we must decide in each case how much structure to
`represent in our tables, and how accessible to make each piece of information.
`To make t his decision, we need to know what operations are to be performed on
`the data. For each problem considered in this chapter, we therefore consider not
`only the data structure but also the class of operations to be done on the data; the
`design of computer representations depends on the desired function of the data
`as well as on its intrinsic properties. Such an emphasis on "function" as weH as
`"form" is basic to design problems in general.
`In order to illustrate this point further, let us consider a simple example
`which arises in computer hardware design. A computer memory is often classified
`as a "random access memory," i.e., MIX's main memory ; or as a "read only
`memory, " i.e., one which is to contain essentially constant information; or a
`"secondary bulk memory," like MIX's disk units, which cannot be accessed at
`high speed although large quantities of information can be stored; or an "asso(cid:173)
`ciative memory," more properly called a "content-addressed memory," i. e., one
`for which information is addressed by values stored with it rather than by its
`location ; and so on. Note that the intended function of each kind of memory is
`so important that it enters into the name of the particular memory type; all of
`these devices are "memory " units, but the purposes to which they are put
`profoundly influence their design and their cost.
`A linear list is a set of n ~ 0 nodes X[l], X[2], ... , X[n] whose structural
`properties essentially involve only the linear (one-dimensional) relative positions
`of the nodes: the facts that, if n > 0, X[l] is the first node; when 1 < k < n,
`1] and followed by X[k + 1] ; and x[n]
`the kth node x[lc] is preceded by X[k -
`is the last node.
`The operations we might want to perform on linear lists include, for example,
`the fo llowing.
`
`- l
`
`to the i
`i) Gain acce
`the content of it fi
`ii) In ert a new node j 1
`iii) Delete the kth node
`iv) Combine two or mo
`y) plit a linear li t in
`ake a copy of a li
`vi)
`vii) Determine the nun:
`·iii) Sort the nodes of t
`of the nodes.
`ix) Search the list for
`some field.
`
`operations (i) , (ii), and (i
`portance since the first a
`a general element is.
`pter, since these topics :
`computer applicatio1
`eir full generality, so we
`pending on the class of c
`- difficult to design a sin
`of these operations are
`e kth node of a long list
`e time we are inserting
`re we distinguish betwe
`erations to be perform<
`!e distinguished by their
`Linear lists in which in
`ways at the first or the 1:
`em special names:
`A stack is a linear list
`accesses) are mac
`A qiieue is a linear list
`all deletions (anc
`A deque ( "double-end
`deletions (and u
`
`. deque is therefore more
`m common with a deck,
`.fu tinguish output-restrict
`ertions, respectively, an
`In some disciplines tl
`o describ e any kind of Ii
`cases identified above a1
`
`ASSA ABLOY Ex. 1020 - Page 3
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`2.2
`
`2.2. 1
`
`STACKS, QUEUES, AND DEQUES
`
`235
`
`ion present in the data than we
`ir. In each "playing card" node
`~EXT field to specify what card is
`¥ay to find what card, if any,
`n card is in. Of course, there is
`f playing cards which has been
`ation: the details of the design
`ds to other objects in the room
`hich compose the cards, etc. It
`1 would be relevant in certain
`·ant to store all of the structure
`rd-playing situations we would
`:1,mple; thus the TAG field, which
`ll often be unnecessary.
`wh case how much stru cture to
`1ake each piece of information.
`~rations are to be performed on
`1apter, we therefore consider n ot
`ions to be done on the data; the
`he desired function of the data
`phasis on "function" as well a
`
`us consider a simple example
`;mter memory is often classified
`memory; or as a "read only
`.ly constant information · or a
`, which cannot be acces~ed a
`on can be stored ; or an "asso(cid:173)
`t-addressed memory," i. e., one
`red with it rather t han by i
`tion of each kind of memory ·
`9articular memory type; all o
`·poses to which they are pu
`
`2], ... , X[n] whose structu r
`dimensional) relative position:.
`first node; when 1 < k < n
`Jllowed by X[k + l] ; and x[
`
`near lists include, for example
`
`i) Gain access to the kth node of the list to examine and/ or to change
`the contents of its fields.
`ii) Insert a new node just before the kth node.
`iii) Delete the kth node.
`iv) Combine two or more linear lists into a single list.
`v) Split a linear list into two or more lists.
`vi) Make a copy of a linear list.
`vi i) Determine the number of nodes in a list.
`viii) Sort the nodes of the list into ascending order based on certain fields
`of the nodes.
`ix) Search t he list for the occurrence of a node with a part icular value in
`some field.
`
`In operations (i), (ii), and (iii) the special cases k = l and k = n are of principal
`importance since the first and last items of a linear list may be easier to get at
`·han a general element is. We will not discuss operations (viii) and (ix) in t his
`·hapter, since t hese topics are the subj ects of Chapters 5 and 6, respectively.
`A computer application rarely calls for all nine of t he above operations in
`· heir full generality, so we find t here are many ways to represent linear lists
`lepending on the class of operations which are to be done most frequently. It
`i.:; difficult to design a single representation method for linear lists in which
`all of these operations are efficient; for example, the ability to gain access to
`he kth node of a long list for random k is comparatively hard to do if at the
`, ame time we are inserting and deleting items in the middle of the list . There(cid:173)
`:ore we distinguish between types of linear lists depending on the principal
`perations to be performed, just as we have noted that computer memories
`re distinguished by their intended applications.
`Linear lists in which insertions, deletions, and accesses to values occur almost
`Jways at the fi rst or t he last node are very frequently encountered, and we give
`· hem special names :
`A stack is a linear list for whi ch all insertions and deletions (and usually all
`accesses) are made at one end of the list.
`A queue is a linear list for whi ch all insertions are made at one end of t he list;
`all deletions (and usually all accesses) are made· at the other end.
`A deque ( "double-ended queue") is a linear list for which all insertions and
`deletions (and usually all accesses) are made at t he ends of the list.
`
`A deque is therefore more general than a stack or a queue; it has some properties
`.n common with a deck of cards, and it is pronounced the same way. We also
`Jistinguish output-restricted or input-restricted deques, in which deletions or in(cid:173)
`,ertions, respectively, are allowed to take place at only one end.
`In some disciplines the word "queue" has been used in a much broader sense
`·o describe any kind of list that is subj ect to insertions and deletions; the special
`a es identified above are then called various "queuing disciplines." Only the
`
`ASSA ABLOY Ex. 1020 - Page 4
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`240
`
`INFORMATION ST RUCTURES
`
`2.2.2
`
`2.2.2. Sequential Allocation
`The simplest and most natural way to keep a linear list inside a computer is to
`put the list items in sequential locations, one node after the other. We thus will
`have
`
`LOC(X[j + l]} = LOC(X[j]) +c,
`
`( sually c = 1. When c > 1, it is
`where c is the number of words per node.
`sometimes more convenient to split a single list into c "parallel" lists, so that
`the kth word of node X[jl is stored a fixed distance from t he location of the
`first word of X[j l. We will continually assume, however, that adjacent groups
`of c words form a single node.) In general,
`
`LOC (X [j ]) = Lo + cj,
`
`where L0 is a constant called the base address, the location of an artificially
`assumed node X[ 0 l.
`This technique for representing a linear list is so obvious and well-known
`t hat there seems to be no need to dwell on it at any length. But we will be
`seeing many other "more sophisticated " methods of representation later on in
`t his chapter, and it is a good idea to examine t he simple case first to see just how
`far we can go wi th it. It is important to understand the limitations as well as
`the power of the use of sequential allocation.
`Sequential allocation is quite convenient for dealing with a stack. We simply
`have a variable T called t he stack pointer. When t he stack is empty, we let
`T = 0 .. To place a new element Yon top of the stack, we set
`T + l ;
`And when the stack is not empty, we can set Y equal to the top node and delete
`that node by reversing t he actions of (2) :
`
`(2)
`
`T -
`
`X[Tl f-Y.
`
`Y f- X[T];
`
`Tf-T -
`
`1.
`
`(3)
`
`(Inside a computer it is usually most efficient to maintain the value cT instead
`of T, because of (1) . Such modifications are easily made, so we will continue our
`discussion as though c = 1.)
`The representation of a queue or a more general deque is a litt le trickier. An
`obvious solution is to keep two pointers, say F and R (for the front and rear of
`the queue), with F = R = 0 when the queue is empty. Then inserting an ele(cid:173)
`ment at the rear of the queue would be
`
`X(R] f-Y.
`
`(4)
`
`Removing the front node (F points just below the front) would be
`
`(5)
`then set Ff-Rf--0.
`if F = R,
`Yf-X[F] ;
`F-F + l ;
`But note what can happen: If R always stays ahead of F (so there is always at
`
`- one node in the queue)
`infinitum, and thi i ter
`_ . 5) i therefore to be u 1
`. quite regularly (for ex
`queue).
`To circumvent the prol
`-· e M nodes X[l] , . .. , X[M
`J· Then the above proce
`if R = M
`then
`if F = M
`then
`circular queuing actio1
`ion of input-ou tput
`- ·u
`T he above discussion
`-- 1mcd 1 nothing could go
`eue, we assumed that th
`ode onto a stack or queL
`rly the method (6), (,
`hods (2) , (3), (-!) , (5) al
`hi n any given computm
`ve actions must be re\\
`..at these restrictions are
`x = Y (insert into stack)
`: = x (delete from stack)
`
`x = Y (insert into queue
`
`-: = x (delete from queue
`
`Herc we assume that X[ l l
`. t ; OVERFLOW and UNDER I
`he initial setting F = R •
`e (6a) and (7a); we she
`The reader is urged 1
`of this simple queuing m
`The next question is,
`In the case of UNDERFLOV
`u ually a meaningful cor
`govern the flow of a pro
`
`ASSA ABLOY Ex. 1020 - Page 5
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`