Lecture Notes 11 – Lists, stacks and queues

CSS 501 – Data Structures and Object-Oriented Programming

Reading for this lecture:      

Carrano 5^th Edition: Chapter 4, 6, 7

Carrano 6^th Edition: Chapter 4, 6, 13.1-13.2

To be covered in this lecture:

• List class
• Review of stacks and queues interface
• Stack implementations
• Queue implementations

ADT List

One of the most common abstract data types that is used in computer science is the list. For example, if you maintain the information about a set of students, a set of phone numbers, or a set of images, you use some kind of list to retain the information. This lecture discusses the operations that we should be able to perform on a list and methods for implementing ADT list using a linked list data structure.

Given a set of objects, we may want to store them in sorted order or we may want to specify the order of the elements using some other criteria. For example, we may want to maintain a list of tasks that need to be done today (go to class, work on the homework, eat dinner). In this case, we may want to store them in the order that we will perform the tasks. We will use this method for now. What operations do we want for our list?

Comparison to array implementation

Let’s compare the linked list implementation of ADT List with an array implementation.

	Linked list	Array
Ease of programming		X
No size limitation	X		Can you predict the max size in advance?
No wasted storage	X
No explicit pointers		X	Less memory per list entry
Direct Access		X	Must traverse the lists to find an entry
No shifting data	X		However, insertion and deletion requires traversal.

Which is better? This depends on the application. For small lists, or those for which you know the maximum size and you are likely to use most of the list, the array implementation can be better. If you cannot limit the size, or you don’t want to waste storage, or the items are large and shifting them would be costly, the linked list implementation will probably be better. A dynamically allocate array implementation has most of the best of both worlds.

Introduction to stacks and queues

Stacks and queues are important ADTs that are commonly used in developing software. Both stack and queues represent collections of objects in some order. In a sense, both are like waiting lists. Elements are added to the list and removed from the list in a predetermined order. What makes them different is the order in which the elements are removed. Queues are like normal waiting lists. The first object on the list is also the first object removed from the list. This behavior is called “first in, first out” or FIFO. Stacks are different. In a stack the first item on the list is the last removed. Similarly, the first item removed is the last added. This is called “last in, first out” or LIFO.

In some ways, a stack can be thought of as an unfair waiting list, since items are removed in the order opposite of which they were added to the stack.

An example of a queue is the waiting list to get a table at a restaurant or to get an entry code to a class. An example of a stack would be a pile of papers on your desk. Each time you add a paper to the pile, you add it at the top. Later, when you are looking for a paper, you start at the top (the most recently added paper) and look through the stack until you find the paper that you are looking for.

Compilers use a stack to remember local variables whenever a function call is made. The local variables are added to the stack (adding to the stack is called a push) prior to the function call. When the function returns the local variables are obtained back from the stack (this is called a pop). We need to have “last in, first out” behavior, since the first function pushed onto the stack (main) is the last one that is popped.

The operations that are commonly performed on stacks and queues are:

Operation:	Name for queues:	Name for stacks (if different):
Creation	Constructor
Destruction	Destructor
Check for emptiness	isEmpty
Add an element	enQueue	Push
Remove an element	deQueue	Pop
Examine first element	getFront	getTop, or Peek

These names are not used consistently. For example, Java uses different names for several of these.

Using a stack

One example where a stack can be used is checking for balanced brackets. For example, you could have a mathematical expression like: 3*(2+[(4-5)/(1+2)]-{4*(3+2)}. Let’s assume that the expression is represented by a class called equation and that we have member functions:

• char equation::getChar(int position) const;         // returns the character at the position in the equation
• int equation::length() const;                       // returns the length of the equation

We can write a function to check for balanced parentheses as follows:

bool equation::isBalanced() const {

                        Stack<char> bracketStack;      

char stackTop;

for (int i = 0; i < length(); i++) {

char nextChar = getChar(i);

if (nextChar == ‘(‘ || nextChar == ‘{‘ || nextChar == ‘[‘)

                                                if  (!bracketStack.push(nextChar)) return false;

                                    else if (nextChar == ‘)’) {

if (bracketStack.isEmpty()) return false;

else bracketStack.pop(stackTop);

if (stackTop != ‘(‘) return false;

                                    }

else if (nextChar == ‘}’) {

if (bracketStack.isEmpty()) return false;

else bracketStack.pop(stackTop);

if (stackTop != ‘{‘) return false;

                                    }          

else if (nextChar == ‘]’) {

if (bracketStack.isEmpty()) return false;

else bracketStack.pop(stackTop);

if (stackTop != ‘[‘) return false;

                                    }

                        }

return bracketStack.isEmpty();

}

Using a queue

Let’s consider a program that reads in single-digit numbers from the keyboard until a non-number is read and then converts the list of numbers into a single multiple-digit integer. We will use a queue to store the numbers. You might ask why we use a queue here, rather than processing the numbers as they come in. In this example, we could. However, suppose the numbers were coming in very quickly from another computer, so that we didn’t have time to process a number before the next number came in. In this case, we need a method to store the numbers, so that we can process them when we have time.

// Gets a sequence of digits from the keyboard and returns the integer value.

            // Reads chars until a non-digit is encountered.

int getInt() {

            Queue<char> charQ;

char next;

cin >> next;

while (next >= '0' && next <='9') {

charQ.enqueue(next);

cin >> next;

            }

int total = 0;

while (!charQ.isEmpty()) {

charQ.dequeue(next);

total = 10 * total + int(next - '0');

            }

return total;

}

Stack Implementations

The implementation is a little easier for stacks, so we will start with those. Stack implementations:
     Array: StackA.h, StackA.cpp
     Pointers: StackP.h, StackP.cpp
     List class: StackL.h, StackL.cpp

Stack implementation comparison

Let’s compare the three implementations that we have seen. Note that ADT List could have been implemented using either an array or a linked list. Some of the same issues that we discussed for ADT List also apply here, but note that we only insert into the top of the stack, so that makes some operations easier.

	Array	Linked-list	ADT List
Size	Fixed	Unlimited	Depends
Implementation	Medium Difficulty	Highest difficult	Lowest difficulty
Insert/delete	Quick	Quick	Quick/slow?
Wasted storage	Yes	No	Maybe
Extra memory for pointers	No	Yes	Maybe

Which implementation should be used? It depends. If you have a good implementation of ADT List using pointers, that is a good choice, since it is easy to implement and allows unlimited size. Otherwise, the choice depends on whether you can predict the maximum size of the stack and whether or not wasting storage is important. 

Queue implementations

Here are links to the queue implementations:
     Array: QueueA.h, QueueA.cpp
     Pointers: QueueP.h, QueueP.cpp
     List class: QueueL.h, QueueL.cpp

Comparison

The comparison of the implementations is nearly the same as it was for stacks. The array-based implementation is a little easier than the pointer-based implementation, but it has a fixed size queue. The ADT list implementation is the easiest. If a good implementation of ADT list is available, then this might be a reasonable choice. Note however, that this implementation won’t be completely efficient with either an array or pointer-based implementation of ADT list. With the pointer implementation, enqueue will always insert at the end of the list, which requires a list traversal (unless the list implementation is changed to use both head and tail pointers). With the array implementation, dequeue will always remove from the beginning of the list, which requires shifting the other data elements. The implementations that don’t use ADT list are both more efficient, since neither list traversal, nor shifting, is ever required. 

Summary of position-oriented ADTs

We’ve looked at three related abstract data types (lists, stacks, and queues) that have some things in common. They all maintain a collection of data (objects of some type) in some order. The difference in these ADTs is in the positions that they operate on the data:

• Lists have unrestricted access to add, retrieve, or delete any item in the list.
• Stacks are restricted to adding, retrieving, and deleting at the top of the stack.
• Queues are restricted to adding at the back, retrieving, and deleting at the front.

Practice problems (optional):

Carrano 5^th Ed:

Chapter 6:

Exercises: #1, #4

Chapter 7:

Exercises: #3, #4

Carrano 6^th Ed:

Chapter 6: Exercise: #3, #5

Chapter 13: Exercise: #3, #6