ADTs: Stacks and Queues Part 2: Using Lists

**WingedPanther** · 01-02-2009 09:34 AM

In the last tutorial, we saw that arrays could get a bit tricky to use, especially with queues. If you ran the resulting program, you also saw that the output was 'a'-'j' instead of 'a'-'t' as you would expect. This was because arrays don't grow dynamically in C++. To overcome these limitations, we will now change the implementation of Stack and Queue to use linked lists instead of arrays to store the data. Again, I will use strings for the data, but it can be easily converted to use templates.

To read the descriptions of the Stack and Queue Abstract Data Types, go here.

To test the new implementations, I've modified the teststack.cpp program... by changing the includes. Nothing else has changed! This is the key idea of an ADT: the implementation should not affect your ability to use it! This comes from the principle in all programming of Loose Coupling (my wife thinks this sounds scandalous). What this means is that, for all classes (and programs in general), you should define interfaces that allow classes/functions/modules to pass the necessary information. The details of the functioning should be hidden from the calling class/function/module so that optimizations in one area do not break functioning in another.

teststack2.cpp

Code:

#include <string>
#include <iostream>
#include "stack2.h"
#include "queue2.h"
using std::cout;
using std::string;

int main()
{
  Stack mystack;
  Queue myqueue;
  string temp;

  //initial state verified
  cout<<"initial size of stack: "<<mystack.size()<<"\n";
  cout<<"initial size of queue: "<<myqueue.size()<<"\n";
  int i;

  //populate the stack with 'a' – 't'... maybe
  try
  {
    for(i=0;i<20;i++)
    {
      temp = 'a'+i;
      mystack.push(temp);
    }
  }
  catch(OverFlow)
  {
    cout<<"stack overflow at i = "<<i<<"\n";
  }
  cout<<"size of stack after for loop: "<<mystack.size()<<"\n";

  //clear the stack, printing the results and force underflow
  try
  {
    for(;i>=0;i--)
      cout<<mystack.pop()<<"\n";
  }
  catch(UnderFlow)
  {
    cout<<"stack underflow at i = "<<i<<"\n";
  }
  cout<<"size of stack after for loop: "<<mystack.size()<<"\n";
  
  //populate the queue with 'a' – 't'... maybe
  try
  {
    for(i=0;i<20;i++)
    {
      temp = 'a'+i;
      myqueue.push(temp);
    }
  }
  catch(OverFlow)
  {
    cout<<"queue overflow at i = "<<i<<"\n";
  }
  cout<<"size of queue after for loop: "<<myqueue.size()<<"\n";

  //clear the queue, printing the results and force underflow
  try
  {
    for(;i>=0;i--)
      cout<<myqueue.pop()<<"\n";
  }
  catch(UnderFlow)
  {
    cout<<"queue underflow at i = "<<i<<"\n";
  }
  cout<<"size of queue after for loop: "<<myqueue.size()<<"\n";
  
  //put remaining stack methods through their paces
  mystack.push("string");
  cout<<"stack contains "<<mystack.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<mystack.top()<<"\"\n";
  cout<<"the stack is ";
  if (!mystack.empty()) 
    cout<<"not ";
  cout<<"empty\n";
  cout<<"stack contains "<<mystack.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<mystack.pop()<<"\"\n";
  cout<<"stack contains "<<mystack.size()<<" element(s)\n";
  cout<<"the stack is ";
  if (!mystack.empty()) 
    cout<<"not ";
  cout<<"empty\n";

  //put remaining queue methods through their paces
  myqueue.push("string");
  cout<<"stack contains "<<myqueue.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<myqueue.front()<<"\"\n";
  cout<<"the stack is ";
  if (!myqueue.empty()) 
    cout<<"not ";
  cout<<"empty\n";
  cout<<"stack contains "<<myqueue.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<myqueue.pop()<<"\"\n";
  cout<<"stack contains "<<myqueue.size()<<" element(s)\n";
  cout<<"the stack is ";
  if (!myqueue.empty())
    cout<<"not ";
  cout<<"empty\n";
}

As you will see, the new implementations of Queue and Stack will be radically different, but the code doesn't need to change at all.

As before, we have two exceptions that are defined in the exact same exceptions.h file.

exceptions.h:

Code:

#ifndef EXCEPTIONS_H
#define EXCEPTIONS_H
class OverFlow
{
};

class UnderFlow
{
};
#endif

Before, we used arrays to store the data. Now we're going to use a linked list (see my tutorial here). The model for the Stack is below:

Code:

          +-----+      +-----+      +-----+      +-----+      +-----+
NULL <--- | "d1"| <--- | "d2"| <--- | "d3"| <--- | "d4"| <--- | "d5"| <--- head
          +-----+      +-----+      +-----+      +-----+      +-----+

The idea here is that we will mark the top of the stack with a head pointer, and use a simple count variable to track the number of elements. The only way to get an OverFlow condition is if we cannot allocate space for a new node.

For the Stack, we start with our includes and declaration. Notice that the public declarations have not changed at all, even though the private declarations are completely different.
stack2.h

Code:

#ifndef STACK2_H
#define STACK2_H
#include <string>
#include "exceptions.h"

class Stack
{
  struct node 
  {
    std::string data;
    node* next;
  };
  node* head;
  int count;
public:
  int size(void);
  void push(std::string);
  std::string pop(void);
  std::string top(void);
  bool empty(void);
  Stack();
};

We are now using count to store the number of elements, so the implementation of size() is easy.

push(string) attempts to allocate memory for a new node. If that fails, we throw an OverFlow, otherwise we assign the data to that node. Then we insert it into our list and adjust the head pointer.

Code:

int Stack::size(void)
{
  return count;
}

void Stack::push(std::string newstring)
{
  node* temp = new node;
  if (temp==NULL)
    throw OverFlow();
  count++;
  temp->data=newstring;
  temp->next=head;
  head=temp;
}

pop() and top() both check the count first, in case of UnderFlow. top() just needs to return the data head points to. pop(), however, needs to free the memory, decrement count, and adjust head.

Code:

std::string Stack::pop(void)
{
  if (count==0)
    throw UnderFlow();
  count--;
  std::string returnval=head->data;
  node* temp = head->next;
  delete head;
  head=temp;
  return returnval;
}

std::string Stack::top(void)
{
  if (count==0)
    throw UnderFlow();
  return head->data;
}

empty() is trivial (return whether count is 0). We initialize head and count in the constructor to be safe.

Code:

bool Stack::empty(void)
{
  return count==0;
}

Stack::Stack(void)
{
  count=0;
  head=NULL;
}
#endif

end stack2.h

Notice that the new version of stack is slightly more involved than before, but is not much harder and does a much better job of managing memory. In contrast, the linked list version of the Queue will make the logic MUCH simpler, along with the improved memory. The diagram of what it looks like is this:

Code:

          +-----+      +-----+      +-----+      +-----+      +-----+
NULL <--- | "d5"| <--- | "d4"| <--- | "d3"| <--- | "d2"| <--- | "d1"| <--- head
          +-----+      +-----+      +-----+      +-----+      +-----+

             ^
             |
            tail

Notice that we need two pointers here, one for pushing new elements, and one for popping elements. Also notice that we don't have the weird "wrapping" issue that existed with the array version.

Again, notice that the public declarations are unchanged. Only the private declarations have changed.
queue2.h

Code:

#ifndef QUEUE2_H
#define QUEUE2_H
#include <string>
#include "exceptions.h"

class Queue
{
  struct node 
  {
    std::string data;
    node* next;
  };
  node* head;
  node* tail;
  int count;
public:
  int size(void);
  void push(std::string);
  std::string pop(void);
  std::string front(void);
  bool empty(void);
  Queue();
};

size() is identical the Stack version. push(string) needs to check whether the Queue is empty first. If empty, we have to set head as well as tail to the new element, otherwise we append a new element to the end of the Queue and shift tail.

Code:

int Queue::size(void)
{
  return count;
}

void Queue::push(std::string newstring)
{
  if (tail==NULL)
  {
    tail = new node;
    if (tail==NULL)
      throw OverFlow();
    head=tail;
  }
  else
  {
    tail->next = new node;
    if (tail->next==NULL)
      throw OverFlow();
   tail=tail->next;
  }
  count++;
  tail->data=newstring;
}

pop() needs to check if it's the last element being popped. If so, we need to point tail to NULL to avoid a Segmentation fault the next time we push an element.

Code:

std::string Queue::pop(void)
{
  if (count==0)
    throw UnderFlow();
  count--;
  std::string returnval=head->data;
  node* temp = head->next;
  delete head;
  head=temp;
  if (count==0)
    tail=NULL;
  return returnval;
}

std::string Queue::front(void)
{
  if (count==0)
    throw UnderFlow();
  return head->data;
}

empty() and the constructor are basically the same as Stack's.

Code:

bool Queue::empty(void)
{
  return count==0;
}

Queue::Queue(void)
{
  count=0;
  head=NULL;
  tail=NULL;
}
#endif

end queue2.h

The result of the code is:

Code:

initial size of stack: 0
initial size of queue: 0
size of stack after for loop: 20
t
s
r
q
p
o
n
m
l
k
j
i
h
g
f
e
d
c
b
a
stack underflow at i = 0
size of stack after for loop: 0
size of queue after for loop: 20
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
queue underflow at i = 0
size of queue after for loop: 0
stack contains 1 element(s)
the top element of the stack is "string"
the stack is not empty
stack contains 1 element(s)
the top element of the stack is "string"
stack contains 0 element(s)
the stack is empty
stack contains 1 element(s)
the top element of the stack is "string"
the stack is not empty
stack contains 1 element(s)
the top element of the stack is "string"
stack contains 0 element(s)
the stack is empty