|
||||||
| C Tutorials All C Tutorials and Code |
![]() |
|
|
LinkBack | Thread Tools | Search this Thread | Display Modes |
|
||||
|
ADTs: Stacks and Queues Part 2: Using Lists
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 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
Code:
+-----+ +-----+ +-----+ +-----+ +-----+
NULL <--- | "d1"| <--- | "d2"| <--- | "d3"| <--- | "d4"| <--- | "d5"| <--- head
+-----+ +-----+ +-----+ +-----+ +-----+
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();
};
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;
}
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;
}
Code:
bool Stack::empty(void)
{
return count==0;
}
Stack::Stack(void)
{
count=0;
head=NULL;
}
#endif
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
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();
};
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;
}
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;
}
Code:
bool Queue::empty(void)
{
return count==0;
}
Queue::Queue(void)
{
count=0;
head=NULL;
tail=NULL;
}
#endif
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
__________________
CodeCall Blog | CodeCall Wiki | Shareware Programming is a branch of mathematics. My CodeCall Blog | My Personal Blog |
|
||||
|
Re: ADTs: Stacks and Queues Part 2: Using Lists
Wow, excellent read! +Rep!
__________________
Questions and Answers | Online News and Social Bookmarking | Code and Text Collaboration General Chat Forum |
|
||||
|
Re: ADTs: Stacks and Queues Part 2: Using Lists
Make sure you read part 1 to get the full picture of what's going on.
__________________
CodeCall Blog | CodeCall Wiki | Shareware Programming is a branch of mathematics. My CodeCall Blog | My Personal Blog |
![]() |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | Search this Thread |
| Display Modes | |
|
|
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| C++ ADTs: Stacks and Queues Part 1: Using Arrays | WingedPanther | C Tutorials | 9 | 11-15-2009 08:45 PM |
| Lists, Stacks, and Queues | Sionofdarkness | Python | 2 | 07-26-2006 09:38 PM |
All times are GMT -5. The time now is 06:55 AM.
Amrosama.cc
Arekbulski.cc
Debtboy.cc
Guest.cc
Jaan.cc
James.cc
Mathx.cc
Tsz.cc
Vswe.cc