MTH 4300: Algorithms, Computers, and Programming II

Stacks

The main element of stack is its node. The node has two components: content and pointer aNext that contains an address of another node. We will use the terminology old nodes for the nodes that are added before. The youngest node is the one that is added the last. We will only keep track of the youngest node. The youngest node contains the address of the second youngest, and the second youngest node contains the address of the third youngest. The oldest node contains the nullpointer.

The procedure of adding a new node to the stack is called push. The youngest node is also called top of the stack. As mentioned earlier, it is sufficient to only keep track of the pointer to this top node. We will call this pointer aTop. Removing the top node is easy. We first save the address from aTop->aNext as this will be the new top (or youngest) node of the stack. Then we delete the top node, and update the pointer aTop to contain the address of the new youngest node.

The implementation of the stack of doubles is given below. The implementation also contains the function copyStack that creates a brand new stack with the same contents as the old one.

#include<iostream>
class SN{// Stack Node
public:
 double content;
 SN* aNext;
};
SN* push(SN* oldTop, double x){
 SN* nTop;
 nTop=new SN;
 nTop->content=x;
 nTop->aNext=oldTop;
 return nTop;
}
SN* pop(SN* oldTop){
 if(oldTop==nullptr){ return nullptr; }
 SN* nextNode;
 nextNode=oldTop->aNext;
 delete oldTop;
 return nextNode;
}
double readTop(SN* aTop){
 if(aTop==nullptr){ return 0.0; }
 return aTop->content;
}
int isEmpty(SN* aTop){
 if(aTop==nullptr){ return 1; }
 return 0;
}
void deleteStack(SN* aTop){
 while(aTop!=nullptr){
    aTop=pop(aTop);
 }
}
SN* copyStack(SN* aTop){
 if(aTop==nullptr){return nullptr;}
 SN* nTop=new SN;
 nTop->content=aTop->content;
 nTop->aNext=copyStack(aTop->aNext);
 return nTop;
}
void printStack(SN* aTop){
  if(aTop!=nullptr){
    printStack(aTop->aNext);
    std::cout << aTop->content<<" ";
  }
}
int main(){
  SN* aTop=nullptr;
  aTop=push(aTop,25);
  aTop=push(aTop,21);
  aTop=push(aTop,33);
  std::cout << "Created stack 1\n";
  SN* aTop2=copyStack(aTop);
  std::cout << "Created stack 2\n";
  aTop=pop(aTop);
  aTop=push(aTop,35);
  aTop=push(aTop,27);
  aTop2=push(aTop2,77);
  aTop2=push(aTop2,372);
  printStack(aTop);std::cout << "\n\n\n";
  printStack(aTop2);std::cout << "\n\n\n";
  return 0;
}