C programming

A stack is a data structure that stores a sequence of data, and that provides (at least) two functions: push , which puts an element first (on top) of the stack, and pop , which removes the first element. (In other words, it is a LIFO: "last in first out".) You can use a stack in many different contexts, but one example is to make a calculator: a program that can calculate various compound expressions and functions. In this task, you must implement a stack containing floating-point numbers of type double , using a linked list. Create two files, a double_stack.h and a double_stack_list.c . The H file should contain the specification for the stack data type, but nothing about the implementation itself. Implementation should instead be in the C file. In order to encapsulate (hide) the implementation, you must declare the following in the H file:

typedef struct double_stack_struct double_stack;

So we say that the type double_stack should be the same as a type called struct double_stack_struct . However, this is an incomplete data type, because we have only declared it and not said what the struct actually contains! But as long as we only handle pointers to double_stack, it doesn't matter. However, we will not be able to dereference such a pointer, except in the code located in double_stack_list.c .

You get to write down the actual implementation of the struct double_stack_structi C file:

struct double_stack_struct{ /***/ };

To be able to encapsulate the actual implementation, you need to implement a function create_stack that creates an empty stack. This is so that the user does not have to know which data structure the stack uses internally. Because outside of the file double_stack_list.c you cannot use the incomplete type, but only pointers to it, we must in this way give the user a pointer that he can use. This function thus constitutes a kind of "stack factory" (or constructor), which outputs a pointer to a new empty stack, which the person who wants to use the stack can work with. Let the function have the following prototype:

double_stack*create_stack();

This function should therefore create an empty list, and return a pointer to it. For it to work, the list must be created dynamically (on the heap), i.e. with malloc . Otherwise, the list created in the function would automatically disappear after the function exits, and the pointer we get back would not be valid anymore. In other words, create a double_stack * stack = malloc( sizeof( double_stack ) ); and return that pointer.

Test that you can build a small test program that uses your code, and just includes double_stack.h and creates a new double_stack* using create_stack.

#include "double.stack.h" int main(int argc, char *argv[]){ double_stack*stack; stack = creat_stack(); return 0; }

This program should be able to compile, even if it produces no visible output when run.

Implement the push function to put new elements on the stack. int push(double_stack*stack, double d);

This function thus takes a pointer to a (possibly empty) stack and a number as input. It should return 1 if everything went well, and 0 otherwise.

Now your test program might look like this. #include "double_stack.h" int main(int argc, char *argv[]){ double_stack*stack; stack = creat_stack(); //empty stack push(stack,1); //now the stack contains 1 push(stack,2); //now the stack contains 2,1 return 0; }

also implement the function pop int pop(double_stack*stack, double*d);

which removes the top element from the stack and puts it where d points to. The function should also return 1 if everything went well, and 0 if it failed to pop (if the stack was empty).

Now in your double_stack.h you have a complete interface for a stack containing floating-point numbers, with all the necessary functions. Finally, create a test program that puts some numbers (taking them as arguments via argv as before) into a stack, and then pops them one by one and prints them, each on a new line.

./task 1 2 3 4 5 5.0000 4.0000 3.0000 2.0000 1.0000

Since there is no function that can check if the stack is empty or not, you have to make sure yourself that you pop as many elements as you have pushed. The program should work regardless of how many numbers come in via argv, not only for five as in the example above. It is not an acceptable solution to, for example, build a list and print it. You should pop one element at a time, and print the result of pop .