Stacks, Push, and Pop

Dr. Lawlor, CS 202, CS, UAF

A "stack" is a weirdly limited data structure.  You "push" items onto the stack, examine the "top" of the stack (the last-pushed item), and "pop" items off the stack in reverse order of pushing--the stack is "last in, first out" (LIFO) data structure:
#include <stack>

int foo(void) {
std::stack<std::string> s;
cout<<"Top of stack: "<<<<"\n";
cout<<"New top of stack: "<<<<"\n";
return 0;

(Try this in NetRun now!)

The 'pop' removes ted, since he was the last one added.

Stacks are useful in a surprising variety of places.  For example, you can evaluate expressions in "reverse polish notation" (HP calculator style) using a stack:
#include <stack>

int foo(void) {
std::stack<float> op; // saved operands
std::string next;
while (std::cin>>next) {
if (isdigit(
{ // it's a number--push it
} else
{ // it's probably an operation--execute it
float; op.pop(); // pop our inputs
float; op.pop();
float result=0.0;
switch ( {
case '+': result=left+right; break;
case '-': result=left-right; break;
case '*': result=left*right; break;
case '/': result=left/right; break;
case '^': result=pow(left,right); break;
default: std::cout<<"Error: unknown "<<next<<"\n";
std::cout<<" "<<left<<next<<right<<" = "<<result<<"\n";
std::cout<<"Final top of stack: "<<<<"\n";
return 0;

(Try this in NetRun now!)

Here's the more sophisticated version of the above that we developed in class.  It includes trancendentals, in either "r" for Radian mode or "d" for degree mode.

#include <stack>

int foo(void) {
std::stack<float> op;
std::string s;
float angle_scale=1.0; // <- radian mode
while (cin>>s) {
if (isdigit( op.push(atof(s.c_str()));
else { // operation
unsigned int needed_ops=2;
if (s=="pi" || s=="r" || s=="d") needed_ops=0;
if (s=="sin" || s=="cos") needed_ops=1;
if (op.size()<needed_ops) {cout<<"Stack underflow error: this calculator uses 'RPN' (HP-style) notation, like '2 3 +', not '2 + 3'!\n"; return 0;}
float right=0.0;
if (needed_ops>0) {; op.pop();}
float left=0.0;
if (needed_ops>1) {; op.pop();}
switch ( {
case '+': op.push(left+right); break;
case '-': op.push(left-right); break;
case '*': op.push(left*right); break;
case '/': op.push(left/right); break;
case '%': op.push(fmod(left,right)); break;
case '^': op.push(pow(left,right)); break;
case 'r': angle_scale=1.0; /* radian mode*/ break;
case 'd': angle_scale=M_PI/180.0; /* degree mode*/ break;
case 's': if (s=="sin") { op.push(sin(angle_scale*right)); break;}
case 'c': if (s=="cos") { op.push(cos(angle_scale*right)); break;}
case 'p': if (s=="pi") { op.push(M_PI); break;}
default: cout<<"ERROR! "<<s<<" unrecognized\n";
while (!op.empty()) {
cout<<"Top of stack: "<<<<"\n"; op.pop();
return 0;

(Try this in NetRun now!)

Stacks are also used in assembly language to implement function calls: information about the current function (say, local variables) lives on the top of the stack, and you push when calling a new function, and pop when returning from the function.  This, in turn, is useful in writing emulators!