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;
	s.push("phil"); 
	s.push("ted");
	cout<<"Top of stack: "<<s.top()<<"\n";
	s.pop();
	cout<<"New top of stack: "<<s.top()<<"\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(next.at(0))) 
		{ // it's a number--push it
			op.push(atof(next.c_str()));
		} else 
		{ // it's probably an operation--execute it
			float right=op.top(); op.pop(); // pop our inputs
			float left=op.top(); op.pop();
			float result=0.0;
			switch (next.at(0)) {
				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";
			op.push(result);
		}
	}
	std::cout<<"Final top of stack: "<<op.top()<<"\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(s.at(0))) 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) {right=op.top(); op.pop();}
			float left=0.0;
			if (needed_ops>1) {left=op.top(); op.pop();}
			switch (s.at(0)) {
			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: "<<op.top()<<"\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!