📄 6stack.html

📁 Visual C++ has been one of most effective tool for the large industrial applications. This book is t
💻 HTML
字号:
<html>
<head>
	<title>Dynamic Stack</title>
    <meta  name="description" content="Dynamically growing stack in C++">
    <meta name="keywords" content="stack, vector, dynamic, grow, new, delete, allocation">
	<link rel="stylesheet" href="rs.css" tppabs="http://www.relisoft.com/book/rs.css">
</head>

<body background="margin.gif" tppabs="http://www.relisoft.com/book/images/margin.gif" bgcolor="#FFFFDC">

<!-- Main Table -->
<table cellpadding="6">
    <tr>
    <td width="78">
	&nbsp;
    <td>

<h4>Dynamic Stack</h4>

<p class=topics>Dynamic arrays

<p>We will now modify the contract of our stack. There will no longer be a strict limit on how many integers can be pushed. We抣l be able to keep pushing until we run out of memory. 
<p>However, we would like our implementation not to be a memory hog, at least not when it抯 not necessary. So every time we run out of space in the stack, we抣l just double its size. Obviously, we won抰 need the method <var>IsFull</var>. Otherwise the interface will be the same as that of our ordinary stack. 

<p>Here抯 how our new stack works: There's a private helper function <var>Grow</var> that's used internally to double the stack size when necessary. We store the current capacity of the stack in a private variable <var>_capacity</var>. For the purpose of testing we'll set the initial capacity of the stack to one, so that we'll be able to see the stack grow almost immediately.

<tr>
<td class=margin valign=top>

<br>
<a href="javascript:if(confirm('http://www.relisoft.com/book/lang/pointer/source/dynstack.zip  \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval.  \n\nDo you want to open it from the server?'))window.location='http://www.relisoft.com/book/lang/pointer/source/dynstack.zip'" tppabs="http://www.relisoft.com/book/lang/pointer/source/dynstack.zip">
<img src="brace.gif" tppabs="http://www.relisoft.com/book/images/brace.gif" width=16 height=16 border=1 alt="Download!"><br>source</a>
<td>

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>const int initStack = 1;

class IStack
{
public:
      IStack ();
      ~IStack ();
      void Push ( int i );
      int  Pop ();
      int  Top () const;
      bool IsEmpty () const;
private:
      void Grow ();

      int * _arr;
      int   _capacity; // size of the array
      int   _top;
};</pre>
</table><!-- End Code -->

<p>Notice that <var>_arr</var> is declared as a pointer rather than an array. A dynamically allocated array <i>has to</i> be declared as a pointer.
<p>We allocate the initial array in the constructor of <var>IStack</var> and we delete the memory in the destructor.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>IStack::IStack ()
      : _top (0), _capacity (initStack)
{
      _arr = new int [initStack]; // allocate memory
}

IStack::~IStack ()
{
      delete []_arr; // free memory
}</pre>
</table><!-- End Code -->

<p>This is a new kind of relationships between objects. Not only can we say that <var>IStack</var> has access to the array, we can say that <var>IStack</var> owns the array. The <b><i>owns-a</i></b> relationship is expressed through a pointer. Object A owns object B if object A is responsible for object B抯 deallocation. We抣l talk more about it when we discuss resource management.

<p><img src="owns-a.gif" tppabs="http://www.relisoft.com/book/lang/pointer/images/owns-a.gif" width=240 height=72 border=0 alt="owns-a relationship">
<p class=caption>Fig. The owns-a relationship between objects.</p>

<p><var>IStack</var> acquires the memory for the array in its constructor and deallocates it in its destructor. In a moment we抣l see that the method <var>Grow</var> does some reallocation of its own.
<p>So what happens when we <var>Push</var> an integer and there is no space left in the array? We call the <var>Grow</var> method and then complete the push.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>void IStack::Push (int i)
{
      assert (_top &lt;= _capacity);
      if (_top == _capacity)
            Grow ();
      _arr [_top] = i;
      ++_top;
}</pre>
</table><!-- End Code -->


<p>Let抯 see what <var>Grow</var> does. It has to go through the following steps:

<ul>
<li>Allocate new array of twice the size of the current array
<li>Copy all entries from the old array into the first half of the new array
<li>Double the <var>_capacity</var> variable
<li>Delete the old array
<li>Set the pointer <var>_arr</var> to point to the newly allocated array.</ul>

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>void IStack::Grow ()
{
      cout &lt;&lt; "Doubling stack from " &lt;&lt; _capacity &lt;&lt; ".\n";
      // allocate new array
      int * arrNew = new int [2 * _capacity];
      // copy all entries
      for (int i = 0; i &lt; _capacity; ++i)
            arrNew [i] = _arr [i];
      _capacity = 2 * _capacity;
      // free old memory
      delete []_arr;
      // substitute new array for old array
      _arr = arrNew;
}</pre>
</table><!-- End Code -->


<p>The statement

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>_arr = arrNew;</pre>
</table><!-- End Code -->

<p>is a <b><i>pointer assignment</i></b>. We are changing the pointer <var>_arr</var> to point into the new location--the same location <var>arrNew</var> is pointing at. This is the one operation that we cannot do with references. Notice: we are not changing the <i>contents</i> of the location. That would be done in the statement

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>*_arr = *arrNew;</pre>
</table><!-- End Code -->


<p>or its equivalent

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>_arr [0] = arrNew [0];</pre>
</table><!-- End Code -->

<p>We are changing the pointer <var>_arr</var> itself.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>_arr = arrNew;</pre>
</table><!-- End Code -->

<p>For completeness, here are the implementations of the rest of the methods. Notice that although <var>_arr</var> is a pointer, it is accessed like an array.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>int IStack::Pop ()
{
      // Do not Pop an empty stack
      assert (_top &gt; 0);
      --_top;
      return _arr [_top];
}

int IStack::Top () const
{
      // Don't call Top on an empty stack
      assert (_top &gt; 0);
      return _arr [_top - 1];
}

bool IStack::IsEmpty () const
{
      assert (_top &gt;= 0);
      return _top == 0;
}</pre>
</table><!-- End Code -->

<p>And here抯 a simple test program that forces the stack to grow a few times. Notice that we never shrink the stack. This is called a <b><i>high water mark</i></b> type of the algorithm. It would be easy though to add the Shrink method called by <var>Pop</var> every time <var>_top</var> gets much below <var>_size/2</var>. 


<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>int main ()
{
      IStack stack;
      for (int i = 0; i &lt; 5; ++i)
      {
            cout &lt;&lt; "Push " &lt;&lt; i &lt;&lt; endl;
            stack.Push (i);
      }
      for (int j = 0; j &lt; 5; ++j)
      {
            cout &lt;&lt; "Pop " &lt;&lt; stack.Pop () &lt;&lt; endl;
      }
}</pre>
</table><!-- End Code -->


</table>
<!-- End Main Table -->
</body>
</html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -