Objectives

In this Lab, you will practise:

• working with stacks and queues

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples

Getting Started

Login and run following commands inside a Unix terminal

Create a new directory for this lab called lab10 by typing:

mkdir lab10

Change to this directory by typing:

cd lab10

Exercise 0: MyExperience

The 2023 T2 myExperience Survey is now open for you to complete.

The myExperience Survey is an anonymous Survey run by UNSW

The myExperience Survey allows you to provide feedback about the course, lectures, a tutorials.

The myExperience Survey feedback is used to improve the course content,
and helps both lecturers and tutors improve there teaching style.

Remember that the survey is anonymous and responses are only released to us after your marks have been finalized, so be honest and provide constructive criticism.

You can access myExperience with the following link:
https://myexperience.unsw.edu.au/

Autotests and Freeing Memory

As you know, every time we use malloc, we need to use a corresponding free when we are finished with the memory. If we don't we will use more and more memory as our program runs. It is given back to the system as soon as the program terminates, so for our short toy programs it has not been an issue.

However, users do not want memory leaks in their ADTs. So in this lab and the next lab we want to make sure you correctly implement your destroy functions (that free all the memory for the ADT) and use them correctly in your client program so we know that you can manage your memory accurately.

We will be testing your programs with the additional --leak-check option for dcc. For example

dcc --leak-check -o prog prog.c

So your program will need to generate the correct output AND free all malloced memory to pass the autotests.

Exercise 1: Balancing Brackets

In this exercise you are going to use a stack that checks whether brackets are balanced.

A text file contains three different types of brackets: round brackets ( ) square brackets [ ] and curly brackets { }.
The task is to read a file one character at a time and determine whether the brackets are "balanced" - in the sense that every opening bracket is matched by an appropriately-placed closing bracket of the same type.

Get a copy of the Stack.h and Stack.c files we wrote in lectures.

$ cp ~cs1911/public_html/23T2/lec/14-9_stacksAndQueues/code/Stack.* .

Note: The stack we wrote is a stack of ints. This will still work for chars.

Write a C program balanced.c which reads characters from stdin with getchar and indicates whether the brackets are balanced.

It should stop either at end-of-input or when it reaches an unbalanced bracket.

Ignore characters other than brackets.

It should use a single stack to track brackets as discussed in the tute.

Don't forget to #include Stack.h at the top of balanced.c

Make it behave like this:

$ dcc  balanced.c Stack.c -o balanced
$ ./balanced
([{}()])([]){}
Yes, balanced.
./balanced
({(()([])])
No, not balanced.
./balanced
((([]{}))
No, not balanced.
./balanced
[]}()
No, not balanced.
./balanced
sizeof (struct list_node)
Yes, balanced.
./balanced
Potato
Yes, balanced.

Also as usual autotest is available to test your program.

$ 1911 autotest lab10 balanced.c

(Optional) Challenge Exercise 1: Implementing a Queue

Get a copy of the following files

$ cp ~cs1911/public_html/23T2/tlb/10/Queue.h .
$ cp ~cs1911/public_html/23T2/tlb/10/testQueue*.c .

The first file has the prototypes for our Queue functions and the other files will help us test our Queue once we have written it.

For this exercise you need to implement a Queue. To do this you must create a file named Queue.c.

It should do the following

• #include "Queue.h"
• define a struct named struct queue ( you must decide what needs to be stored in the struct)
• write code for all the functions defined in Queue.h
  • For createQueue, you are passed in the maximum Size for the queue, instead of using a #define constant (like we did in Stack.h and Stack.c)
  • For the enqueue function: If the queue is full you should print "Queue full\n" to standard error, free the queue and exit the program with EXIT_FAILURE
  • For the top and dequeue function: If the queue is empty you should print "Queue empty\n" to standard error, free the queue and exit the program with EXIT_FAILURE

To test your programs you can use the test files we have provided, which we will also use in the autotesting. There are 4. testQueue1.c, testQueue2.c, testQueue3.c, testQueue4.c

For example to compile and run testQueue1.c, do the following

dcc -o testQueue1 testQueue1.c Queue.c
./testQueue1

Also as usual autotest is available to test your program.

$ 1911 autotest lab10 Queue.c

(Optional) Challenge Exercise 2: Realloced Stack

Implement the same stack data type instead using a a malloced array which is grown with realloc as needed so there is no limited on how many items can be stored in the stack.

You should implementing the re-sizing in the following way:

• When an attempt is made to push an item onto a stack that is already full, the array is resized to accomodate the extra element. Make sure the stack is only resized when it is full and make the resized array be 2 times bigger.
• Also when the size of the stack drops below 1/4 of the size of the array, the array size should be resized to half of its size. However the array size should never drop below its original starting size.
• Make the default starting size 5 (we are making it smaller than you would in reality so we can more easily test it).

Put this in StackRealloc.c

Of course you should #include Stack.h again and balanced.c should work with StackRealloc.c without changes.

dcc balanced.c StackRealloc.c -o balancedRealloc
./balancedRealloc
([{}()])([]){}
Yes, balanced.

You should also get a copy of the following files to test your stack with

cp ~cs1911/public_html/23T2/tlb/10/testStack*.c .

Note: our autotests will only check that your stack still functions and can grow bigger that the default size of the stack, your tutor will also need to check whether your stack is growing and shrinking accordingly.

$ 1911 autotest lab10 StackRealloc.c

(Optional) Challenge Exercise 3: Changing the Queue Implementation

For this challenge you will create a different implementation of a Queue in a file named CircularQueue.c

In your original queue implementation, most likely, when an item was removed, all the remaining items were shifted down one place in the array. (Or you may have done your queue in the opposite way and you may have needed to shift items across when you added elements to the queue). This means iff we have n items in the array, we would need to shift approximately n items.

To make our queue more efficient, modify your queue so you store the index of the start of the queue and the end of the queue. This way when you remove an element you do not have to shift all the elements over one place, you can just update the index of the start of the queue. Note: your indexes may need to wrap around again to 0 in some situations.

You should also still make sure your implementation checks that the queue never exceeds its maximum and that it never trys to get an element from an empty queue. In this case you should still print the error message (to standard error) and exit the program. (Unlike the previous challenge question, you do not have to resize the array when it becomes full).

Note: Your queue should still produce the same output as it did before, it is just that it will be more efficient. You can test it with the testQueue1.c etc files you used in exercise 2.

Note: our autotests will only check that your queue still functions your tutor will also need to you have implemented it according to the instructions.

$ 1911 autotest lab10 CircularQueue.c

Submission/Assessment

When you are satisfied with your work, ask your tutor to assess it. You are to submit it electronically by typing (run this command in your lab10 directory):

give cs1911 lab10 balanced.c Queue.c StackRealloc.c CircularQueue.c

Submit advanced exercises only if you attempt the advanced exercise.

Remember the lab assessment guidelines - if you don't finish the exercises you can finish them in your own time, submit them by 19:59:59 Sunday using give and ask ask tutor to assess them at the start of the following lab.

You can also just run the autotests without submitting by typing

1911 autotest lab10