C Stacks and Queues

This assignment is intended to have you start working with stacks, queues, and linked lists. There are several parts to the assignment, each described below.

For this assignment, you are provided with some starter code that defines the structures you'll be working with and prototypes the functions youll be writing.

It's important that you dont modify the function prototypes.

To help grade your assignment, we will use a set of unit tests that assume these functions exist and have the same prototypes that are defined in the starter code. If you change the prototypes, it will cause the unit tests to break, and your grade for the assignment will likely suffer. Feel free, however, to write any additional functions you need to accomplish the tasks described below.

In this assignment, your work will be limited to the files list_reverse.c, queue_from_stacks.c, and stack_from_queues.c, where you will implement the functions described below. In addition to the descriptions below, there is thorough documentation in these files describing how each function should behave.

1. Implement a function to reverse a linked list in place

In node.h, a simple structure implementing a node in a singly-linked list is defined. For this part of the assignment, you will implement a function called list_reverse() that takes as an argument a single link structure representing the pointer to the first node of a linked list "first", reverses that list, and returns the new pointer to the first node of the reversed list. This function is prototyped in list_reverse.h, and you will implement it in list_reverse.c. Importantly, you must perform the list reversal in place and may not allocate any new memory in this function.

2. Implement a queue using two stacks

In the files stack.h and stack.c, a simple stack is implemented using a linked list. For the second part of this assignment, you will use two instances of this stack code to implement a queue. In other words, you will implement a queue that uses two stacks to form the underlying container in which data is stored (instead of, for example, a dynamic array or a linked list). For example, when the user calls enqueue() on your queue-from-stacks data structure, it will add the newly-enqueued element into one of the two stacks, as appropriate, and when the user calls dequeue(), your queue-from-stacks will remove the appropriate element from one of the two stacks. To the user of your queue-from-stacks, it will behave just like a normal queue.

The interface of your queue-from-stacks is defined in queue_from_stacks.h, and you must complete each of the functions implementing the queue-from-stacks in queue_from_stacks.c. Each of the functions in queue_from_stacks.c has a function header comment that describes more precisely how it should behave.

Importantly, you may only use the functions prototyped in stack.h to interface with your two stacks, and you may not access the underlying data directly. Also, make sure your queue-from-stacks implementation does not have any memory leaks!

Hint: think of one stack as an "inbox" and one stack as an outbox.

3. Implement a stack using two queues

In the files queue.h and queue.c, a simple queue data structure is implemented. For the third part of this assignment, you will use two instances of this queue data structure to implement a stack. In other words, you will implement a stack that uses two queues to form the underlying container in which data is stored (instead of, for example, a dynamic array or a linked list). For example, when the user calls push() on your stack-from-queues data structure, it will add the newly-pushed element into one of the two queues, as appropriate, and when the user calls pop(), your stack-from-queues will remove the appropriate element from one of the two queues. To the user of your stack-from-queues, it will behave just like a normal stack.

The interface of your stack-from-queues is defined in stack_from_queues.h, and you must complete each of the functions implementing the stack-from-queues in stack_from_queues.c. Each of the functions in stack_from_queues.c has a function header comment that describes more precisely how it should behave.

Importantly, you may only use the functions prototyped in queue.h to interface with your two queues, and you may not access the underlying data directly. Also, make sure your stack-from-queues implementation does not have any memory leaks!

Hint: there are two possible implementations of the stack-from-queues, one with an expensive pop operation and an efficient push operation, and one with an expensive push operation and an efficient pop operation. Whichever of these you choose to implement, the key is knowing where in your two queues the most recently pushed element is. This is always the next element to be popped from the stack.

Testing your work

In addition to the starter code provided, you are also provided with some application code in test.c to help verify that your functions are behaving the way you want them to. In particular, the code in test.c calls the functions you'll implement in this assignment, passing them appropriate arguments, and then prints the results. You can use the provided Makefile to compile all of the code in the project together, and then you can run the testing code as follows:

make
./test

You can see some example output from a correct solution to the assignment in the file example_output.txt.

In order to verify that your memory freeing functions work correctly, it will be helpful to run the testing application through valgrind.

There is also a more extensive unit test suite for all of the functions you'll write for this assignment included in unittest.c. After running make, you can run these unit tests as follows:

./unittest

There are several unit tests included, and if any unit test failures occur, an error message will be printed out indicating the line number in unittest.c from which the failure originated. There are comments above each test that you can read to more thoroughly understand any given test failure.

Example Output

$ ./test
===========================
== Testing list_reverse()
===========================

== Original list contents: 0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225
== Reversed list contents: 225 196 169 144 121 100 81 64 49 36 25 16 9 4 1 0

== Original length=1 list contents: 16
== Reversed length=1 list contents: 16

== Original null list contents: (null)
== Reversed null list contents: (null)


=============================================
== Testing queue-from-stacks implementation
=============================================

== Enqueueing into queue-from-stacks.
== Dequeueing some from queue-from-stacks: front / dequeued (expected)
- 1 / 1 ( 1)
- 3 / 3 ( 3)
- 5 / 5 ( 5)
- 7 / 7 ( 7)
- 9 / 9 ( 9)
- 11 / 11 ( 11)
- 13 / 13 ( 13)
- 15 / 15 ( 15)
== Enqueueing more into queue-from-stacks.
== Dequeueing rest from queue-from-stacks: front / dequeued (expected)
- 17 / 17 ( 17)
- 19 / 19 ( 19)
- 21 / 21 ( 21)
- 23 / 23 ( 23)
- 25 / 25 ( 25)
- 27 / 27 ( 27)
- 29 / 29 ( 29)
- 31 / 31 ( 31)
- 33 / 33 ( 33)
- 35 / 35 ( 35)
- 37 / 37 ( 37)
- 39 / 39 ( 39)
- 41 / 41 ( 41)
- 43 / 43 ( 43)
- 45 / 45 ( 45)
- 47 / 47 ( 47)
== Is queue-from-stacks empty (expect 1)? 1

=============================================
== Testing stack-from-queues implementation
=============================================

== Pushing onto stack-from-queues.
== Popping some from stack-from-queues: top / popped (expected)
- 30 / 30 ( 30)
- 28 / 28 ( 28)
- 26 / 26 ( 26)
- 24 / 24 ( 24)
- 22 / 22 ( 22)
- 20 / 20 ( 20)
- 18 / 18 ( 18)
- 16 / 16 ( 16)
== Pushing more onto stack-from-queues.
== Popping rest from stack-from-queues: top / popped (expected)
- 46 / 46 ( 46)
- 44 / 44 ( 44)
- 42 / 42 ( 42)
- 40 / 40 ( 40)
- 38 / 38 ( 38)
- 36 / 36 ( 36)
- 34 / 34 ( 34)
- 32 / 32 ( 32)
- 14 / 14 ( 14)
- 12 / 12 ( 12)
- 10 / 10 ( 10)
- 8 / 8 ( 8)
- 6 / 6 ( 6)
- 4 / 4 ( 4)
- 2 / 2 ( 2)
- 0 / 0 ( 0)
== Is stack-from-queues empty (expect 1)? 1