Stacks

CSCI 362: Data Structures

Professor William Killian

#include <stack>
// only access "top"
// no iterators? why

std::stack<int> s;
s.push(4);
s.push(5);
s.top()

5

s.pop();
s.top()

4

Code Tracing Example

#include <string>
#include <stack>

std::string str1, str2;
std::stack<char> s;
str1 = "hello";
for (char c : str1) {
  s.push (c);
}
while (!s.empty()) {
  str2.push_back(s.top());
  s.pop();
}

#include <algorithm>

bool palindrome (std::string const& s) {
    return std::equal (s.begin(), s.end(), s.rbegin(), s.rend());
}

palindrome ("tacocat")

true

Code Tracing Part II

#include <algorithm>
#include <iterator>
#include <string>

bool mystery (std::string s1) {
    std::string s2;
    //1
    std::copy (s1.rbegin(), s1.rend(), std::back_inserter(s2));
    //2
    std::reverse_copy (s1.begin(), s1.end(), std::back_inserter(s2));
    return s1 == s2;
}

Base Conversion

Problem: Given an integer, convert it to hexidecimal. You must output the result as std::string

std::string toHex (int value) {
    std::string result;
    std::stack<char> s;
    // do-while handles input value = 0
    do {
        int rem = value & 15; // int rem = value % 16
        value >>= 4;          // value /= 16
        if (rem > 9) {
            s.push ('a' + (rem - 10));
        } else {
            s.push ('0' + rem);
        }
    } while (value);
    while (!s.empty()) {
        result.push_back (s.top());
        s.pop();
    }
    return result;
}