13.2 Stacks and Queues
But many who are first now will be last, and many who are last now will be first.
MATTHEW 19:30
Linked lists have many applications. In this section we give two samples of what they can be used for. We use linked lists to give implementations of two data structures known as a stack and a queue. In this section we always use regular linked lists and not doubly linked lists.
Stacks
A stack is a data structure that retrieves data in the reverse of the order in which the data is stored. Suppose you place the letters 'A', 'B', and then 'C' in a stack. When you take these letters out of the stack, they will be removed in the order 'C', 'B', and then 'A'. This use of a stack is diagrammed in Display 13.16. As shown there, you can think of a stack as a hole in the ground. In order to get something out of the stack, you must first remove the items on top of the one you want. For this reason a stack is often called a last-in/first-out (LIFO) data structure.
Display 13.16 A Stack
Stacks are used for many language processing tasks.In Chapter 14 we will discuss how the computer system uses a stack to keep track of C++ function calls. However, here we will do only one very simple application. Our goal in this example is to show you how you can use the linked list techniques to implement specific data structures; a stack is one simple example of the use of linked lists.You need not read Chapter 14 to understand this example.
Programming Example A Stack Class
The interface for our Stack class is given in Display 13.17. This particular stack is used to store data of type char. You can define a similar stack to store data of any other type. There are two basic operations you can perform on a stack: adding an item to the stack and removing an item from the stack. Adding an item is called pushing the item onto the stack, and so we called the member function that does this push. Removing an item from a stack is called popping the item off the stack, and so we called the member function that does this pop.
Display 13.17 Interface File for a Stack Class
1 //This is the header file stack.h. This is the interface for the class Stack,
2 //which is a class for a stack of symbols.
3 #ifndef STACK_H
4 #define STACK_H
5 namespace stacksavitch
6 {
7 struct StackFrame
8 {
9 char data;
10 StackFrame *link;
11 };
12 typedef StackFrame* StackFramePtr;
13 class Stack
14 {
15 public:
16 Stack( );
17 //Initializes the object to an empty stack.
18 Stack(const Stack& aStack);
19 //Copy constructor.
20 ~Stack( );
21 //Destroys the stack and returns all the memory to the freestore.
22 void push(char theSymbol);
23 //Postcondition: theSymbol has been added to the stack.
24 char pop( );
25 //Precondition: The stack is not empty.
26 //Returns the top symbol on the stack and removes that
27 //top symbol from the stack.
28 bool empty( ) const;
29 //Returns true if the stack is empty. Returns false otherwise.
30 private:
31 StackFramePtr top;
32 };
33 }//stacksavitch
34 #endif //STACK_H
The names push and pop derive from another way of visualizing a stack. A stack is analogous to a mechanism that is sometimes used to hold plates in a cafeteria. The mechanism stores plates in a hole in the countertop. There is a spring underneath the plates with its tension adjusted so that only the top plate protrudes above the countertop. If this sort of mechanism were used as a stack data structure, the data would be written on plates (which might violate some health laws, but still makes a good analogy). To add a plate to the stack, you put it on top of the other plates, and the weight of this new plate pushes down the spring. When you remove a plate, the plate below it pops into view.
Display 13.18 shows a simple program that illustrates how the Stack class is used. This program reads a word one letter at a time and places the letters in a stack. The program then removes the letters one by one and writes them to the screen. Because data is removed from a stack in the reverse of the order in which it enters the stack, the output shows the word written backward.
Display 13.18 Program Using the Stack Class
1 //Program to demonstrate use of the Stack class.
2 #include <iostream>
3 #include "stack.h"
4 using namespace std;
5 using namespace stacksavitch;
6
7 int main( )
8 {
9 stack s;
10 char next, ans;
11
12 do
13 {
14 cout << "Enter a word: ";
15 cin.get(next);
16 while (next != '\n')
17 {
18 s.push(next);
19 cin.get(next);
20 }
21
22 cout << "Written backward that is: ";
23 while ( ! s.empty( ) )
24 cout << s.pop( );
25 cout << endl;
26
27 cout << "Again?(y/n): ";
28 cin >> ans;
29 cin.ignore(10000, '\n');
30 } while (ans != 'n' && ans != 'N');
31
32 return 0;
33 }
<The ignore member of cin is discussed in Chapter 8. It discards input remaining on the current input line up to 10,000 characters or until a return is entered. It also discards the return ('\n') at the end of the line.>
Sample Dialogue
Enter a word: straw Written backward that is: warts Again?(y/n): y Enter a word: C++ Written backward that is: ++C Again?(y/n): n
As shown in Display 13.19, our Stack class is implemented as a linked list in which the head of the list serves as the top of the stack. The member variable top is a pointer that points to the head of the linked list.
Display 13.19 Implementation of the Stack Class
1 //This is the implementation file stack.cpp.
2 //This is the implementation of the class Stack.
3 //The interface for the class Stack is in the header file stack.h.
4 #include <iostream>
5 #include <cstddef>
6 #include "stack.h"
7 using namespace std;
8
9 namespace stacksavitch
10 {
11 //Uses cstddef:
12 Stack::Stack( ) : top(NULL)
13 {
14 //Body intentionally empty.
15 }
16
17 Stack::Stack(const Stack& aStack)
<The definition of the copy constructor is Self-Test Exercise 11.>
18 Stack::~Stack( )
19 {
20 char next;
21 while (! empty( ))
22 next = pop( ); //pop calls delete.
23 }
24
25 //Uses cstddef:
26 bool Stack::empty( ) const
27 {
28 return (top == NULL);
29 }
30
31 void Stack::push(char theSymbol)
<The rest of the definition is Self-Test Exercise 10.>
32 //Uses iostream and cstdlib:
33 char Stack::pop( )
34 {
35 if (empty( ))
36 {
37 cout << "Error: popping an empty stack.\n";
38 exit(1);
39 }
40
41 char result = top->data;
42
43 StackFramePtr tempPtr;
44 tempPtr = top;
45 top = top->link;
46
47 delete tempPtr;
48
49 return result;
50 }
51 }//stacksavitch
Writing the definition of the member function push is Self-Test Exercise 10. However, we have already given the algorithm for this task. The code for the push member function is essentially the same as the function headInsert shown in Display 13.4, except that in the member function push we use a pointer named top in place of a pointer named head.
An empty stack is just an empty linked list, so an empty stack is implemented by setting the pointer top equal to NULL. Once you realize that NULL represents the empty stack, the implementations of the default constructor and of the member function empty are obvious.
The definition of the copy constructor is a bit complicated but does not use any techniques we have not already discussed. The details are left to Self-Test Exercise 11.
The pop member function first checks to see if the stack is empty. If the stack is not empty, it proceeds to remove the top character in the stack. It sets the local variable result equal to the top symbol on the stack. That is done as follows:
char result = top->data;
After the symbol in the top node is saved in the variable result, the pointer top is moved to the next node on the linked list, effectively removing the top node from the list. The pointer top is moved with the following statement:
top = top->link;
However, before the pointer top is moved, a temporary pointer, called tempPtr, is positioned so that it points to the node that is about to be removed from the list. The node can then be removed with the following call to delete:
delete tempPtr;
Each node that is removed from the linked list by the member function pop is destroyed with a call to delete. Thus, all that the destructor needs to do is remove each item from the stack with a call to pop. Each node will then have its memory returned to the freestore.
Self-Test Exercises
Give the definition of the member function push of the class Stack described in Display 13.17.
Give the definition of the copy constructor for the class Stack described in Display 13.17.
Queues
A stack is a last-in/first-out data structure. Another common data structure is a queue, which handles data in a first-in/first-out (FIFO) fashion. A queue behaves exactly the same as a line of people waiting for a bank teller or other service. The people are served in the order they enter the line (the queue). The operation of a queue is diagrammed in Display 13.20.
Display 13.20 A Queue
A queue can be implemented with a linked list in a manner that is similar to our implementation of the Stack class. However, a queue needs a pointer at both the head of the list and at the other the end of the linked list, since action takes place in both locations. It is easier to remove a node from the head of a linked list than from the other end of the linked list. So, our implementation will remove a node from the head of the list (which we will now call the front of the list) and we will add nodes to the other end of the list, which we will now call the back of the list (or the back of the queue).
Programming Example A Queue Class
The interface for our queue class is given in Display 13.21. This particular queue is used to store data of type char. You can define a similar queue to store data of any other type. There are two basic operations you can perform on a queue: adding an item to the end of the queue and removing an item from the front of the queue.
Display 13.21 Interface File for a Queue Class
1 //This is the header file queue.h. This is the interface for the class Queue,
2 //which is a class for a queue of symbols.
3 #ifndef QUEUE_H
4 #define QUEUE_H
5 namespace queuesavitch
6 {
7 struct QueueNode
8 {
9 char data;
10 QueueNode *link;
11 };
12 typedef QueueNode* QueueNodePtr;
13
14 class Queue
15 {
16 public:
17 Queue();
18 //Initializes the object to an empty queue.
19 Queue(const Queue& aQueue);
20 ~Queue();
21 void add(char item);
22 //Postcondition: item has been added to the back of the queue.
23 char remove();
24 //Precondition: The queue is not empty.
25 //Returns the item at the front of the queue and
26 //removes that item from the queue.
27 bool empty() const;
28 //Returns true if the queue is empty. Returns false otherwise.
29 private:
30 QueueNodePtr front; //Points to the head of a linked list.
31 //Items are removed at the head
32 QueueNodePtr back; //Points to the node at the other end of the
33 //linked list. Items are added at this end.
34 };
35 }//queuesavitch
36 #endif //QUEUE_H
Display 13.22 shows a simple program that illustrates how the queue class is used. This program reads a word one letter at a time and places the letters in a queue. The program then removes the letters one by one and writes them to the screen. Because data is removed from a queue in the order in which it enters the queue, the output shows the letters in the word in the same order that the user entered them. It is good to contrast this application of a queue with a similar application using a stack that we gave in Display 13.18.
Display 13.22 Program Using the Queue Class
1 //Program to demonstrate use of the Queue class.
2 #include <iostream>
3 #include "queue.h"
4 using namespace std;
5 using namespace queuesavitch;
6
7 int main()
8 {
9 Queue q;
10 char next, ans;
11
12 do
13 {
14 cout << "Enter a word: ";
15 cin.get(next);
16 while (next != '\n')
17 {
18 q.add(next);
19 cin.get(next);
20 }
21
22 cout << "You entered:: ";
23 while ( ! q.empty() )
24 cout << q.remove();
25 cout << endl;
26
27 cout << "Again?(y/n): ";
28 cin >> ans;
29 cin.ignore(10000, '\n');
30 } while (ans !='n' && ans != 'N');
31
32 return 0;
33 }
<The ignore member of cin is discussed in Chapter 8. It discards input remaining on the current input line up to 10,000 characters or until a return is entered. It also discards the return (‘\n’) at the end of the line.>
Sample Dialogue
Enter a word: straw You entered: straw Again?(y/n): y Enter a word: C++ You entered: C++ Again?(y/n): n
As shown in Displays 13.21 and 13.23, our queue class is implemented as a linked list in which the head of the list serves as the front of the queue. The member variable front is a pointer that points to the head of the linked list. Nodes are removed at the head of the linked list. The member variable back is a pointer that points to the node at the other end of the linked list. Nodes are added at this end of the linked list.
Display 13.23 Implementation of the Queue Class
1 //This is the implementation file queue.cpp.
2 //This is the implementation of the class Queue.
3 //The interface for the class Queue is in the header file queue.h.
4 #include <iostream>
5 #include <cstdlib>
6 #include <cstddef>
7 #include "queue.h"
8 using namespace std;
9
10 namespace queuesavitch
11 {
12 //Uses cstddef:
13 Queue::Queue() : front(NULL), back(NULL)
14 {
15 //Intentionally empty.
16 }
17
18 Queue::Queue(const Queue& aQueue)
19 <The definition of the copy constructor is Self-Test Exercise 12.>
20
21 Queue::~Queue()
22 <The definition of the destructor is Self-Test Exercise 13.>
23
24 //Uses cstddef:
25 bool Queue::empty() const
26 {
27 return (back == NULL); //front == NULL would also work
28 }
29
30 //Uses cstddef:
31 void Queue::add(char item)
32 {
33 if (empty())
34 {
35 front = new QueueNode;
36 front->data = item;
37 front->link = NULL;
38 back = front;
39 }
40
41 else
42 {
43 QueueNodePtr tempPtr;
44 tempPtr = new QueueNode;
45 tempPtr->data = item;
46 tempPtr->link = NULL;
47 back->link = tempPtr;
48 back = tempPtr;
49 }
50 }
51
52 //Uses cstdlib and iostream:
53 char Queue::remove()
54 {
55 if (empty())
56 {
57 cout << "Error: Removing an item from an empty queue.\n";
58 exit(1);
59 }
60
61 char result = front->data;
62
63 QueueNodePtr discard;
64 discard = front;
65 front = front->link;
66 if (front == NULL) //if you removed the last node
67 back = NULL;
68
69 delete discard;
70
71 return result;
72 }
73 }//queuesavitch
An empty queue is just an empty linked list, so an empty queue is implemented by setting the pointers front and back equal to NULL. The rest of the details of the implementation are similar to things we have seen before.
Self-Test Exercises
Give the definition of the copy constructor for the class
Queuedescribed in Display 13.21.Give the definition of the destructor for the class
Queuedescribed in Display 13.21.