07.STACKS
SYNTAX
DEFINITIONS
STACK
a list of homogenous elements, wherein the addition & deletion of elements occurs only at one end (top of the stack).
The stack is a last-in-first out concept (LIFO) or first-in-last-out (FILO) data structure
the bottom element of the stack is the earliest/first added one - this is the last one to be deleted
the top element is the last added item
the last added item will be the first one to be deleted
STACK BASIC OPERATIONS
isEmptyStack: Checks whether the stack is empty
isFullStack: Checks whether the stack is full
this can only be done if the implementation is an array list
push: Adds a new element to the top of the stack
top: Returns ore retrieves the information from top of the stack
pop: Removes the top of the stack
STACK IMPLEMENTATION METHODS
Update the ArrayList class to define the three main stack functions: push, top, & pop
Update the LinkedList class to define the three main stack functions: push, top & pop
Define a new class Stack that inherits the class ArrayList
Define a new class Stack that inherits the class LinkedList
STACK PRACTICAL APPLICATION: HANDLING INFIX ARITHMETIC EXPRESSION
STACK PRACTICAL APPLICATION: HANDLING POSTFIX/PREFIX NOTATION IN ARITHMETIC EXPRESSION
postfix expression simplifies the manipulation of arithmetic expression
TRANSFORMING INFIX EXPRESSIONS TO EQUIVALENT POSTFIX EXPRESSION
STACK APPLICATION (POSTFIX)
PROCEDURE
push(6)
push(3)
whenever an operator is encountered, the last two pushed elements (6,3) in this case must be handled using the plus sign
x = top()
x will be 3
pop()
this removes 3 from the stack
y = top()
y will be 6
pop()
this removes 6 from the stack
push(x +y)
the stack will now have 9 which is the sum of 6 and 3
push(2)
m = top()
m will be 2
pop()
this removes 2 from the stack
n = top()
n will be 9
pop()
this removes 9 from the stack
push(m * n)
the stack will now have 18 which is the product of 9 and 2
ALGORITHM
IMPLEMENTATION
UML
VISUALIZATION
SOURCE CODE
HEADER FILE: arrayList.h
/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 111003NOV24
# Filename: arrayList.h
# Dependency: N/A
################################################*/
template <class Type>
class ArrayList
{
protected:
int selfLength, selfMaxSize;
Type* selfList;
public:
ArrayList(int); //constructor
bool isEmpty();
bool isFull();
int listSize();
int maxListSize();
const void print();
bool isItemAtEqual(int, const Type&);
void insertAt(int, const Type&);
void insertEnd(const Type&);
void removeAt(int);
void retrieveAt(int, Type&);
void replaceAt(int, const Type&);
void clearList();
int seqSearch(const Type&);
void insert(const Type&); //without duplication
void remove(const Type&);
ArrayList(const ArrayList<Type>&); //copy constructor
~ArrayList();
const ArrayList<Type>& operator=(const ArrayList<Type>&);
};HEADER FILE: stack.h
#include "arrayList.h"
template<class Type>
class Stack : public ArrayList<Type>
{
public:
Stack(int);
bool isEmpty();
bool isFullStack();
void printStack();
void push(const Type& x);
Type top();
void pop();
};
template<class Type>
Stack<Type>::Stack(int maxSize) : ArrayList<Type>(maxSize){
//we call the constructor of the ArrayList with a parameter maxSize
//the maxSize in ArrayList<Type>(maxSize) will be the maximum number
//hence, there is no statement necessary in this section
}
template<class Type>
bool Stack<Type>::isEmpty(){
return ArrayList<Type>::isEmpty();
}
template<class Type>
bool Stack<Type>::isFullStack(){
return ArrayList<Type>::isFull();
}
template<class Type>
bool Stack<Type>::printStack();{
ArrayList<Type>::print();
}
template<class Type>
void Stack<Type>::push(const Type& x){
ArrayList<Type>::insertEnd(x);
}
template<class Type>
Type Stack<Type>::top(){
int n;
Type x;
n = ArrayList<Type>::listSize();
//the position at n-1 will be stored in x
ArrayList<Type>::retrieveAt(n-1, x);
return x;
}
template<class Type>
void Stack<Type>::pop(){
int n;
n = ArrayList<Type>::listSize();
ArrayList<Type>::removeAt(n - 1);
}#include<iostream>
using namespace std;
#include"Stack.h"
#include<string>
#include<iomanip>
template<class Type>
void postfix(Stack<Type> s)
{
string e;
float num, num1, num2;
cin >> e;
while (e != "=")
{
if (e == "+")
{
num1 = s.top();
s.pop();
num2 = s.top();
s.pop();
s.push(num1 + num2);
}
else if(e == "-")
{
num1 = s.top();
s.pop();
num2 = s.top();
s.pop();
s.push(num2 - num1);
}
else if (e == "*")
{
num1 = s.top();
s.pop();
num2 = s.top();
s.pop();
s.push(num1* num2);
}
else if (e == "/")
{
num1 = s.top();
s.pop();
num2 = s.top();
s.pop();
s.push(num2 / num1);
}
else
{
num = stof(e);
s.push(num);
}
cin >> e;
}
cout << setprecision(2) << fixed << s.top() << endl;
}
int main()
{
/*Stack<int> s(10);
cout<<"Is empty stack? "<<s.isEmptyStack() << endl;
s.push(10); s.push(2); s.push(25);
cout << "Top = "<<s.top() << endl;
s.printStack();
s.pop();
cout << "Top = " << s.top() << endl;
s.printStack();
cout << "Is full stack? " << s.isFullStack() << endl;*/
//code for postfix evaluation
Stack<float> s(10);
postfix(s);
return 0;
}Last updated