CSCE 2014 - Laboratory Assignment 7

    The purpose of this lab is to introduce students to the stack abstract data type, and to see how stacks can be implemented using linked list techniques. We will also create a simple program to test the stack interface (ie. the public methods).

  1. Introduction to Stacks
  2. The stack abstract data type is used to store and access data in a LIFO (last in first out) manner. For example if we store 3 values A, B, and C in a stack. Then when we retrieve the data, we will get C, B, and A. The 'C' was the last value stored, so it will be the first value retrieved.

    Stacks have found a number of uses in computer systems. Perhaps the most important use of stacks is in operating systems, where they are used to coordinate execution of instructions after servicing interrupts. Stacks are also used to implement recursion when a program is running.

    Five basic operations can be performed on a stack:
    Pop: To retrieve and remove the top most item from the stack
    Push: To push an item on to the top of the stack
    Top: To retrieve the top most item on the stack
    IsEmpty: Check whether the stack is empty
    IsFull: Check whether the stack is full

  3. The Stack Class
  4. Consider the C++ class declaration below for a Stack class. Notice that we have declared a SNode class with two public data fields. This is a somewhat lazy way to implement the SNode class, but we are only intending to use this class within the Stack class, so "real" users will not be using SNodes.

    //-----------------------------------------------------------
    //  Purpose:    Header file for the Stack class.
    //  Author:     John Gauch
    //-----------------------------------------------------------
    #include < iostream >
    using namespace std;
    
    // Stack data node definition
    class SNode
    {
       public:
       int Number;
       SNode *Next;
    };
    
    class Stack
    {
       public:
          // constructor functions
          Stack();
          ~Stack();
    
          // general stack operations
          void Push(int Number);
          void Pop(int &Number);
          void Top(int &Number);
          bool IsFull();
          bool IsEmpty();
          void Print();
    
       private:
          SNode *Head;
          int Length;
    };
    

  5. Stack Implementation
  6. Consider the partial implementation of the Stack class below. Notice that we have left several functions empty on purpose. We will fill these in later on.

    //-----------------------------------------------------------
    //  Purpose:    Implementation of Stack class.
    //  Author:     John Gauch
    //-----------------------------------------------------------
    #include "stack.h"
    
    //-----------------------------------------------------------
    // Constructor function.
    //-----------------------------------------------------------
    Stack::Stack()
    {
       Head = NULL;
       Length = 0;
    }
    
    //-----------------------------------------------------------
    // Destructor function.
    //-----------------------------------------------------------
    Stack::~Stack()
    {
    }
    
    //-----------------------------------------------------------
    // This checks to see if stack is full.
    //-----------------------------------------------------------
    bool Stack::IsFull()
    {
       return (false);
    }
    
    //-----------------------------------------------------------
    // This checks to see if stack is empty.
    //-----------------------------------------------------------
    bool Stack::IsEmpty()
    {
       return (Length == 0);
    }
    
    //-----------------------------------------------------------
    // This routine pushes data into the stack.
    //-----------------------------------------------------------
    void Stack::Push(int Number)
    {
       // Check for full stack
       if (IsFull())
          return;
    
       // Allocate space for data
       SNode *Temp = new SNode;
       if (Temp == NULL)
          return;
    
       // Insert data at head of list
       Temp->Number = Number;
       Temp->Next = Head;
       Head = Temp;
       Length++;
    }
    
    //-----------------------------------------------------------
    // This routine pops data from the stack.
    //-----------------------------------------------------------
    void Stack::Pop(int &Number)
    {
       // Check for empty stack
       if (IsEmpty())
          return;
    
       // Extract information from node
       Number = Head->Number;
    
       // Pop item from linked list
       SNode *Temp = Head;
       Head = Head->Next;
       delete Temp;
       Length--;
    }
    
    //-----------------------------------------------------------
    // This routine returns the data from the front of the stack.
    //-----------------------------------------------------------
    void Stack::Top(int &Number)
    {
       // ADD HERE
    }
    
    //-----------------------------------------------------------
    // This routine prints all records in the stack.
    //-----------------------------------------------------------
    void Stack::Print()
    {
       // ADD HERE
    }
    
    //-----------------------------------------------------------
    // Main program.
    //-----------------------------------------------------------
    int main()
    {
       // ADD HERE
    }
    

  7. Testing the Stack Class
  8. Copy and paste the class declaration into a file called "stack.h" in your NetBeans project. Then copy and paste the class implementation into a file called "stack.cpp". When you compile and run this code, it should do nothing.

    Now extend the main function, to create a Stack object called "stack" and then call the Push and Pop methods to store and retrieve the numbers 3 1 4 1 5 9. To see what happens, print each value as it is pushed on the stack and when it is popped off the stack.

    Cut and paste your new main function below:

    Cut and paste your program output below:

  9. Implementing Top and Print
  10. You will notice that the Top and Print methods are not implemented for the stack class. As noted above, the Top method is supposed to return the value of the top element on the stack, but it is NOT supposed to remove this value. Use this information to implement Top and extend your main function to call top at different times in your Push, Pop sequence.

    Cut and paste your Top method below:

    Now you can implement the Print method. To do this you must "walk the linked list" to access each of the integer values. By this time, this process should look pretty familiar. When you have finished implementing Print, call this function several times between your Push and Pop calls to get a quick view of the stack as your program is running.

    Cut and paste your Print method below:

    Cut and paste your main function below:

    Finally, cut and paste your program output below:

  11. Submit Work
  12. This lab assignment will be submitted electronically to the TAs once you fill in the fields below and click on the "submit" button. You do NOT need to print a copy of this document to hand in.

    Your full name:
    Your uaid number: