- 作业标题：CSCI 2122 - Systems Programming - lab6 Queues, Stacks, and Binary Trees
- 课程名称：Dalhouse University CSCI 2122 Systems Programming
- 完成周期：2天
1. Introduction
This lab is designed to introduce you to queues, stacks, and binary trees. By the end of this lab, you will be expected to understand those concepts. In the next lab we will be expanding your trees to encompass heaps (priority queues) and we will be using queues and stacks to perform depth-first and breadth-first searches, so it’s important that you do your best to understand the concepts laid out below. In this lab you are expected to perform the basics of cloning your Lab 6 repository from the GitLab course group. A link to the course group can be found here and your repository can be found in the Lab6 subgroup. See the Lab Technical Document for more information on using git. You will notice that your repository has a file in the Lab6 directory named delete this file. Due to the limitations of GitLab, we are not able to push completely empty directories. Before you push your work to your repository (which should be in the Lab6 directory anyway), make sure to first use the git rm command to remove the extra file. If you do not, your pipeline could fail.
2. 2 Queues
A queue is a common data structure which performs operations in a “first in, first out” order. This is often abbreviated as FIFO. A common analogy is to imagine that you are in line at the bank. The first person in line will be the first person served at one of the tellers. In this case, it’s a first come, first served situation where the first “thing” added to the queue is also the first thing we work with when the time comes to do some processing.
In this lab, your task will be to implement a queue using any designs or libraries of your own make, including ones you have written before in this class. The goal is that your queue should be able to hold any reasonable number of items such that we are able to minimally perform the three basic queue operations: enqueue, dequeue, and peek. In addition to the three basic queue operations, you’ll also be expected to provide size and contains function.
Your queue will have an initialization function, which should return a pointer to a typedefed struct called Queue (see the Queue contract for more information). It should start as an array or list (your choice) and should have no elements in it to start. Similar to previous labs, your queue will hold typeless data in the form of void pointers so that you don’t have to worry about creating hard-typed queues.
2.1. enqueue
Whenever a user wants to add an item to a queue, they will need to call the enqueue function. The enqueue function should accept a pointer to a Queue and a pointer to an element, then add that element to one end of its list. This can be at the start of the list or the end of the list, as long as you are consistent every time. Every time an element is added, the size of your queue should increase.
2.2. dequeue
Whenever a user wants to retrieve an item from a queue, they will need to call the dequeue function. The dequeue function should accept a pointer to a Queue, then remove and return the item which has been in the queue the longest in the form of a void pointer. Every time an element is removed, the size of your queue should decrease. The item removed should be from the opposite end of the list compared to where you add (enqueue) them.
2.3. peek
A user is allowed to look at whatever the current oldest item is in your queue using the peek function. The peek function should accept a pointer to a Queue, then return a void pointer representing the item at the front of the queue, which should be the oldest item. Since the item is not removed, the size of the queue should not change.
2.4. 2.4 size
The size function should return the number of items remaining in a Queue. It will accept a pointer to a Queue and return an integer representing the number of items currently in that queue.
2.5. 2.5 contains
The contains function will accept a pointer to a Queue and a void pointer to an element, then return true if the element is currently in the queue. If the element is not in the queue, this should return false instead.
3. Lab 6 Function Contracts
In this lab you will be responsible for fulfilling three lab contracts: the Queue contract, the Stack contract, and the Binary Tree contract. Each contract is designed to test you on some of the things you’ve learned throughout the instruction portion of this lab.
All contracts must be completed exactly as the requirements are laid out. Be very careful to thoroughly read the contract instructions before proceeding. This does not, however, preclude you from writing more functions than you are asked for. You may write as many additional functions as you wish in your C source files.
All contracts are designed to be submitted without a main function, but that does not mean you cannot write a main function in order to test your code yourself. It may be more convenient for you to write a C source file with a main function by itself and take advantage of the compiler’s ability to link files together by accepting multiple source files as inputs. When you push your code to Gitlab, you don’t need to git add any of your extra main function source files.
The programs you write for this lab will not be compiled with any additional libraries by us, although your repository and Makefiles can include/compile any additional libraries or files you need.
For those of you who are concerned, when deciding which naming conventions you want to use in your code, favour consistency in style, not dedication to a style that doesn’t work.
The contracts in this document are worth the following points values, for a total of 10.
。。。
