Welcome Back!

Learning Objectives
By the end of this class, you should know...
  • The difference between  the stack and queue ADTs
  • Applications of stacks
  • The most important stack operations
  • How to implement a stack data structure
  • If time: recursion


Announcements

  • Project Report 1 due next class
  • Quiz 2 after the break
  • Lab 3 due Monday
  • Please see me at break if you did not get on a project team
  • Please see me at break if you did not get a partner for Lab 3 (required!)



Review Activity

  • True or False, the Queue is organized according to the principles of LIFO?
  • Write the insertIterator function for the double linked list from Lab 2


Stacks

  • Last class we talked briefly about Stacks.
  • We learned that Stacks are organized by the principle of Last In, First Out or LIFO, just like a stack of dishes.
  • The last dish placed on the stack of dishes is the first one to be removed.

A Stack

Stack of Dishes 2

Like this stack of dishes, Stacks are organized according to the principle of LIFO: last in, first out. Image Source


  • Therefore, many of the Stack operations are concentrated at the very front of the stack.
  • What does this mean for our Stack implementation?


Stack Applications
  • Function call stacks (we will discuss more when we get to recursion).
  • Undo sequence of a text editor.
  • Page visited history in a web browser.
  • Matching tags in HTML and XML
  • Can you think of any others?


Stack Operations
  • Two important Stack operations are known as Push and Pop.
  • Pushing an item onto the Stack means inserting a new item at the top of the Stack.
  • Popping an item off the Stack means removing the item at the top of the Stack.


Two important Stack operations: Push and Pop. Image Source.

  • Note that unlike the Queue, the Stack only allows access to its top item.


Stack vs Queue

Queue:

Stack:



Writing Our Own Stack Class

  • Copy and paste the following header file into a new file called Stack.h.
  • What looks different from the Queue?
#ifndef Stack_H_
#define Stack_H_

#include <iostream>
#include <cstddef>
#include <assert.h>

using namespace std;

template <class stackdata>
class Stack
{
    public:
        /**constructors and destructors*/

        Stack();

        //initializes an empty stack
        //postcondition: an empty stack

        Stack(const Stack &S);
        //initializes this stack to have same elements as S
        //postcondition: a copy of stack


        ~Stack();
        //frees memory allocated to the stack
        //postcondition: memory for stack has been freed

        /**manipulation procedures*/

        void pop();
        //removes an element from the top of the stack
        //precondition: size != 0
        //postcondition: an element has been removed from the top of the stack

        void push(stackdata data);
        //adds an element to the top of the stack
        //postcondition: an element added to the top of the stack

        /**accessors*/


       bool operator==(const Stack &S);
       //returns whether this stack is equal to another stack S

       stackdata peek() const;
       //returns the element at the top of the stack
       //precondition: size != 0

       int getSize() const;
       //returns the size of the stack

       bool isEmpty() const;
       //returns whether the stack is empty


       /**additional operations*/

       void displayStack(ostream& out) const;
       //prints the elements in the stack each element separate by a blank space to stdout

    private:
       struct Node {
           stackdata data;
           Node* next;

           Node(stackdata ndata) {
                data = ndata;
                next = NULL;
          }
       };

       Node* top;
       int size;

};



Activity 5.1 Writing Your Stack Functions

  • Next write your stack functions
  • You should write these functions in a file named Stack.cpp
  • Test your functions inside of main in a file named StackTest.cpp
  • You will submit your code as part of Lab 3
  • Note that push should be written like insertStart and pop should be written like removeStart from the List class (Lab 1).



Upcoming Assignments:

  • Lab 3 Due Monday
  • Project Report 1: Due Monday
~Have a Great Weekend!~