Pop in O(1) - stacks

Hello.
I'm making a stack from scratch and I've realized I can't find a way to get a pop operation to work in O(1). I know it has to be simple but I am having a hard time finding an implementation of stacks that use arrays instead of vectors.

I've got two structs and an incomplete method, like:

typedef struct 
{
  struct stack_node* next;
  void* data;
} stack_node;

typedef struct stack
{
  stack_node* top;
}

void* stack_pop (const stack_t* stack)
{
  void* aux_node = stack_get_top(stack);
  free(stack->top);

  //here I am missing an order to tell the stack that the new top is the previous node to the one that's being deleted. How do I do that?

  return aux_node;
}

Last edited on

Duthomhas (13206)

You should use temporary values:

void* stack_pop (stack* stack)  // stack cannot be const, as you wish to modify it
{
  // Cannot pop if there is no stack
  if (!stack) return NULL;

  // Cannot pop an empty stack
  if (!stack->top) return NULL;

  // Remember the user's data
  void* data = stack->top->data;

  // This is the node to delete
  stack_node* node_to_delete = stack->top;

  // Update the stack to use the next node as the new top node
  stack->top = stack->top->next;

  // Delete the old top
  free( node_to_delete );

  // And return the user's data
  return data;
}

BTW, the typical idiom for this kind of stuff is:

typedef struct stack_node_tag
{
  struct stack_node_tag* next;
  void* data;
}
stack_node;

typedef struct 
{
  stack_node* top;
}
stack;

Hope this helps.

Powdertrail (46)

Thanks for responding! First off, yes, you're right, I'm just too used to writing const so sometimes habit gets the best of me.

There's something I never got about it (not saying that you're wrong): as you add nodes (push), the next of the last node you add is always null, and the next of the previous top is the new node.

Therefore, when you do

  stack_node* node_to_delete = stack->top;

  stack->top = stack->top->next;

  free( node_to_delete );

Wouldn't you be deleting "top-1" and setting the temporary node as new top instead? Like "updating" the top instead of reducing the size of the stack?

What I want to do is something like:

node->node->node->node_to_delete->null becomes node->node->node->null

Or have I gotten it wrong from the start and pushing works like
node<-node<-node<-new_node?

Last edited on

firedraco (6243)

Your next pointer should point *down* the stack, since otherwise you would have to walk the entire stack just to figure out what is on top of it.

So yes, you have gotten it wrong from the start, like you thought.

Powdertrail (46)

That solves a huge issue I had. Thanks to Duoas for the example and firedraco for the clarification (would've been great to have my professors tell me this!)

Topic archived. No new replies allowed.

C++

Forum

Pop in O(1) - stacks