ADTs continued: Stacks

A new ADT: the Stack.

• A specialized data structure that only allows a user to add, access and remove the last element
  • "Last in, First out"
  • Super-fast (O(1)) for these operations
    • Built directly into the hardware
• Main operations:
  • push(value): add an element to the end of the stack.
  • pop(): remove and return the last element in the stack
  • peek(): return (but do not remove) the last element in the stack

Stacked examples:

• Real life: Rotis, Clothes, Plates in the dining hall, question papers in examination hall, ...
• In Computer Science:
  • Function calls
  • Keeping track of edits to undo or pages visited on a website to go back to.

Stack syntax

#include "stack.h" 
Stack nums;
nums.push(1); 
nums.push(3); 
nums.push(5); 
cout << nums.peek() << endl; // 5 
cout << nums << endl; // {1, 3, 5} 
nums.pop(); // nums = {1, 3} 
s.isEmpty()  O(1)  returns true if stack has no 

Member functions

s.isEmpty()	O(1)	returns true if stack has no elements
s.peek()	O(1)	returns top value without removing it; throws an error if stack is empty
s.pop()	O(1)	removes top value and retuns it; throws an error if stack is empty
s.push(value)	O(1)	places given value on top of stack, increasing its size by one
s.size()	O(1)	returns number of elements in stack.

Stack limitations/patterns

• You cannot access a stack's elements by index!

  Stack<int> s;
  for (int i = 0; i < s.size(); i++) {
    do something with s[i]; //does not compile!
  }
  

  THE ABOVE CODE WILL NOT COMPILE!
• Instead you pull elements out of the stack one at a time.
• common pattern: pop each element until the stack is empty.

  //process (and empty!) an entire stack
  while (!s.isEmpty()) {
    int i = s.pop();
    //do something with i
  }
  

Exercise: Sentence Reversal

• Goal: print the words of a sentence in reverse order
  • Input: "I am xyz". Output: "xyz am I"
  • Input: "Hello". Output: "Hello"
• Assume characters are only letters and spaces
• How could we use a Stack?

Solution 1: use istringstream.

Solution 2: do it by hand

void printSentenceReverse(const string &sentence) {  
    Stack<string> wordStack;  
    for (char c : sentence) {  
        if (c == ' ') {  
            wordStack.push(word);  
            word = ""; // reset  
        } else {  
            word += c;  
        }  
    }  
    if (word != "") {  
        wordStack.push(word);  
    }  
    cout << " New sentence: ";  
    while (!wordStack.isEmpty()) {  
        word = wordStack.pop();  
        cout << word << SPACE;  
    }  
    cout << endl; 
} 

In summary: when to use what?

• 2-D data? Use grids
• 1-Data? Which elements do I need to access?
  • Frequent looping or middle elements? Use Vector
  • Last element? Use Stack

Mapping to C++ STL functions

Member functions (first Stanford function, then STL function, then description): reference http://www.cplusplus.com/reference/stack/stack/:

s.isEmpty()	s.empty()	returns true if stack has no elements
s.peek()	s.top()	returns top value without removing it; throws an error if stack is empty
s.pop()	s.pop()	C++ STL version only removes top value (but does not return it); throws an error if stack is empty
s.push(value)	s.push(value)	places given value on top of stack, increasing its size by one
s.size()	s.size()	returns number of elements in stack.