What is a Stack, Heap and Queue ?

Hi !!
I have read some books to know exactly what is a stack a heap and a queue. But I couldnt find much information. What really is a stack or a heap ? Many books just mention that during program execution the variables are "pushed on to" a stack ( or was that a heap or a queue ??).Another confusion is FIFO. To illstrate the FIFO concept the "plates" example was given. But if something is accesed on a First In First Out basis, what happens to the other variables that are below this variable. Does this mean that in a FIFO sequence only the variable that is First In gets out first and the remaining variables just remain there? .
I tried to search for information but could not find much. I would be extremely thankful if someone could help me with these.

Ok, first a heap. A heap is a region of free memory that your program can use with C's dynamic memory allocation functions. Such as malloc() and free(). This is memory NOT yet in use by any program, including windows, but set aside for use for the program in question that created the heap.

A queue is best represented with FIFO. First in First out. Best way to think of it as an array with two variables that will represent the position you are at. Basicaly one variable remembers how many you've put in and the other variable remembers how many you've taken out. Like this:

Code:

---

#define MAX 100

int queue[MAX];
int storePosition = 0;
int retrievePosition = 0;

void store(int num) {
  if(storePosition >= MAX) {
    printf("Full.\n");
  }
  else {
    queue[storePosition] = num;
    storePosition++;
  }
}

int retrieve(void) {
  int temp;

  if(retrievePosition >= storePosition) {
    printf("Empty.\n");
    temp = 0;
  }
  else {
    temp = queue[retrievePosition];
    retrievePosition++;
  }
  return temp;
}

---

A stack on the other hand is best represented as FILO. First in Last Out. Typicaly a stack is thought to have two functions that will push() data into the stack and pop() data out of the stack. In this case only one variable will be needed to keep track of the position your in. Essentialy you put two, it incrememts position by two. When you retrieve one, it decrememts position by one.

Code:

---

#define MAX 100

int stack[MAX];
int topPosition;

void push(int num) {
  if(topPosition >= MAX) {
    printf("Full.\n");
  }
  else {
    stack[topPosition] = num;
    topPosition++;
  }
}

int pop(void) {
  int temp;

  topPosition--;
  if(topPosition < 0) {
    printf("Empty.\n");
    temp = 0;
  }
  else {
    temp = stack[topPosition];
  }
  return temp;
}

---

Hope this helps.

Hi !!

Thanks a lot for the answer. But could you tell me a good book or a site whre i could learn moer about stacks heap and queue. I was told that to be a good C/C++ programmer it is necessary to have a good understanding of these. Thanks again for the answer.

Algorithms in C by Sedgewick. It's hard to understand at first, but if you read it a few times the logic begins to sink in.

-Prelude