### Understanding how to implement a stack using an array vs. linked list.

## Understanding how to implement a stack using an array vs. linked list.

Practicing with the use of Stacks in certain applications

Instructions:

Important note: The source code for

class stackADT (p 398, an abstract class implementing a stack as an ADT),

class stackType (p 400, an array implementation of a stack ) and

class linkedStackType (p 416, a linked list implementation of a stack)

as given in the textbook is available inside Labs -> Lab Files-> Lab6.zip in Blackboard. You will need to use some or all of these files to complete the exercises below.

1. Partially implementing a stack: Adapted from #3 and #4 in page 447 of the textbook

Your job is to add the following operation to the class stackType (p 400, an array implementation of a stack) given in the textbook:

void reverseStack(stackType<Type> &otherStack);

This operation copies the elements of a stack in reverse order onto another stack. Consider the following statements:

stackType<int> stack1;

stackType<int> stack2;

The statements

stack1.reverseStack(stack2);

copies the elements of stack1 onto stack2 in reverse order. That is,the top element of stack1 is the bottom element of stack2, and so on.The old contents of stack2 are destroyed and stack1 is unchanged.

Write the definition of the function template to implement the operation reverseStack.

2. Repeat Exercises 1-1 above for class linkedStackType (p 416, a linked list implementation of a stack).

Save your stackType.h as stackType-6-1-yourName.h and linkedStackType.h as linkedStackType-6-1.h for submission. Also, write a test program to show how your new opetation works for both classes stackType and linkedStackType. Save your test program as lab6-1-yourName.cpp for submission.

2. Applications of stacks, adapted from #5 in page 447.

Write a program that takes as input an arithmetic expression. The program outputs whether the expression contains matching grouping symbols. For example, the following arithmetic expressions contain matching grouping symbols.

[10 + (3 – 6) * 8];

(10 + [3 – 6] * 8);

(10 + (3 – 6) * 8);

(((3 – 6)));

7 + 8 * 2;

However, the following arithmetic expressions do not contain matching grouping symbols.

7 + (8 * 2;

[7 + (8 * 2];

You can assume that only matching grouping symbols are[ ] and ( ) in the expressions.

You can assume that only arithmetic operators +, - , *, / are used in the expressions.

Your program must use a stack to do the job. You can include and use either class stackType (p 400, an array implementation of a stack ) or linkedStackType (p 416, a linked list implementation of a stack) given in the text book to write your program.

Save your program as lab6-2-yourname.cpp for submission- Please do not submit the class stackType.h and linkedStackType.h files as you will not need to touch and change these files for this exercise.

3. Applications of stacks

A palindrome is a string that reads the same both forward and backward. For example, "madam" or "anna" are two palindromes. Write a program that will use a stack to decide if a given string is a palindrome. You can include and use either class stackType (p 400, an array implementation of a stack ) or linkedStackType (p 416, a linked list implementation of a stack) given in the text book to write your program.

Save your program as lab6-3-yourname.cpp for submission- Please do not submit the class stackType.h and linkedStackType.h files as you will not need to touch and change these files for this exercise.

## Comments

## Post a Comment