<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
<title></title>
</head>
<body text="#000000" bgcolor="#ffffff">
G'Day Mark<br>
In pre-hysterical times I was a member of the first exam setting
panel for IS. At that stage there were a few teachers who had no
formal IT training so we would occasionally drop in a more
interesting question to encourage teachers to look more closely at
particular topics that were poorly answered. This question may well
have been designed to get classes to look more closely at different
ways of handling stacks. <br>
Conventionally the top of stack pointer does not actually point to
the top of the stack but to where the next item should be added,
however this may confuse newbies more than having a TOS pointer
which points to the actual top of stack. Also if the question used
a conventional TOS pointer the stack would not get full with the
given steps.<br>
Often element zero in the stack array would contain the TOS pointer
so in a new stack element 0 would contain the value 1. Doing this
avoids the need for a separate TOS variable. <br>
I think the question has certainly provoked discussion - maybe its a
hint that there will be a question on stacks on the EOY exam :-)<br>
Might be a good idea to look at various stack algorithms. ;-)<br>
<br>
Mike<br>
<br>
<br>
On 27/04/2011 2:35 PM, Mark KELLY wrote:
<blockquote
cite="mid:BANLkTikUCf___U4OkGDuJ2TRcJKt9rOcgg@mail.gmail.com"
type="cite">Thanks for the bone, Mike. Woof! It finally let me
work out the many assumptions underlying the question: and after
all that, I'm not wagging my tail.<br>
<br>
I think the question is far from clear, and I doubt students would
make much of it in a real exam.<br>
<br>
- It does not, for example, say that the stack is zero-based. If
one assumes (as I did) that the stack indexing starts at 1, the
whole thing changes and nothing makes sense.<br>
- It does not indicate what the mysterious bolding of the bottom 2
items is meant to represent. If the examiners invent their own
conventions, they should explain them to us.<br>
- It does not tell us that the stack pointer in updated <b>before</b>
a push/pop instead of being changed afterwards, as often happens.
Again, this changes everything.<br>
- One has to realise that the stack is expanding from the bottom
and not from the top. Stacks are often represented growing in
either direction.<br>
<br>
When it comes to real-world stack implementation, there are so
many different options such as these that I found the question
mind-boggling while I went through the permutations of possible
readings.<br>
<br>
Grrr.<br>
<br>
<div class="gmail_quote">On 21 April 2011 14:45, Mike Brookes <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:mikebr@tpg.com.au">mikebr@tpg.com.au</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt
0.8ex; border-left: 1px solid rgb(204, 204, 204);
padding-left: 1ex;">
<div text="#000000" bgcolor="#ffffff"> Hi Mark et Al<br>
<br>
For the question to make sense one has to make the
assumption that the stack positions start at the bottom with
position zero and go up to position 4 which is the top of
the stack. At the start the bottom two (in bold on the PDF)
are valid, hence the top of stack pointer showing 1. <br>
<br>
Below is the completed table and the stack at the start and
after each step:<br>
<table width="817" border="0" cellpadding="0"
cellspacing="0">
<colgroup><col style="width: 26pt;" width="35"> <col
style="width: 68pt;" width="91"> <col style="width:
23pt;" width="30"> <col style="width: 93pt;"
width="124"> <col style="width: 22pt;" width="29"> <col
style="width: 23pt;" width="30" span="2"> <col
style="width: 48pt;" width="64" span="7"> </colgroup><tbody>
<tr style="min-height: 15.75pt;" height="21">
<td style="min-height: 15.75pt; width: 26pt;"
width="35" height="21"><br>
</td>
<td style="width: 68pt;" width="91"><br>
</td>
<td style="width: 23pt;" width="30"><br>
</td>
<td style="width: 93pt;" width="124"><br>
</td>
<td style="width: 22pt;" width="29"><br>
</td>
<td style="width: 23pt;" width="30"><br>
</td>
<td style="width: 23pt;" width="30"><br>
</td>
<td style="width: 48pt;" width="64"><br>
</td>
<td style="width: 48pt;" width="64"><br>
</td>
<td style="width: 48pt;" width="64"><br>
</td>
<td style="width: 48pt;" width="64"><br>
</td>
<td style="width: 48pt;" width="64"><br>
</td>
<td style="width: 48pt;" width="64"><br>
</td>
<td style="width: 48pt;" width="64"><br>
</td>
</tr>
<tr style="min-height: 15.75pt;" height="21">
<td style="min-height: 15.75pt;" height="21"><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td colspan="7" style="border-right: 1pt solid black;">Stack
at start and after each step</td>
</tr>
<tr style="min-height: 15.75pt;" height="21">
<td style="min-height: 15.75pt;" height="21">Step</td>
<td style="border-left: medium none;">Function</td>
<td style="border-left: medium none;">Top</td>
<td style="border-left: medium none;">Output</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td style="border-top: medium none;">Start</td>
<td style="border-top: medium none; border-left:
medium none;">Step 1</td>
<td style="border-top: medium none; border-left:
medium none;">Step 2</td>
<td style="border-top: medium none; border-left:
medium none;">Step 3</td>
<td style="border-top: medium none; border-left:
medium none;">Step 4</td>
<td style="border-top: medium none; border-left:
medium none;">Step 5</td>
<td style="border-top: medium none; border-left:
medium none;">Step 6</td>
</tr>
<tr style="min-height: 15pt;" height="20">
<td style="min-height: 15pt; border-top: medium none;"
height="20">1</td>
<td style="border-top: medium none; border-left:
medium none;">Push (23)</td>
<td style="border-top: medium none; border-left:
medium none;">2</td>
<td style="border-top: medium none; border-left:
medium none;">Item added (23)</td>
<td><br>
</td>
<td rowspan="5" style="border-bottom: 1pt solid
black;">Stack position</td>
<td style="border-left: medium none;" align="right">4</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">92</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">92</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">92</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">92</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">92</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">92</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">92</td>
</tr>
<tr style="min-height: 15pt;" height="20">
<td style="min-height: 15pt; border-top: medium none;"
height="20">2</td>
<td style="border-top: medium none; border-left:
medium none;">Push (18)</td>
<td style="border-top: medium none; border-left:
medium none;"> </td>
<td style="border-top: medium none; border-left:
medium none;">Item added (18)</td>
<td><br>
</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">3</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">75</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">75</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">18</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">18</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">75</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">75</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">75</td>
</tr>
<tr style="min-height: 15pt;" height="20">
<td style="min-height: 15pt; border-top: medium none;"
height="20">3</td>
<td style="border-top: medium none; border-left:
medium none;">Pop</td>
<td style="border-top: medium none; border-left:
medium none;">2</td>
<td style="border-top: medium none; border-left:
medium none;">Item removed (18)</td>
<td><br>
</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">2</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">23</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">23</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">23</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">23</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">23</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">23</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">23</td>
</tr>
<tr style="min-height: 15pt;" height="20">
<td style="min-height: 15pt; border-top: medium none;"
height="20">4</td>
<td style="border-top: medium none; border-left:
medium none;">Push (75)</td>
<td style="border-top: medium none; border-left:
medium none;"> </td>
<td style="border-top: medium none; border-left:
medium none;">Item added (75)</td>
<td><br>
</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">1</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">83</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">83</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">83</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">83</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">83</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">83</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">83</td>
</tr>
<tr style="min-height: 15.75pt;" height="21">
<td style="min-height: 15.75pt; border-top: medium
none;" height="21">5</td>
<td style="border-top: medium none; border-left:
medium none;">Push (92)</td>
<td style="border-top: medium none; border-left:
medium none;">4</td>
<td style="border-top: medium none; border-left:
medium none;">Item added (92)</td>
<td><br>
</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">0</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">52</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">52</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">52</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">52</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">52</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">52</td>
<td style="border-top: medium none; border-left:
medium none;" align="right">52</td>
</tr>
<tr style="min-height: 15.75pt;" height="21">
<td style="min-height: 15.75pt; border-top: medium
none;" height="21">6</td>
<td style="border-top: medium none; border-left:
medium none;">Push (47)</td>
<td style="border-top: medium none; border-left:
medium none;"> </td>
<td style="border-top: medium none; border-left:
medium none;">Stack full</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
</tr>
<tr style="min-height: 15.75pt;" height="21">
<td style="min-height: 15.75pt;" height="21"><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td><br>
</td>
<td>Top</td>
<td style="border-left: medium none;" align="right">1</td>
<td style="border-left: medium none;" align="right">2</td>
<td style="border-left: medium none;" align="right">3</td>
<td style="border-left: medium none;" align="right">2</td>
<td style="border-left: medium none;" align="right">3</td>
<td style="border-left: medium none;" align="right">4</td>
<td style="border-left: medium none;" align="right">4</td>
</tr>
</tbody>
</table>
<br>
<font color="#888888"> Mike Brookes <br>
Semi retired gentleman from Copperfield College</font>
<div class="im"><br>
<br>
On 21/04/2011 1:35 PM, Mark KELLY wrote:
<blockquote type="cite">
<p class="MsoNormal">Would someone be kind enough to
throw me a bone about the stack question - Q3?<br>
<br>
I thought I knew stack implementation from my assembly
language days with Z80... this question feels like
walking into someone's half-finished thought process.
I'm really confused about this.After half an hour of
conjecture, I’ve tried four times to ask a series of
sensible questions to make sense of it, and have
failed every time. <br>
</p>
<p class="MsoNormal"><br>
</p>
<p class="MsoNormal">The only apparent answer involves
time travel, reversed arrays, irrelevant stack
pointers and bogus bolding of stack items. The
relationship between the stack and the table is only
the beginning of the problem...<br>
</p>
<p class="MsoNormal"><br>
</p>
<p class="MsoNormal">I’d be delighted if anyone could
walk me through this...</p>
<p class="MsoNormal"><br>
</p>
<p class="MsoNormal">Regards</p>
<p class="MsoNormal">Mark<br>
</p>
<br>
</blockquote>
</div>
</div>
</blockquote>
</div>
</blockquote>
<br>
</body>
</html>