Skip to main content

Program Design

Exercises​

Question 19.1​

A queue is similar to a stack, except that items are added at one end but removed from the other in a FIFO (first-in, first-out) fashion. Operations on a queue might include:

  • Inserting an item at the end of the queue
  • Removing an item from the beginning of the queue
  • Returning the first item in the queue (without changing the queue)
  • Returning the last item in the queue (without changing the queue)
  • Testing whether the queue is empty

Write an interface for a queue module in the form of a header file named queue.h.

queue.h
#ifndef QUEUE_H
#define QUEUE_H

#include <stdbool.h>      /* C99 Only */

typedef int Item;

//  Here, we are assuming to use a queue of fixed size. So, the struct queue_type will have the following members:
//    struct queue_type {
Login to view full code

Question 19.2​

Modify the stack2.c file to use the PUBLIC and PRIVATE macros.

  • Makefile
  • main.c
  • stack.c
  • stack.h

Question 19.3​

  1. Write an array based implementation of the queue module described in Exercise 1. Use three integers to keep track of the queue's status, with one integer storing the position of the first empty slot in the array (used when an item is inserted), the second storing the position of the next item to be removed, and the third storing the number of items in the queue. An insertion or removal that would cause either of the first two integers to be incremented past the end of the array should instead reset the variable to zero, thus causing it to "wrap around" to the beginning of the array.
  2. Write a linked-list implementation of the queue module described in Exercise 1. Use two pointers, one pointing to the first node in the list and the other pointing to the last node. When an item is inserted into the queue, add it to the end of the list. When an item is removed from the queue, delete the first node in the list.
  • Makefile
  • main.c
  • queue_1.c
  • queue_1.h
  • queue_2.c
  • queue_2.h

Question 19.4​

  1. Write an implementation of the Stack type, assuming that Stack is a structure containing a fixed-length array.
  2. Redo the Stack type, this time using a linked-list representation instead of an array. (Show both stack.h and stack.c.)
  • Makefile
  • stackADT.c
  • stackADT.h
  • stackclient.c

Question 19.5​

Modify the queue.h header of Exercise 1 so that it defines a Queue type, where Queue is a structure containing a fixed-length array (see Exercise 3(a)). Modify the functions in queue.h to take a Queue * parameter.

  • Makefile
  • main.c
  • queue.c
  • queue.h

Question 19.6​

  1. Add a peek function to stackADT.c. This function will have a parameter of type Stack. When called it returns the top item on the stack but doesn't modify the stack.
  2. Repeat part (a), modifying stackADT2.c this time.
  3. Repeat part (a), modifying stackADT3.c this time.

Question 19.7​

Modify stackADT2.c so that a stack automatically doubles in size when it becomes full. Have the push function dynamically allocate a new array that's twice as large as the old one and then copy the stack contents from the old array to the new one. Be sure to have push deallocate the old array once the data has been copied.

  • Makefile
  • main.c
  • stackADT3.c
  • stackADT3.h

Programming Projects​

Project 19.1​

Modify Programming Project 1 from Chapter 10 so that it uses the stack ADT described in Section 19.4. You may use any of the implementations of the ADT described in that section.

  • Makefile
  • main.c
  • stackADT.c
  • stackADT.h

Project 19.2​

Modify Programming Project 6 from Chapter 10 so that it uses the stack ADT described in Section 19.4. You may use any of the implementations of the ADT described in that section.

  • Makefile
  • main.c
  • stackADT.c
  • stackADT.h

Project 19.3​

Modify the stackADT3.c file of Section 19.4 by adding an int member named len to the stack_type structure. This member will keep track of how many items are currently stored in a stack. Add a new function named length that has a Stack parameter and returns the value of the len member. (Some of the existing functions in stackADT3.c will need to be modified as well.)Modify stackclient.c so that it calls the length function (and displays the value that it returns) after each operation that modifies a stack.

  • Makefile
  • main.c
  • stackADT4.c
  • stackADT4.h

Project 19.4​

Modify the stackADT.h and stackADT3.c files of Section 19.4 so that a stack stores values of type void *, as described in Section 19.5; the Item type will no longer be used. Modify stackclient.c so that it stores pointers to strings in the s1 and s2 stacks.

  • Makefile
  • main.c
  • stackADT.c
  • stackADT.h
  • stackADT4.c

Project 19.5​

Starting from the queue.h header of Exercise 1, create a file named queueADT.h that defines the following Queue type:

typedef struct queue_type *Queue;

queue_type is an incomplete structure type. Create a file named queueADT.c that contains the full definition of queue_type as well as definitions for all the functions in queue.h. Use a fixed-length array to store the items in a queue (see Exercise 3(a)). Create a file named queueclient.c (similar to the stackclient.c file of Section 19.4) that creates two queues and performs operations on them. Be sure to provide create and destroy functions for your ADT.

  • Makefile
  • main.c
  • queueADT.c
  • queueADT.h

Project 19.6​

Modify Programming Project 5 so that the items in a queue are stored in a dynamically allocated array whose length is passed to the create function.

The given question is already done in Exercise 3(a). It contains the full queue ADT - with wrap around functionality - as well as a client file (exercise_3) which contains the implementation of the ADT.

Project 19.7​

Modify Programming Project 5 so that the items in a queue are stored in a linked list (see Exercise 3(b)).

The given question is already done in Exercise 3(b). It contains the queue ADT implemented using linked list. The implementation of the queue ADT is shown in exercise_3.c file which contains two different queueADT implementations.

Contents

Edit this page