Answers to Selected Exercises Chapter 1

Chapter 5

(a) Yes

(c) Yes

(e) Yes

(g) No

3. (a)

5 16 1 0 (each on a separate line)

(b)

0 5 6 5 (each on a separate line)

5. stack.Push(letter);

letter	X					letter	X
stack.top	4					stack.top	4
.overFlow						.overFlow	T
.underFlow						.underFlow
.items	A	B	C	D	E	.items	A	B	C	D	E
	[0]	[1]	[2]	[3]	[4]		[0]	[1]	[2]	[3]	[4]

{

stack.Pop(secondElement);

}

(b) Set bottom equal to the bottom element in the stack, leaving the stack empty.

while (!stack.IsEmpty())

stack.Pop(bottom);

}

(c) Set bottom equal to the bottom element in the stack, leaving the stack unchanged.

StackType tempStack;

ItemType tempItem;
while (!stack.IsEmpty())

{

stack.Pop(tempItem);

}

bottom = tempItem;

while (!tempStack.IsEmpty())

{

tempStack.Pop(tempItem);

}

}

{

StackType tempStack;

while (!stack.IsEmpty())

{

stack.Pop(tempItem);

}
// restore stack

while (!stack.IsEmpty())

{

tempStack.Pop(tempItem);

copy.Push(tempItem)

}

}

12. (a) Draw a diagram of how the stack might look.

[0]	[1]	[2]	[3]	....	[197]	[198]	[199]

(b)

{

public:

void Push(int item);

void PopLarge(int& item);

void PopSmall(int& item);

private:

int smallTop;

int largeTop;

int items[200];

}

(c)

{

if (item <= 1000)

small++;

}

else

large--;

}

}

void (StackType& stack, ItemType oldItem, ItemType newItem)

{

StackType tempStack;

while (!stack.IsEmpty())

{

stack.Pop(tempItem);

tempStack.Push(newItem);

else

tempStack.Push(tempItem);

// restore stack

while (!stack.IsEmpty())

{

tempStack.Pop(tempItem);

}

}

MAX_ITEMS: Maximum number of items that might be on the stack.

ItemType: Data type of the items on the stack.
Operations (provided by the ADT):

MakeEmpty

Function: Sets stack to an empty state.

Precondition: None

Postcondition: Stack is empty.
Boolean IsEmpty

Function: Determines whether the stack is empty.

Precondition: Stack has been initialized.

Postcondition: Function value = (stack is empty)
Boolean IsFull

Function: Determines whether the stack is full.

Precondition: Stack has been initialized.

Postcondition: Function value = (stack is full)
Push(ItemType newItem, Boolean& error)

Function: Adds newItem to the top of the stack.

Precondition: Stack has been initialized.

Postcondition: If stack is not full, newItem is at the top of the stack and error is false;

otherwise, error is true and the stack is unchanged.

(b) None

An alternative implementation would add an error data member to the class. This error flag would be set if underflow or overflow occurred and the operation would not be performed. A member function would have to be added to the class to allow the user to check the error flag.

20. Yes, this sequence is possible.

22. (a)

5 16 0 3

(b)

6 4 6 0

24. queue.Enqueue(letter);

letter	J					letter	J
queue.front	4					queue.front	4
.rear	3					.rear	3
.overFlow						.overFlow	T
.underFlow						.underFlow
.items	V	W	X	Y	Z	.items	V	W	X	Y	Z
	[0]	[1]	[2]	[3]	[4]		[0]	[1]	[2]	[3]	[4]

letter						letter	V
queue.front	4					queue.front	0
.rear	2					.rear	2
.overFlow						.overFlow
.underFlow						.underFlow	F
.items	V	W	X	Y	Z	.items	V	W	X	Y	Z
	[0]	[1]	[2]	[3]	[4]		[0]	[1]	[2]	[3]	[4]

30. (a) Set secondElement to the second element in the queue, leaving the queue without its original front two elements.

{

queue.Dequeue(secondElement);

}

(b) Set last equal to the rear element in the queue, leaving the queue empty.

while (!queue.IsEmpty())

queue.Dequeue(last);

}

(c) Set last equal to the rear element in the queue, leaving the queue unchanged.

QueType tempQ;

ItemType item;
while (!queue.IsEmpty())

{

queue.Dequeue(last);

}

while (!tempQ.IsEmpty())

tempQ.Dequeue(item);

ueue.Enqueue(item);

}

}

{

QueType tempQ;

{

queue.Dequeue(item);

}

while (!tempQ.IsEmpty())

tempQ.Dequeue(item);

queue.Enqueue(item);

copy.Enqueue(item);

}

}

32. The correct answer for the first statement is (d); the correct answer for the second statement is (a).

(b) Yes

(d) No

(f) Yes

(h) Yes

37.

queue)

{

QueType tempQ;

ItemType item;

int length = 0;

while (!queue.IsEmpty())

{

queue.Dequeue(item);

tempQ.Enqueue(item);

}

while (!tempQ.IsEmpty())

{

tempQ.Dequeue(item);

queue.Enqueue(item);

length++;

}

return length;

}

39. The second else-clause is only executed if both queues are not empty, but one had to be empty for the loop to be exited, so only one can be empty. Therefore, string1 can only be assigned a value from one queue or the other but not both.

42. No, this sequence is not possible.

44.

#include "StackType.h"

#include

bool IsOpen(char symbol);

bool IsClosed(char symbol);

bool Matches(char symbol, char openSymbol);
int main()

{

using namespace std;

char symbol;

StackType stack;

bool balanced = true;

char openSymbol;

try

{

cout << "Enter an expression and press return."

<< endl;

cin.get(symbol);

while (symbol != '\n' && balanced)

{

if (IsOpen(symbol))

stack.Push(symbol);
else if (IsClosed(symbol))

{

if (stack.IsEmpty())

balanced = false;

else

{

openSymbol = stack.Top();

stack.Pop();

balanced = Matches(symbol, openSymbol);

}

}

cin.get(symbol);

}

}

catch (FullStack error)

{

cout << "Push called when the stack is full." << endl;

return 1;

}

catch (EmptyStack error)

{

cout << "Top or Pop called when stack is empty."

<< endl;

return 1;

}
if (balanced)

cout << "Expression is well formed." << endl;

else

cout << "Expression is not well formed." << endl;

return 0;

}

bool IsOpen(char symbol)

{

if ((symbol == '(') || (symbol == '{') || (symbol == '['))

return true;

else

return false;

}
bool IsClosed(char symbol)

{

if ((symbol == ')') || (symbol == '}') || (symbol == ']'))

return true;

else

return false;

}
bool Matches(char symbol, char openSymbol)

{

return (((openSymbol == '(') && symbol == ')')

|| ((openSymbol == '{') && symbol == '}')

|| ((openSymbol == '[') && symbol == ']'));

}

Directory: samples
samples -> Running head: capstone project
samples -> Memorandum of understanding long beach city college- long beach unified school district
samples -> Cell Phone Antennas: a look at the history and design of vhf antennas
samples -> Affinity program guidelines
samples -> Chapter 2: Setting Up Your Android Development Environment Multiple Choice Questions
samples -> High School Musical
samples -> Finance crisis Introduction
samples -> Android Application Development: Working with the Emulator
samples -> -

Download 0.49 Mb.

Share with your friends: