Monash University > CSSE > CSE1303 > Part A > Tutorials > Tutorial A2

CSE1303 Computer Science
Summer Semester, 2003
Part A
Tutorial A2 : Stacks and Queues

This tute covers material from lectures A03 to A04.

There may not be time in the tutorial to cover all of these questions. Attempt at least the ones marked with an asterisk before the tutorial; these are the ones that will be focussed on during the class. If you have specific questions about unmarked questions, you can ask the tutor about them during the tutorial. If you want further revision questions, suggestions of questions from the textbooks are provided at the end of the tutorial sheet.

---

Note: The purpose of tutorials is not simply to give you the answers to these questions! (Solutions will be released in about a week online, so if all you want is the answers, there are easier ways.)

---

* Exercise 1

Assume MAXSTACK has been defined as 5, and Stack and the functions operating on Stack have been defined as in lectures. Show the contents of theStack after each pop and push in the following code. For theStack.entry show only the items in the array which correspond to items on the stack.

float x;
float y;
Stack theStack;

initializeStack(&theStack);

push(&theStack, 1.2);
push(&theStack, 1.0);
x = pop(&theStack);
y = pop(&theStack);
push(&theStack, y - x);
push(&theStack, 4.9);
push(&theStack, 5.1);
x = pop(&theStack);
y = pop(&theStack);
push(&theStack, y + x);
x = pop(&theStack);
y = pop(&theStack);
y *= x;

What is the value of y at the end of the computation?

Exercise 2

Write a C function float topElement(const Stack* stackPtr) which returns the top element of the stack and doesn't change the stack.

Exercise 3

Write a C function void printStack(const Stack* stackPtr) which prints all the elements in the stack, from the top down, and doesn't change the stack.

Exercise 4

Write a C function int stackSize(const Stack* stackPtr) which returns the number of items in the stack, but doesn't change the stack.

* Exercise 5

Assume MAXQUEUE has been defined as 5, and Queue and the functions operating on Queue have been defined as in lectures. Show the contents of theQueue after each append and serve. For theQueue.entry show only those items in the array that correspond to items in the queue.

float x;
int n = 10;

Queue theQueue;
initializeQueue(&theQueue);

while (n != 0 && !queueFull(&theQueue))
{
  append(&theQueue, n);
  n /=  2;
}

while (!queueEmpty(&theQueue))
{
  x = serve(&theQueue);
  append(&theQueue, --x);

  if (x > 4)
  {
    break;
  }
}

What is the value of x at the end of the computation?

Exercise 6

Write a C function void printQueue(const Queue* queuePtr) which prints all the items in the queue, from front to rear, and doesn't change the queue.

Exercise 7

Assume that Queue has been declared as above. Design and code a function reverseQueue(Queue* queuePtr) that uses a stack of floats to reverse all the entries of a given queue. Use only the functions given in lectures. You may assume that the queue and the stack can contain the same number of objects.

* Exercise 8

(Preparation for the prac)
Reverse Polish notation is a different way of entering mathematical expressions which does not have the precedence problems that "infix" notation does. The table below is also in the prac notes, and explains how "infix" notation is translated to reverse Polish.

Infix	Reverse Polish
a + b*c	a b c * +
a + (b*c)	a b c * +
(a + b)*c	a b + c *
a*b + c	a b * c +
a*(b + c)	a b c + *
(a + b)*(c - d)	a b + c d - *
(a + b)*(c - d)/(e + f)	a b + c d - * e f + /




Write the following 'infix' expressions in Reverse Polish Notation

(a)     (8 + 7) * (3 + 2) + 4 / 3
(b)     (3 - 4 + 2) * 7 + 1

Write the following Reverse Polish expressions in infix notation

(c)     5 3 + 4 7 - * 2 /
(d)     7 2 3 + * 5 -

ADDITIONAL EXERCISES

Kruse et al.
    Exercises 3.1 E6 4.3 E4, E8, E9,
    Review 3.1 Q1
    Review 4.1 Q1, 2, 3


Deitel & Deitel (2^nd Edition)
    Self Review Exercises 12.1 a, e, j, 12.3
    Exercises 12.10, 12.11, 12.12

[ Top | Home ]

Last modified: Tuesday 02 December 2003 22:29:33