Thread: stacks and dynamic arrays

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    57

    stacks and dynamic arrays

    i have a couple questions......i dont think they are related but they could be

    1. What is a stack ADT
    2. How do I declare a dynamic two dimensional array so that i can have a fairly large array that doesnt overflow the stack.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >What is a stack ADT
    Think about a stack of plates, you always remove and replace from the top of the stack. That's the idea behind it.

    >How do I declare a dynamic two dimensional array so that i can have a fairly large array that doesnt overflow the stack.
    I'm not sure why you would want a two dimensional array, but here is one way to go about it that minimizes the number of allocation requests:
    Code:
    #include <iostream>
    #include <cstdlib>
    
    int **create_twod ( size_t rows, size_t cols )
    {
      size_t i;
      int **ret, *dat;
    
      /* Set aside space for the data */
      dat = new int [rows * cols];
      if ( dat == NULL )
        return NULL;
    
      /* Set aside space for rows pointers to the data */
      ret = new int* [rows];
      if ( ret == NULL ) {
        delete [] dat;
        return NULL;
      }
    
      /* Mark the data at cols intervals */
      for ( i = 0; i < rows; i++ ) {
        ret[i] = dat;
        dat += cols;
      }
    
      return ret;
    }
    
    void delete_twod ( int **a )
    {
      delete [] *a; /* Free the data */
      delete [] a;  /* Free the pointer to the data */
    }
    
    int main()
    {
      int **a;
      int i, j;
      int rows = 5, cols = 5;
      
      if ( ( a = create_twod ( rows, cols ) ) == NULL ) {
        std::cerr<<"Error allocating matrix\n";
        std::exit ( EXIT_FAILURE );
      }
      
      for ( i = 0; i < rows; i++ ) {
        for ( j = 0; j < cols; j++ )
          a[i][j] = i + j;
      }
      
      for ( i = 0; i < rows; i++ ) {
        for ( j = 0; j < cols; j++ )
          std::cout<< a[i][j] <<' '<<std::flush;
        
        std::cout<<std::endl;
      }
    
      delete_twod ( a );
    }
    -Prelude
    My best code is written with the delete key.

  3. #3
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    arrays can't be dynamic. You can declare their size at runtime like
    int* array = new int[size];
    but you can't change the size after you have declared it.
    you will have to use a different data structure if you want it to be dynamic.

  4. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    57
    i want to use a two dimensional array so that i can get words from a file but i only know how to get one character at a time. is there a way to get whole strings?

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    1. A stack ADT (abstract data type) is a LIFO (last in, first out) containter that, at a minimum, supports an interface of push() and pop(). A popular analogy is a stack of trays in a caferteria. As customers go through the line, they take a tray off the top (pop) and as trays are cleaned they are placed on the top of the stack (push). So if you had a stack of char's and you did: push('a'), push('b'), push('c') - the first pop() would be 'c', next 'b', then 'a' - and the stack is empty.

    2. If you know how to dynamically create a 1D array, then extended that to 2D isn't too hard. Think of it as an array of array's (or an array of pointers).
    So we could do this...
    Code:
    int *a[3]; //an array of 3 pointers
    //create 3 arrays, one for each index
    a[0] = new int[3];
    a[1] = new int[3];
    a[2] = new int[3];
    Now we have a 3x3 matrix, but the array which contains all the rows is still allocated on the stack. So, to create the "row array" on the heap as well:
    Code:
    int **a; //a pointer to a pointer (or what will be an array of pointers)
    a = new int*[3]; create an array of 3 pointers on the heap
    a[0] = new int[3];
    a[1] = new int[3];
    a[2] = new int[3];
    Once you understand this, study Prelude's code.

    gg

  6. #6
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398

    Just a couple more thougts on stacks...

    The plates or trays are memory... There's data on each one of those trays!

    The "Back" and "Forward" buttons on your browser work like a stack. Every time you visit a new page, a new page gets added (pushed) to the stack... Last In First Out... You have to work your way all the way to the bottom of the stack to get back to the first page you visited.

    The thing about stacks and queues that makes them different from "ordinary" random access memory, is that you don't have to keep track of a specific variable or address.

    You use stacks and queues when the sequence is important, and random access to the data is not important. When you send a string of characters to your printer, all you need to know is which character is next (a queue).

    With a stack, your program might look like this (psudo):
    Push Name
    Push Name
    Push Name

    Pop Name
    Pop Name
    Pop Name

    With "random access" variables:
    Write Name[1]
    Write Name[2]
    Write Name[3]

    Read Name[3]
    Read Name[2]
    Read Name[1]

    Stack Overflow -
    The compiler/operating system sometimes limit the amount of memory avaliable for use as a stack. Usually, more memory is made available for the "heap".

    Sometimes, there is physical memory dedicated to the stack. But, I don't think this applies to high level languages... That wouldn't be "abstract".

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic storage class?
    By Xinok in forum C++ Programming
    Replies: 12
    Last Post: 12-20-2005, 01:14 PM