DATA STRUCTURE WITH C++ PROGRAMMING USING STACK
PREREQUISITES TO IMPLEMENTING STACK IN C++
We will need to understand how to use some of the constructs in C++ that makes up the implementation of stack in C++ against. And this concepts will also help you in developing other codes and to debug or understand the C++ codes in a company's code bank or to interpret a boiler plate code (a ready made code).
Some of these constructs or concepts are:
1. sizeof()
2. Function
3. Pointer
4. Function Pointer
5. Arrow operator
6. malloc()
7. typedef
8. struct
PHASE 1: sizeof()
It is used to determine the size of variables used in a program, it can determine the size of primitive (or predefined) datatype too and for any user-defined datatypes. It is an inbuilt keyword and a compile-time operator.
syntax-1 using variable
sizeof(variableName);
syntax-2 using primitive datatype
sizeof(datatype);
//code implementation
#include<iostream>
using namespace std;
int main(){
//declare variable
int age;
//display the variable size
cout<<"The size of the variable age is:: "<<sizeof(age);
//display the size of a datatype directly
//you can change the datatype to other ones you know to get their size
cout<<"\n\nThe size of the datatype bool is:: "<<sizeof(bool);
return 0;
}
PHASE 2: Function
functions are used to make coding easy, it helps you to split your code into different modules. You define the code once and can use it many times. Before a function can run, it must first be created outside the predefined function main(), then called within the main().
C++ has at least one function which is main(), main() is the predefined function of C++ but as a programmer, you can also create your own functions to perform certain tasks (this is called user-defined function)
syntax-1 creating a function without parameters
datatype functionName(){
//statements to be executed
}
syntax to call a function
//write the function name followed by two parentheses "( )" and a semicolon ";"
functionName();
//code implementation
#include<iostream>
using namespace std;
//create a function
void displaymsg(){
cout<<"function is interesting to implement"<<endl;
}
int main(){
//call the function
displaymsg();
displaymsg();
return 0;
}
syntax-2 creating a function with parameters
//Here you can pass data known as parameters into a function
datatype functionName(parameter1, parameter2,...,parameterN){
//statements to be executed
}
syntax to call a function
Here you can pass data known as arguments into a function when it is called. The number of parameters in the created function must match the one in the caller function
functionName(parameter1, parameter2,...,parameterN);
//code implementation
#include<iostream>
using namespace std;
//create a function
void school(string sname){
cout<<"Some universities in Nigeria:: "<<sname<<endl;
}
int main(){
//call the function
school("Caleb University");
school("Covenant University");
return 0;
}
PHASE 3: Pointer
It holds the memory address of a particular variable. Pointer stores address rather than the value itself. Pointers are symbolic representations of addresses. Iterating over elements in array or other data structures is one of the main use of pointers. We need pointer to track the memory address of the stack as either empty, full, element added or deleted.
syntax
datatype *variableName
//aliter
datatype* variableName
//example
string *sname;
PHASE 4: function pointer
we use a pointer to point to a functionName and call it using that pointer
syntax creating a function pointer with parameters
datatype functionName(datatype *variableName){
//statements to be executed
}
//sample code snippet
void createEmptyStack(stk *st){
st->top = -1;
}
st->top = -1
Pronounced as: st arrow top equals to -1
Meaning: Assign the address of Variable top to variable st then assign empty container (-1) to variable st
Also, Before pushing elements to the Stack, the stack is empty
After pushing element(s) into the stack, the stack will no longer be empty
analysis: A pointer (top) is set to keep track of the topmost item in the stack. The stack is initialized to -1, then a check is performed to determine if the stack is empty by comparing top to -1. As elements are added to the stack, the top position is updated, also when elements are deleted, the topmost element is removed and the top position is updated again.
PHASE 5: Arrow operator
Arrow operator "->" or class member access
It is used to access the public members of a class, structure with the help of a pointer variable. In other to bind a function pointer variable to another variable we use the arrow operator (it is made up of minus and greater operator)
//example1
st -> top = -1; //create an empty stack before adding items to the stack
with the help of arrow operator, variable stk is pointing to variable top in the memory address of the stack.
//example2
st->top == maxSize - 1
Analysis: A pointer (top) is set to keep the track of hte topmost item in the stack. The stack is initialized to -1, then a check is done if the stack is full by comparing top to maxSize -1 (the maximum size that the stack can store).
PHASE 6: malloc()
Malloc is stands for Memory Allocation. It is included in the <cstdlib> header in C++ library. It is used to allocate uninitialized memory block of specified size to a poiner or variable.
syntax
malloc(memSize, allocSize);
//code implementation
#include<iostream>
using namespace std;
int main(){
//allocate memory of int size to int pointer
int *age = (int*)malloc(sizeof(int));
//assign the value 27 to allocated memory
*age = 27;
cout<<*age;
return 0;
}
PHASE 7: typedef
typedef is a C++ keyword used to assign alternative names to the existing datatypes (predefined or user-defined)
syntax
typedef <currentName> <newName>
//code implementation
#include<vector>
using namespace std;
int main(){
//assign alternative names using typedef
typedef vector<float> vecValue;
//v1, v2 are vector of user-defined datatype vecValue
vecValue v1, v2; //multiple declaration
//add elements to v1
v1.push_back(3.80);
v1.push_back(4.99);
//add elements to v1
v2.push_back(1.75);
v2.push_back(2.99);
//print v1 element
cout<<"vector V1 elements are:: ";
for(auto xcount : v1){
cout<<xcount<<" ";
}
//print v2 element
cout<<"\n\nvector V2 elements are:: ";
for(auto xcount : v2){
cout<<xcount<<" ";
}
return 0;
}
PHASE 8: struct
struct means Structure, it is used to group several related variables (called members) into one place. Unlike array, a strcuture can contain many different data types (int, string, float, double, bool). We use the dot operator to bind struct name to struct members i.e. to access memebrs of structure.
syntax 1: declare structure and create single structure variable
struct{ //strucutre declaration
//structure member(s)
} structVariableName; //structure variable
//code implementation
#include<iostream>
using namespace std;
int main(){
//declare and create structure variable sinfo
struct{
//structure members
string stdname;
int stdage;
} sinfo;
//assign values to the members
sinfo.stdname = "dmactutor";
sinfo.stdage = 21;
//print memebers
cout<<"The student name is "<<sinfo.stdname <<" "<<"with age "<<sinfo.stdage;
return 0;
}
syntax 2: declare structure and create multiple structure variables (separated with comma)
struct{ //strucutre declaration
//structure member(s)
} structVariableName1, structVariableName2,...,structVariableNameN ; //structure variables
STACK IMPLEMENTATION
Stack is a data structure that stores data elements using Last-In-First-Out (LIFO) principle or order.
fig1: Stack diagram: Application of stack on web browser
Each time you visit a new webpage on the browser, it is added on top of the stack.
Stack is also implemented in expression evaluation and checking parentheses for compiler [e.g. (a+b)*(c-d)], palindrome (reversing characters e.g dad, pap, madam), syntax parsing.
Operations on stack
push, pop, isempty, isfull, peek
METHOD 1 - Using non-interactive approach to handle stack implementation
Top Down Analysis
Outside the main() function
step 1: Create a structure (struct) to declare and create variables top and items[MAX] (to be added to the stack)
step 2: create a new variable st through struct user-defined dataype mystack using typedef statement (to assign alternative name to the existing datatype "mystack")
step 3: declare a function pointer to create an empty stack container (*xs is the pointer variable to the top element, then initialize pointer variable as -1, which means empty recall index 0, 1, 2,....). " xs->top = -1;" Assign the address of top to xs and intialize it to -1
step 4: declare a function pointer to check if the stack container is full, compare the pointer variable to the maximum capacity the stack can hold i.e. 10 items for now "if (xs->top == MAX - 1)", if full, it returns 1 else it returns 0 (which means more elements can still be added)
step 5: declare a function pointer to check if the stack container is empty.
step 6: declare a function pointer to add elements into the stack
step 7: declare a function pointer to remove elements from the stack
step 8: declare a function pointer to print all the elements stored in the stack container
Within the main() function where program execution takes place
step 9: declare and allocate memory to the pointer variable *xs with malloc() statement
step 10: call function createEmptyStack(xs); and pass one argument, the pointer variable xs
step 11: call function push(xs, 16), and pass two arguments, the pointer variable xs and value to be stored in the stack
step 12: call function printStack(xs); and pass one argument, the pointer variable xs
step 13: call function pop(xs), and pass one argument, the pointer variable xs
step 14: call function printStack(xs); and pass one argument, the pointer variable xs
NB: if you notice, we did not call function isfull(), it is because the function is only meant to return value 1 or 0
//code implementation
// Stack implementation in C++
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MAX 10
int size = 0;
// Create structure mystack with two members
struct mystack {
int items[MAX];
int top;
};
typedef struct mystack st;
//create method createEmptyStack, to make an empty stack container
void createEmptyStack(st *xs) {
xs->top = -1;
}
// create method isfull, Check if the stack is full
int isfull(st *xs) {
if (xs->top == MAX - 1)
return 1;
else
return 0;
}
// create method isempty, Check if the stack is empty
//xs holds the address of Variable top and compare if the stack is empty
int isempty(st *xs) {
if (xs->top == -1)
return 1;
else
return 0;
}
// create method push, Add elements into stack
void push(st *xs, int newitem) {
if (isfull(xs)) {
cout << "STACK FULL";
} else {
xs->top++;
xs->items[xs->top] = newitem;
}
size++;
}
// create method pop, Remove element from stack
void pop(st *xs) {
if (isempty(xs)) {
cout << "\n STACK EMPTY \n";
} else {
cout << "Item popped= " << xs->items[xs->top];
xs->top--;
}
size--;
cout << endl;
}
// create method printStcak, Print elements of stack
void printStack(st *xs) {
printf("Stack Elements: ");
for (int i = 0; i < size; i++) {
cout << xs->items[i] << " ";
}
cout << endl;
}
// Execution starts here
int main() {
int ch;
st *xs = (st *)malloc(sizeof(st));
//call each method and pass (data) arguments into them based on the number of parameters
//call createEmptyStack()
createEmptyStack(xs);
//call push()
push(xs, 16);
push(xs, 32);
push(xs, 90);
push(xs, 45);
//call printStack()
printStack(xs);
//call pop()
pop(xs);
cout << "\nAfter popping out\n";
// call printStack()
printStack(xs);
}
CODE OUTPUT
For the code above: reference from https://www.programiz.com/dsa/stack
METHOD 2 - Using interactive approach to handle stack implementation
Constructs you need to know
Array
Selection statement (if...else, swtich case)
Loop statement (do...while)
To implement the code, the user can interact with the program to add integer element(s) of his choice,
check if stack is underflow (trying to delete element from an empty stack)
add element to the stack
delete element from the stack containing elements
display the element in a stack
NB: Let's enter the same values that we have in the METHOD-1 approach
Top Down Analysis
declare array size of 10 for the stack (we can increase the size if we want)
//CODE IMPLEMENTATION
#include <iostream>
using namespace std;
int stack[10], n=10, top=-1, uservalue;
//create function push()
void push(int val){
if(top>=n-1)
cout<<"Stack overflow"<<endl;
else{
top++;
stack[top] = val; //store the content of variable top inside the stack container
}
}
//create function pop()
void pop(){
if(top<=-1)
cout<<"Stack underflow"<<endl;
else{
cout<<"Popped element " <<stack[top] <<endl;
top--;
}
}
void display(){
if(top>=0){
cout<<"Stack elements"<<endl;
//traverse the elements in the stack using for loop
for(int xcount=top; xcount>=0; xcount--)
cout<<stack[xcount]<<" "<<endl;
} else
cout<<"Stack is empty";
}
int main() {
int choice;
//display menu option
cout<<"\t_________\n\n";
cout<<"\tWeclcome to the STACK PAGE\n\n"<<endl;
cout<<"\t_________ MENU __________\n\n";
cout<<"\t | --Press 1 to PUSH / ADD / INSERT ELEMENT-- | "<<endl;
cout<<"\t | --Press 2 to POP / REMNOVE / DELETE ELEMENT-- | "<<endl;
cout<<"\t | --Press 3 for DISPLAY STACK ELEMENT(S) -- | "<<endl;
cout<<"\t | --Press 4 to EXIT APPLICATION-- | "<<endl;
//display user action
do{
cout<<"\n\t --Enter your choice-- | ";
//accept input
cin>>choice;
//menu to select
switch(choice){
case 1:
cout<<"Enter element to be pushed"<<endl;
cin>>uservalue;
//call method push and pass argument uservalue
push(uservalue);
break;
case 2:
pop(); //delete top element in the stack
break;
case 3:
display();
break;
case 4:
cout<<"\t --Thank You-- "<<endl;
cout<<"--EXIT--";
exit(0); //pass the integer value 0 into the exit() function, to indicate success
break;
default:
system("cls"); //to clear the screen
cout<<"\t --Please check the selected option \n Try again-- "<<endl;
main(); //take control to the main body
}
} while(choice != 4);
return 0;
}
CODE OUTPUT
Comments
Post a Comment