<body bgcolor="#ffffff"
text="#000000" link="#0000FF" Vlink="#660099">
<table id="pageTable"
width="599" STYLE="position: relative; left: auto; top:
auto;"><tr><td>
<nobr>
<div class=ts1p0><span
class="ft0p1">Chapter 5. Stacks, Recursion and Backtracking
</span></div>
<div class=ts1p2><span
class="ft1p1">Frederick Thulin, Knowledge Systems Institute, USA
(fthulin@ksi.edu) </span></div>
<div class=ts1p4><span
class="ft2p1"> </span></div>
<div class=ts1p5><span
class="ft2p1">Chapter Outline </span></div>
<div class=ts1p7><span
class="ft1p1"> </span></div>
<div class=ts1p8><span
class="ft1p1">5.1. Stacks </span></div>
<div class=ts1p10><span
class="ft1p1"> </span></div>
<div class=ts1p11><span
class="ft1p1">5.1.1. The LIFO Nature of Stacks
</span></div>
<div class=ts1p13><span
class="ft1p1"> </span></div>
<div class=ts1p14><span
class="ft1p1">5.1.2. Reversing with a Stack
</span></div>
<div class=ts1p16><span
class="ft1p1"> </span></div>
<div class=ts1p17><span
class="ft1p1">5.1.3. Stack Operations
</span></div>
<div class=ts1p19><span
class="ft1p1"> </span></div>
<div class=ts1p20><span
class="ft1p1">5.1.4. Contiguous Implementation
</span></div>
<div class=ts1p23><span
class="ft1p1"> </span></div>
<div class=ts1p24><span
class="ft1p1">5.1.5. Linked Implementation
</span></div>
<div class=ts1p26><span
class="ft1p1">5.2. Recursion
</span></div>
<div class=ts1p28><span
class="ft1p1"> </span></div>
<div class=ts1p29><span
class="ft1p1">5.2.1. Introduction
</span></div>
<div class=ts1p31><span
class="ft1p1"> </span></div>
<div class=ts1p32><span
class="ft1p1">5.2.2. Procedure Calls and the Run-Time Stack
</span></div>
<div class=ts1p36><span
class="ft1p1"> </span></div>
<div class=ts1p37><span
class="ft1p1">5.2.3. Sum of the First n Positive Integers
</span></div>
<div class=ts1p39><span
class="ft1p1"> </span></div>
<div class=ts1p40><span
class="ft1p1">5.2.4. Factorials
</span></div>
<div class=ts1p42><span
class="ft1p1"> </span></div>
<div class=ts1p43><span
class="ft1p1">5.2.5. Collatz 3x+1 Problem
</span></div>
<div class=ts1p45><span
class="ft1p1"> </span></div>
<div class=ts1p46><span
class="ft1p1">5.2.6. Greatest Common Divisor
</span></div>
<div class=ts1p49><span
class="ft1p1"> </span></div>
<div class=ts1p50><span
class="ft1p1">5.2.7. Towers of Hanoi
</span></div>
<div class=ts1p52><span
class="ft1p1"> </span></div>
<div class=ts1p53><span
class="ft1p1">5.2.8. Reversing a Line of Input
</span></div>
<div class=ts1p55><span
class="ft1p1">5.3. Backtracking
</span></div>
<div class=ts1p57><span
class="ft1p1"> </span></div>
<div class=ts1p58><span
class="ft1p1">5.3.1. Introduction<span class="ft3p1">
</span></span></div>
<div class=ts1p60><span
class="ft1p1"> </span></div>
<div class=ts1p61><span
class="ft1p1">5.3.2. The Eight Queens Problem
</span></div>
<div class=ts1p63><span
class="ft1p1"> </span></div>
<div class=ts1p64><span
class="ft1p1">5.3.3. Escape from a Maze
</span></div>
<div class=ts1p66><span
class="ft1p1">Exercises </span></div>
<div class=ts1p68><span
class="ft0p1"> </span></div>
<div class=ts1p69><span
class="ft0p1">5.1. Stacks </span></div>
<div class=ts1p71><span
class="ft1p1"> </span></div>
<div class=ts1p72><span
class="ft2p1">5.1.1. The LIFO Nature of Stacks
</span></div>
<div class=ts1p74><span
class="ft1p1"> </span></div>
<div class=ts1p75><span
class="ft1p1">A stack is a data structure analogous to stacks encountered in
everyday life. For example, </span></div>
<div class=ts1p77><span
class="ft1p1">consider a stack of books on a desk. One may easily
put a new book on top of the stack, and </span></div>
<div class=ts1p78><span
class="ft1p1">one may easily remove the top book. Adding books to,
or removing them from, the middle of </span></div>
<div class=ts1p79><span
class="ft1p1">the stack may be perilous. In the stack data
structure accessing items in the middle is
</span></div>
<div class=ts1p81><span
class="ft1p1">prohibited. Items may be added to or removed from
only the top of the stack. </span></div>
<div class=ts1p83><span
class="ft1p1"> </span></div>
<div class=ts1p84><span
class="ft1p1">Saving an item on a stack is referred to as pushing the item,
and retrieving an item is called </span></div>
<div class=ts1p86><span
class="ft1p1">popping the item. Popping an item removes the item
from the stack. Pushes and pops are done
</span></div>
<div class=ts1p87><span
class="ft1p1">at the top of the stack, which may be thought of as a
distinguished end of the stack. This means
</span></div>
<div class=ts1p88><span
class="ft1p1">that if two items are pushed and then one popped, the second
one pushed will be popped. This
</span></div>
<div class=ts1p90><span
class="ft1p1">order of data access is called last in, first out or LIFO
access. </span></div>
<div class=ts1p92><span
class="ft1p1"> </span></div>
<div class=ts1p93><span
class="ft2p1">5.1.2. Reversing with a Stack
</span></div>
<div class=ts1p95><span
class="ft1p1"> </span></div>
<div class=ts1p96><span
class="ft1p1">Suppose a sequence of items is presented and it is desired to
reverse the sequence. Various </span></div>
<div class=ts1p97><span
class="ft1p1">methods could be used and the beginning programmer usually will
suggest a solution using an </span></div>
<div class=ts1p99><span
class="ft1p1">array. A conceptually very simple solution, however,
is based on using a stack. The LIFO
</span></div>
<div class=ts1p100><span
class="ft1p1">property of stack access guarantees the reversal.
</span></div>
<div class=ts2p0><span class="ft0p2"> </span></div>