CODEWITHSUNDEEP
carrayspointersstack
C. Rib
C. Rib

Reputation: 390

Should the stack pointer point to the value on the top, or the the position where the next value should be?

For example, take this example functions:

#include <stdlib.h>

#define MAX 100
typedef struct stack {
int sp;
int val [MAX];
} STACK;


void initStack (STACK *s){
    s->sp = 0;
}

int push (STACK *s, int x){
    if(s->sp == MAX) return -1;
    else s->val[s->sp++] = x;
    return 0;
}

int main(){
    STACK s;
    int pushval, p;

    initStack(&s);

    p = push(&s, 1);
    pushval = s.val[s.sp-1];
    printf("pushval %d\n", pushval);

    return 0;
}

So in this case if I do s.val[s.sp] I get gibberish. If I do s.val[s.sp-1] I get the value I pushed on to the stack. I don't know if the stack pointer should point to the "next available space" aka be equal to the number of elements in the array, or should be equal to the index of the last element of the array aka number of elements in the array - 1

Upvotes: 0

Views: 2235

Answers (2)

John Bode
John Bode

Reputation: 123458

For me, the most natural implementation of an array-based stack is one that grows "downwards", with the stack pointer pointing to the most recently pushed element:

void initStack (STACK *s)
{
    s->sp = MAX;
}

int push (STACK *s, int x)
{
  if( !s->sp ) 
    return 0;               
  else                      
    s->val[--s->sp] = x;    
  return 1;                 
}    

int pop(STACK *s, int *x)
{
  if ( s->sp == MAX )
    return 0;
  else
    *x = s->val[s->sp++];
  return 1;
}

The checks are simpler IMO, and since it never decrements below 0, you can safely use an unsigned type as your stack pointer (which I tend to do for reasons that probably aren't completely rational).

Note that this mimics the x86 (and many other architectures') stack behavior, in that the SP grows "downwards", towards 0.

Notice that I changed the return value on success and failure, since in C 0 means "false" and non-zero means "true". This way you can write code like

if ( push( stack, val ) )
{
  ...
}
else
{
  // push failed, handle as appropriate
}

Again, this is just a more natural implementation IMO.

EDIT

One big drawback of this method is that it's difficult to grow the stack if necessary. If you allocate the backing array dynamically, you can use realloc to extend it, but you will have to move all the existing data to the new stack "bottom", which would be expensive and a pain in the ass. By contrast, if you grow the stack upwards, you don't have that problem. But, if I wanted a stack that could grow or shrink as necessary, I wouldn't use an array-based stack, I'd use one based on a linked list, where items are pushed by adding them to the head of the list and popped by removing them from the head.

Upvotes: 1

Jean-Baptiste Yun&#232;s
Jean-Baptiste Yun&#232;s

Reputation: 36401

This is just a matter of convention. Many implementations let the top stack pointer points to the "next available space", but you can really do what you prefer, provided that externally your stack behave as intented.

Upvotes: 3

Related Questions