# stacks and dynamic arrays

• 03-10-2003
Gil22
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.
• 03-10-2003
Prelude
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
• 03-10-2003
beege31337
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.
• 03-10-2003
Gil22
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?
• 03-10-2003
Codeplug
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
• 03-10-2003
DougDbug
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]