A stack is a data structure that has element that we can push and pop ( hence the name stack ) . If we push the numbers 10,20 and 30 onto the stack then conceptually it looks like:
30
20
10
----
When we pop elements out we pop out 30 . We cannot get at the elements below that at the point the 30 is there . The stack is called a List in First Out structure as the element that is pushed last is the element that gets popped out first. We can write our own implementation of the stack using an array as follows:
File: "mystack.h"
#include <iostream>using namespace std ;class mystack { public: int holder[100] ; int noItems = 0 ; int capacity = 100 ; int index = -1 ; bool isFull () { if ( noItems == capacity ) return true ; return false ; } bool isEmpty () { if ( noItems == 0 ) return true ; return false ; } void push( int value ) { if ( isFull() ) throw "Stack Full." ; else { holder[++index] = value ; noItems++ ; } } int pop( ) { int result ; if ( isEmpty() ) throw "Stack Empty." ; else { result = holder[index] ; index-- ; noItems-- ; return result ; } }};
File: "driver.cpp"
#include <iostream>#include "mystack.h"using namespace std ;int main(){ mystack stackLeft ; stackLeft.push( 10 ) ; stackLeft.push( 20 ) ; cout << stackLeft.pop() << endl ; cout << stackLeft.pop() << endl ; cout << stackLeft.pop() << endl ;}
Output:
user@DESKTOP-B634IQO ~/cs297/stacks
$ g++ driver.cpp
user@DESKTOP-B634IQO ~/cs297/stacks
$ ./a.exe
20
10
terminate called after throwing an instance of 'char const*'
Aborted (core dumped)
We wrote out the functions in the header file for the file "mystack.h" . Usually we define the body of the function in the ".cpp" file but we want to keep things as simple as possible. The file "driver.cpp" can simple include the file "mystack.h" .
We push 2 elements and pop them in the opposite order and an exception gets thrown when we try to pop the third element as the stack is empty.
Bracket Validation
We have an expression with two curly brackets.
A string S consisting of N characters is called properly nested if:
S is empty;
S has the form "{U}" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
"{}" is valid
"}{" is invalid
"{{}}" is valid
https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/
File: "bracket1.cpp"
#include <iostream>#include "mystack.h"using namespace std ;bool isExpressionValid ( char expr[] , int size ){ mystack stack1 ; char LEFT_CURLY_BRACKET = '{' ; char RIGHT_CURLY_BRACKET = '}' ; for( int i1=0 ; i1< size ; i1++ ) { if ( expr[i1] == LEFT_CURLY_BRACKET ) { cout << "Pushing on the stack." << endl ; stack1.push( LEFT_CURLY_BRACKET ) ; } else { cout << "Else." << endl ; if ( stack1.isEmpty() ) { cout << "stack is empty." << endl ; return false ; } else { cout << "stack popped." << endl ; stack1.pop() ; } } } //for if ( ! stack1.isEmpty() ) return false ; else return true ;}int main(){ char arr1[] = { '{' , '}' } ; char arr2[] = { '}' , '{' } ; char arr3[] = { '{' , '{', '}' , '}' } ; // cout << isExpressionValid ( arr1, 2 ) << endl ; // cout << isExpressionValid ( arr2, 2 ) << endl ; cout << isExpressionValid ( arr3, 4 ) << endl ;}
Eating Fish problem:
https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/
#include <iostream>#include "mystack.h"using namespace std ;int findAliveFish(int A_arr[], int B_arr[], int length ){ mystack stackLeft ; //0 in B mystack stackRight ; //1 in B int prevFishDirection = -1 ; for( int i1=0 ; i1< length ; i1++ ) { if( prevFishDirection == -1 ) { cout << "Step1" << endl ; prevFishDirection = B_arr[i1] ; if( prevFishDirection == 0 ) stackLeft.push( i1 ) ; else stackRight.push( i1 ) ; } else { if( B_arr[i1] == 1 ) //right { cout << "Step2" << endl ; prevFishDirection =1 ; stackRight.push( i1 ) ; } else //fish going left { //right if ( prevFishDirection == 1 ) { //clash cout << "Step3" << endl ; int prevIndex = stackRight.pop() ; if( A_arr[prevIndex] > A_arr[i1] ) { //left eats the right cout << "left:" << prevIndex << "eats the right:" << i1 << endl ; stackRight.push( prevIndex ) ; } else { //right eats the left cout << "right:" << i1 << "eats the left:"<< prevIndex << endl ; //eat the previous ones ? bool done = true ; int winner = i1 ; while ( done ) { if ( stackRight.isEmpty() ) { cout << "Break loop." << endl ; break ; } cout << "while loop." << endl ; // int indexRight = stackRight.pop() ; cout << "indexRight:"<< indexRight << endl ; if ( A_arr[i1] >
A_arr[indexRight] ) { cout << "left:" << i1 << "eats the right:"<< indexRight << endl ; winner = i1 ; } else { winner = indexRight ; stackRight.push( winner ) ; prevFishDirection = 1 ; cout << "right:" << indexRight << "eats the left:"<< i1 << endl ; break ; } } if ( winner == i1 ) { stackLeft.push( i1 ) ; prevFishDirection = 0 ; } } //if( A_arr[prevIndex] > A_arr[i1] ) } else { cout << "Step6" << endl ; stackLeft.push( i1 ) ; prevFishDirection = 0 ; } } } //if( prevFishDirection == -1 ) } //for return stackLeft.noItems + stackRight.noItems ;}int main(){ int noFish = 5 ; int A_arr[] = { 4 , 3, 2, 1, 5 } ; int B_arr[] = { 0, 1, 0, 0, 0 } ; //int A_arr[] = { 4 , 3, 5, 2, 1 } ; //int B_arr[] = { 1, 1, 0, 0, 0 } ; //int A_arr[] = { 4 , 3, 5, 2, 1 } ; //int B_arr[] = { 1, 0, 1, 0, 1 } ; cout << findAliveFish(A_arr, B_arr, noFish ) << endl ; //cout << stackLeft.pop() << endl ;}
Ex1:
Rewrite the bracket example but the expression can have 3 characters instead namely the curly bracket, the round bracket and the square bracket. Example expressions are:
"{[" Invalid
"{ [ ( } ] } " Valid
" { ] [ }" Invalid
#include <iostream>#include "mystack.h"using namespace std ;bool isExpressionValid ( char expr[] , int size ){ mystack stack1 ; const char LEFT_CURLY_BRACKET = '{' ; const char RIGHT_CURLY_BRACKET = '}' ; const char LEFT_ROUND_BRACKET = '(' ; const char RIGHT_ROUND_BRACKET = ')' ; const char LEFT_SQUARE_BRACKET = '[' ; const char RIGHT_SQUARE_BRACKET = ']' ; char ch ; //TO DO if ( ! stack1.isEmpty() ) return false ; else return true ;}int main(){ char arr1[] = { '{' , '}' } ; char arr2[] = { '}' , '{' } ; char arr3[] = { '{' , '[', '(' , ')' , ']' , '}' } ; cout << isExpressionValid ( arr1, 2 ) << endl ; cout << isExpressionValid ( arr2, 2 ) << endl ; cout << isExpressionValid ( arr3, 6 ) << endl ;}
Ex2:
A stack needs to be implemented that in addition to having the stack functionally can provide the minimum element at any time of the elements in the stack without traversing the stack. The scheme that will be used is to use 2 stacks. We call them "mainStack" and "auxStack" . Say we push the elements 10,6,12 and 13 onto the stack. Initially both are empty . When we push 10 we push it on both the stacks.
mainStack: 10
auxStack: 10
We are going to use the "mainStack" in a normal way and the "auxStack" to help with the minimum value. Now we are going to push 6. We push it on the "mainStack" . Now we look at the top element of the "auxStack" and compare it to 6. Whichever is smaller ; we push that value to the "auxStack" .
maxStack: 10 6
auxStack: 10 6
Similarly we push 12 and 13 and the stacks look like:
maxStack: 10 6 12 13
auxStack: 10 6 6 6
The elements in the "auxStack" represent the min values of the stack at that particular position. What that means is from positions 2 to 4 the min value is 6 . However for position 1 to 1 we have the min value 10 . When we do the pop operation we remove the top values from both the stacks.
#include <iostream>#include "mystack.h"using namespace std ;class MinStack { public: mystack mainStack ; mystack auxStack ; void push ( int value ) { } int pop() { } int getMin() { if ( auxStack.isEmpty() ) throw "Stack is empty." ; return ( auxStack.peek() ) ; } void print() { mainStack.print() ; auxStack.print() ; }} ;int main(){ MinStack stack1 ; stack1.push( 10 ) ; stack1.print() ; cout << "Min:" << stack1.getMin() << endl ; stack1.push( 6 ) ; stack1.push( 12 ) ; stack1.push( 13 ) ; cout << "Min:" << stack1.getMin() << endl ; stack1.pop() ; stack1.pop() ; stack1.pop() ; cout << stack1.getMin() << endl ;}
Ex 3:
Change the "mystack.h" to use dynamic memory. If the stack is full then allocate more memory ( 2 times the original capacity ) , copy the old elements into the new memory, delete the old memory. Add template functionality to your class.
Ex 4:
Use the stack class from STL .