Stacks are restricted linear lists of data where additions and deletions are made only at one end, called the "top" of the stack. The restrictions imposed on stacks allow us to specialize their implementation with arrays or linked lists, in ways that can increase efficiency.
Stacks provide a very efficient storage structure for manipulating data that is accessed according to the LIFO method. Stacks are often used as temporary storage to facilitate the solution of a problem.
Once you get your implementation to work, go back and study the way that the stack class sets and uses top, the index of the top element in the stack. As implemented, top is initialized to zero, and it's maintained as the index of the next place into which the push routine should copy a value. Thus, in push, top is post-incremented, but in pop, top is pre-decremented.
Introduce the following bug into pop: Change it to do post-decrementation on top; make it return listarray[top--] instead of listarray[--top]. Recompile the program and rerun it. In a sentence or two, describe the symptom this bug produces.
_________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________Change pop back. Introduce the following bug, into push: Change it to do pre-incrementation instead of post-incrementation. Recompile and rerun the program. What symptom does this bug produce?
_________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________It turns out that a pre-increment push can be done, but you need a post-decrement pop and you should initialize top to -1. The idea is that instead of top being the index of the next place into which to push, you make it the index of the last place pushed into. Change pop to do post-decrement, and change top so that it's initialized to -1. (Keep push as it is, with pre-increment.)
You should also change the isEmpty. topValue, and isFull member functions to correspond to this new notion of how top works. Test your implementation (and make the program run correctly).
Try using a List to List assignment operator in main. Can you assign a Stack<int> to a Stack<char>? _______
Can you assign a Stack<int, 6> to a Stack<int, 6>_________? Hint - What error message do you get when you cannot do the assignment?
_________________________________________________________________________
Why??? The types are the same - why is there no default assignment allowed???? Try removing the const modifier from the declaration of the stack's size member.
Now can you assign a Stack<int, 6> to a Stack<int, 6>? ___________ When an object contains a const data member, default assignment is not provided since it would change the const. In this case, you can still write an assignment operator - it will have to leave the const members unchanged.
Note - the fact that the compiler allows it does not mean it is a good idea! In all but the simplest classes, default assignment will cause serious problems. In general, if the object contains only primitive data and does not contain pointers, default assignment is OK. Look at the Stack class. Is default assignment OK for this class (with the non-const members), or will it result in corruption of some data? Pick one of the following answers! Consider the fact that the Stack might contain objects that contain pointers. Explain your answer:
___Default assignment is OK regardless of the
objects stored in the stack because...
___Default assignment cannot work properly for this class (regardless of stored object types)
because...
___Default assignment might cause a problem when...
Explain:
In main, can you create a new stack of int's using a default (system supplied) copy constructor for Lists?
_______ Write the statement you used to test this out and tell what error message you obtained (if any).
_________________________________________________________________________
_________________________________________________________________________
Say that we have a stack where the pop routine also prints out the value it pops. What would be printed by the following code fragment?
Stack<int> s; //each pop prints the popped value s.push(1); s.pop(); s.push(2); s.push(3); s.pop(); s.push(4); s.pop(); s.pop();
_____________
_____________
_____________
_____________Stacks are useful when processing a sequence of data when some notion of physical nearness is important. For example, consider the problem of looking at a string of characters to see if they have balanced parentheses. Let's include curly braces and square brackets among our kinds of parentheses, so the strings "()", "((())())", and "([]{})[]" are examples of strings with balanced parentheses. The strings ")(", "(()))", and "([)]" are examples with unbalanced parentheses.
In general, to see if a string has balanced parentheses, we can process it character by character, from left to right, keeping a stack of the parentheses that are currently unmatched. Opening parenthesis are simply stored. Closing parenthesis are matched to the top item on the stack which is then removed and discarded. If some parenthesis is not matched, then the input is not balanced. For example, for the string "([]{})[]", our stack might be as follows (we show the top of the stack on the right):
The main program for this task calls a function isBalanced(s) where s is a string. The function should return true if and only if s has balanced parentheses:
Input Stack Action {({
isBalanced(s):
Let parens be an empty stack of characters.
For each character c of s
If c is a left paren, brace, or bracket, then
Push it onto s
Else if c is a right paren, brace, or bracket, then
If the stack is not empty
Pop the top character from the stack
If that top character doesn't correctly complement c,
Return false
Else
Return false
Else (c isn't a paren, brace, or bracket)
Ignore c.
After the loop: Return true iff no unmatched left items remain on stack.
Complete the implementation of the balanced parenthesis detector. Be sure
to use the complement function that is provided! Test your
implementation, then go on to answer the following questions. In each case, your
answer may not have more than 4 or 5 characters.
a) Give an example of a string of parens that will result in a non-empty stack after the normal termination of the loop (all input characters matched) in the isBalanced function
________________________________
b) Give an example of a string of parens that will cause the loop to terminate early because (in the course of the loop) the stack has no top item to compare
________________________________
c) Give an example of a string of parens that will cause the loop to
terminate early because the top item on the stack does not match the current
input value
________________________________
That's it for this lab. Please hand in printed copies of the two files (don't forget to add your name and date) and this handout. Thank you.