logo CodeStepByStep logo


Language/Type: C++ Stack Queue collections
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function named isSorted accepts a reference to a stack of integers as a parameter and returns true if the elements in the stack occur in ascending (non-decreasing) order from top to bottom, else false. That is, the smallest element should be on top, growing larger toward the bottom. An empty or one-element stack is considered to be sorted. For example, if passed the following stack, your function should return true:

bottom {20, 20, 17, 11, 8, 8, 3, 2} top

The following stack is not sorted (the 15 is out of place), so passing it to your function should return a result of false:

bottom {18, 12, 15, 6, 1} top

When your function returns, the stack should be in the same state as when it was passed in. In other words, if your function modifies the stack, you must restore it before returning.

Constraints: You may use one queue or one stack (but not both) as auxiliary storage. Do not declare any other auxiliary data structures (e.g. arrays, Grids, Vectors, etc.), but you can have as many simple variables as you like. Your solution should run in O(N) time, where N is the number of elements of the stack.

Type your C++ solution code here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.