lab_quacks
Spiteful Stacks and Questionable Queues
QuackFun Namespace Reference

Namespace to contain the stack and queue functions for this lab. More...

Functions

template<typename T >
sum (stack< T > &s)
 Sums items in a stack. More...
 
bool isBalanced (queue< char > input)
 Checks whether the given string (stored in a queue) has balanced brackets. More...
 
template<typename T >
void scramble (queue< T > &q)
 Reverses even sized blocks of items in the queue. More...
 
template<typename T >
bool verifySame (stack< T > &s, queue< T > &q)
 

Detailed Description

Namespace to contain the stack and queue functions for this lab.

Function Documentation

template<typename T >
T QuackFun::sum ( stack< T > &  s)

Sums items in a stack.

Parameters
sA stack holding values to sum.
Returns
The sum of all the elements in the stack, leaving the original stack in the same state (unchanged).
Note
You may modify the stack as long as you restore it to its original values.
You may use only two local variables of type T in your function. Note that this function is templatized on the stack's type, so stacks of objects overloading the + operator can be summed.
We are using the Standard Template Library (STL) stack in this problem. Its pop function works a bit differently from the stack we built. Try searching for "stl stack" to learn how to use it. Think recursively!
bool QuackFun::isBalanced ( queue< char >  input)

Checks whether the given string (stored in a queue) has balanced brackets.

A string will consist of square bracket characters, [, ], and other characters. This function will return true if and only if the square bracket characters in the given string are balanced. For this to be true, all brackets must be matched up correctly, with no extra, hanging, or unmatched brackets. For example, the string "[hello][]" is balanced, "[[][[]a]]" is balanced, "[]]" is unbalanced, "][" is unbalanced, and "))))[cs225]" is balanced.

For this function, you may only create a single local variable of type stack<char>! No other stack or queue local objects may be declared. Note that you may still declare and use other local variables of primitive types.

Parameters
inputThe queue representation of a string to check for balanced brackets in
Returns
Whether the input string had balanced brackets
template<typename T >
void QuackFun::scramble ( queue< T > &  q)

Reverses even sized blocks of items in the queue.

Blocks start at size one and increase for each subsequent block.

Parameters
qA queue of items to be scrambled
Note
Any "leftover" numbers should be handled as if their block was complete.
We are using the Standard Template Library (STL) queue in this problem. Its pop function works a bit differently from the stack we built. Try searching for "stl stack" to learn how to use it. You'll want to make a local stack variable.
template<typename T >
bool QuackFun::verifySame ( stack< T > &  s,
queue< T > &  q 
)
Returns
true if the parameter stack and queue contain only elements of exactly the same values in exactly the same order; false, otherwise.
Note
You may assume the stack and queue contain the same number of items!
The back of the queue corresponds to the top of the stack!
There are restrictions for writing this function.
  • Your function may not use any loops
  • In your function you may only declare ONE local boolean variable to use in your return statement, and you may only declare TWO local variables of parametrized type T to use however you wish.
  • No other local variables can be used.
  • After execution of verifySame, the stack and queue must be unchanged. Be sure to comment your code VERY well.