Writing a push and pop in c

Question

Original Q: I'm trying to create this calculator in C for a project. I got the math functions working, but not I am stuck on how to handle the push an pop. Can somebody help me get started? I know what push and pop are supposed to do from java, but I am not sure how to use them without using nodes or an array.

My includes and stack struct:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "stack.h"
#include "debug.h"

#define DEFAULT_CAPACITY 16

struct stack {
   size_t capacity;
   size_t size;
   stack_item *data;
};

My attempted push and pop:

UPDATED

    void push_stack (stack *this, stack_item item) {
   if (full_stack (this)) realloc_stack (this);  
   this->data[this->size++]=item;
}

stack_item pop_stack (stack *this) {
   assert (! empty_stack (this)); 
   if(this->data == NULL){
     fprintf(stderr, "fail");}
   else{
    stack_item tempPop = this->data[this->size--];   
    return tempPop;}
}

Updated Q: This is now what I am doing for my push/pop method. I am getting no warnings and no errors, but when I run it, it seg faults after it should pop.

My new question is, does it appear that something I am doing in this block of code is causing my seg fault?

Answer 1

//Validation sample code of behavior

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if 0
 #include "stack.h"
 #include "debug.h"
#else
 typedef char* stack_item;
#endif

#define DEFAULT_CAPACITY 16

struct stack {
   size_t capacity;
   size_t size;
   stack_item *data;
};

typedef struct stack stack;

stack *Stack(void){
    stack *s = malloc(sizeof(stack));
    s->capacity = DEFAULT_CAPACITY;
    s->size = 0;
    s->data = malloc(s->capacity * sizeof(stack_item));
    return s;
}

int full_stack(stack *this){
    return this->capacity == this->size;
}

int empty_stack(stack *this){
    return this->size == 0;
}

void realloc_stack(stack *this){
    this->capacity += DEFAULT_CAPACITY;
    this->data = realloc(this->data, this->capacity*sizeof(stack_item));
}

void push_stack (stack *this, stack_item item) {
    if (full_stack (this))
        realloc_stack (this);  
    this->data[this->size++]=item;
}

stack_item pop_stack (stack *this) {
    assert (!empty_stack (this)); 
    if(this->data == NULL){
        fprintf(stderr, "fail");
        exit(1);//Maybe malloc or realloc
    }
    return this->data[--(this->size)];
}

int main(void){
    stack *s = Stack();
    push_stack(s, "sin");
    push_stack(s, "+");
    push_stack(s, "cos");
    while(!empty_stack(s)){
        puts(pop_stack(s));
    }
    //Stack_(s);//call destructor
    return 0;
}

Answer 2

I understand what you mean when you say "I know what push and pop are supposed to do from java", but please bear in mind that push and pop are just operations that you can do to a data structure that is known as a stack. A stack is more of an idea and that concept can be implemented in any language.

To start of, I would advice you not to use a array. A stack imposes an order in the way you access elements and its perfectly fine with a nice linked list because you only need to remove from the head and add elements to the same head. You typically use an array when you want to access elements at any position in O(1) complexity. The effect of using a linked list is that you dont really have a bound in the number of elements you can add to the stack (unless you really want to).

If you decide to go for a linked list I would advice you to use two structures:

struct stack_node {
    int data;
    stack_node* next;
};

struct stack {
    int current_size;
    int max_size;
    struct stack_node head;
};

The you can always do

void push(struct stack* s, int x){
    if(s->max_size > s->current_size+1){
        add to the stack
    } else {
        stack is full!!
    }
}

int pop(struct stack* s) {
     if(s->current_size == 0){
         Ops! No data in stack, throw error or something
      } else {
         return head and remove item from stack
     }
 }

Note that this is only a template to give you an idea... Also, I dont really understand in your code what does "realloc_stack". I think the main problem in your code is that you might still be in a bit of a java minset and programming C requires you to think a bit more low level and do more thinks yourself...

Answer 3

Use linked lists.

struct stack_element {
    struct stack_element* next; // reserved for stack control
    int data0; // whatever
    int data1;
    int data2;
};

void push_stack(struct stack_element** stack, struct stack_element* element)
{
    element->next = *stack;
    *stack = element;
}

struct stack_element* pop_stack(struct stack_element** stack)
{
    struct stack_element* element = *stack;
    if (element)
        *stack = element->next;
    return element;
}

struct stack_element* stack = NULL; // your stack. its empty

Creating new stack element and adding to stack:

struct stack_element* element = malloc(sizeof(struct stack_element)); // created new element
element->data0 = 123;
element->data1 = 456;
element->data2 = 789;
push_stack(&stack, element); // stored in stack

Fetching an element from stack:

struct stack_element* element = pop_stack(&stack);
if (element == NULL)
    printf("Stack was empty, no elements to fetch.");

PS: The same element can never be pushed to the stack more than once.

You can also have the stack control separated from the data, in which case you will be able to store the same element more than once:

struct stack_control {
    struct stack_control* next;
    void* data;
};

void push_stack(struct stack_control** stack, void* data)
{
    struct stack_control* temp = malloc(sizeof(struct stack_control));
    temp->data = data;
    temp->next = *stack;
    *stack = temp;
}

void* pop_stack(struct stack_control** stack)
{
    void* data = NULL;
    struct stack_control* temp = *stack;
    if (temp)
    {
        data = temp->data;
        *stack = temp->next;
        free(temp);
    }
    return data;
}

struct stack_control* stack = NULL; // empty stack

This code the way it is can be used to stack pointers of any type, because void* is generic.