Creating a Push Member Function in C++

Now that you’ve seen how to define a class that creates a stack, we’ll show you how to define additional member functions that enable the class to push values onto the stack. Pushing a value onto the stack is a two-step process. First, you must determine if there is room on the stack for another value. If there is, you push the value onto the stack; otherwise, you don’t.

We’ll create different member functions for each step, beginning by defining a member function that determines if there is room on the stack. We’ll call it isFull() and define it in the following code. The isFull() member function is simple. It compares the value of the top attribute with the one less than the value of the size attribute.

The value of the top attribute is –1 when the instance of the stack is declared. Suppose the value of size is 10. The condition expression in the if statement of the isFull() member function determines if the value of top, which is –1, is 1 less than the value of size. Since the value of size is 10, the condition expression compares –1 < 9. If top is greater than or equal to 9, then a true is returned; otherwise, a false is returned.

Why do you subtract 1 from the size of the stack? The value of the top attribute is an index of an array element. Remember that the index begins with zero. In contrast, the size is actually the number of array elements in the stack. Therefore, the tenth array element on the stack has an index of 9.

bool isFull()
 {
  if(top < size-1)
  {
  return false;
  }
  else
  {
  return true;
  }
 }

With the isFull() member function defined, we’ll move on to defining the push() member function, as shown in the next example. The push() member function pushes a value onto the stack. The value being pushed onto the stack is passed as an argument to the push() member function and is assigned to the variable x in this example.

Before doing anything else, the push() member function determines if there is room on the stack by calling the isFull() member function in the condition expression of the if statement. The condition expression might look a little strange because the call is preceded by an exclamation point (!) so we’ll take apart the condition expression to explain what is really happening here.

Remember from your programming classes that statements within an if statement execute only if the condition expression is true. This means the condition expression must be true for the value passed to the push() member function to be placed on the stack.

Here’s a slight problem. We’re calling the isFull() member function to determine if there is room on the stack for another value. However, the isFull() member function returns false if there is room and true if there isn’t room. A false causes the push() member function to skip statements that place the value on the stack. We really need the isFull() member function to return a true if there is room available, not a false. Rather than rewrite the isFull() member function, we use the exclamation point to reverse the logic. As you remember from your programming class, the exclamation point is the not operator—that is, a false is treated as a true, which causes the value to be placed on the stack.

There are two statements within the if statement. The first statement increments the value of the top attribute, which is the index of the last value placed on the stack. If the stack is empty, then the current value of the top attribute is –1. Incrementing –1 changes the value of the top attribute to 0, which is the index of the first array element of the stack. The last statement in the if statement assigns the value passed to the push() member function to the next available array element.

void push(int x)
 {
  if(!isFull())
  {
  top++;
  values[top] = x;
  }
 }

Creating a Pop Member Function in C++

We still need a way to remove values from the stack. To do this, we need to define two additional member functions, isEmpty() and pop(). The isEmpty() member function determines if there are any values on the stack. The pop() member function removes the value from the top of the stack.

Let’s define the isEmpty() member function in this next example. The isEmpty() member function contains an if statement. The condition expression of the if statement compares the value of the top attribute to –1. Remember that –1 is the initial value of the top attribute when the instance of a stack is declared. If the top attribute is equal to –1, then a true is returned because the stack is empty; otherwise, a false is returned.

bool isEmpty()
 {
  if(top == -1)
  {
  return true;
  }
  else
  {
  return false;
  }
 }

The pop() member function of the Stack class has the job of changing the index that is at the top of the stack and returning the value of the corresponding array to the statement that calls the pop() member function. The next example defines the pop() member function.

The first statement in the definition declares an integer variable called retVal that stores the value returned by the pop() member function. The retVal is initialized to zero.

Next, the isEmpty() member function is called in the condition expression of the if statement to determine if there is a value at the top of the stack. Notice the exclamation point reverses the logic as it did in the pop() member function.

Statements within the if statement should only execute if the isEmpty() member function returns a false, meaning the stack is not empty. Therefore, we need to use the exclamation point to reverse the logic of the condition expression to make the condition expression true if the isEmpty() member function returns a false.

Two steps occur within the if statement. First, the value at the top of the stack is assigned to the retVal variable by referencing the values array using the index contained in the top attribute. Next, the value of the top attribute is decremented. The return retVal is then returned by the pop() member function.

int pop()
 {
  int retVal = 0;
  if(!isEmpty())
  {
  retVal = values[top];
  top--;
  }
  return retVal;
 }

Stack in Action Using C++

Now that you understand how to create and use a stack, we’ll pick up the pace and explore an industrial-strength stack. You’ve may have heard the term industrial strength used in relation to programming and may be curious what this really means.

Industrial strength is a term used in industry that implies a product is designed to withstand stress. Industrial strength can be used to describe any kind of product, but in this case the product is the program that creates and uses a stack.

Programs used to illustrate the concepts of a stack in this chapter are bare bones and lack the robust features that are found in industrial-strength programs. A bare-bones program is what you need when you’re learning the concepts of stacks and other data structures because the program contains only statements that pertain to what you are learning.

However, once you learn the concept, you need to see how it’s applied in a real-world program. That’s what we’ll be exploring in the “Stack in Action” sections of this chapter. In this section, you’ll take a look at how a stack is created and used in an industrial-strength C++ program. Later, you’ll see the Java version of this program.

We’ll use as an example an industrial-strength C++ program that creates and uses a stack. The program is contained within three files, stack.h, stack.cpp, and stackDemo.cpp. The stack.h file is a header file that contains the definition of the Stack class, which is the “blueprint” of the Stack class. The stack.cpp file is a source code file that contains the implementation of the member functions of the Stack class. The stackDemo.cpp file contains the source code for the C++ program that declares the instance of the Stack class and calls its member functions. Let’s begin by taking a look at the stack.h header file, which is shown in the next code example. As you’ll recall from your C++ classes, a header file typically contains definitions and preprocessor instructions. A preprocessor is a program that applies preprocessor instructions to source code before the code is compiled.

The stack.h header file contains one preprocessor instruction, #define, which defines a symbol. Here we’ve defined the symbol DEFAULT_SIZE and given it a value of 10. The preprocessor then replaces all occurrences of DEFAULT_SIZE with 10 before the code is compiled. The DEFAULT_SIZE is the default size of the stack if the no argument is passed to the constructor. Function parameters in C and C++ can be assigned default values in the function prototype as long as those arguments are at the end of the argument list. If the size value is not passed in, it gets defaulted to the value of DEFAULT_SIZE, which is 10 in our example.

The stack.h file also contains the definition of the Stack class. The Stack class definition has the same size, top, and values attributes you saw in the previous C++ example. However, the definition of member functions is different from what you saw because member functions are implemented outside the class definition in the stack.cpp source code file. The header file contains only the prototype of the functions, which make up the blueprint for the class.

From your C++ class, you’ll remember that only the prototype or signature of a member function needs to be included in a class definition. The implementation of the member function can be outside the class definition. There are two important reasons for keeping the definition (header file) and implementation (source) in separate files:

• It keeps your development environment cleaner and easier to understand.

• It allows you to provide a commercial software application programmer interface to a programmer without handing over your source code. You provide the programmer with your header files, which they will use to compile their code (they only need header files to compile the code). You provide your source code in the form of precompiled libraries that are referenced by the programmer’s program during linking.

The class definition contains signatures of six member functions. The first member function is called Stack, which is the constructor that you learned about previously in this chapter. Previously, you learned that the constructor is passed an integer representing the size of the stack. In the real-world version, the program sets a default size that can be overridden when an instance of the class is created in the program. The default size is specified by using the DEFAULT_SIZE, which is 10 (see #define).

The next member function is ~Stack() and is the destructor of the class. A destructor is the last member function that is called when the instance of the class goes out of scope and dies. A constructor must always be the same name as the class and begin with a tilde (~). By definition, destructors cannot accept any arguments. The purpose of the destructor is to free memory that is used by the stack or do any other sort of cleanup that’s required.

The remaining member functions are the same functions that you learned about previously in this chapter.

//stack.h
 #define DEFAULT_SIZE 10
 class Stack 
 {
  private:
  int size;
  int top;
  int* values;
  public:
  Stack(int size = DEFAULT_SIZE);
  virtual ~Stack();
  bool isFull();
  bool isEmpty();
  void push(int);
  int pop();
 };
 

The stack.cpp file is a source code file that contains the implementation of the Stack class’s member functions. We placed these in a different file from the class definition because it is easier to read and maintain as well as for other reasons explained previously.

The file begins with the preprocessor instruction #include that tells the computer to evaluate the contents of the stack.h file before compiling the stack.cpp file so it “knows” about the Stack class definition before compiling the program.

Member functions in the stack.cpp file will be familiar to you because all except one are the same member functions that you learned about previously in the chapter. However, the names of the member functions might be confusing at first glance because each name begins with the name of the class followed by two colons (::). The two colons are called the scope resolution operator.

You must precede the name of a member function with the class name and scope resolution operator if the member function is defined outside the class definition. Think of this as telling the computer that the member function belongs to the Stack class.

The ~Stack() member function frees memory used by the stack. It does this by using the delete operator and referencing the name of the array used for the stack. In this example, values is the name of the array.

To avoid memory leaks, freeing memory is important whenever memory is dynamically allocated. The square brackets ([]) are used with delete because the object being removed from memory was dynamically created.

The stack.cpp is compiled as you would compile any source code. The result is an object file that is joined together with the compiled stackDemo.cpp source code file by the linker to create an executable program called a load module.

//stack.cpp
 #include "stack.h"
 Stack::Stack(int size)
 {
  this->size = size;
  values = new int[size];
  top = -1;
 }
 Stack::~Stack()
 {
  delete[] values;
 }
 bool Stack::isFull()
 {
  if(top < size-1)
  {
  return false;
  }
  else
  {
  return true;
  }
 }
 bool Stack::isEmpty()
 {
  if(top == -1)
  {
  return true;
  }
  else
  {
  return false;
  }
 }
 void Stack::push(int x)
 {
  if(!isFull())
  {
  top++;
  values[top] = x;
  }
 }
 int Stack::pop()
 {
  int retVal = 0;
  if(!isEmpty())
  {
  retVal = values[top];
  top--;
  }    
  return retVal;
 }

Finally, we come to the stackDemo.cpp program, which is the C++ program that creates the instance of the Stack class. The first statement creates the stack in a three-step process. The first step is to use the new operator to allocate space in memory for the Stack class by calling the constructor of the class. The new operator returns the memory location of the stack. The second step is to declare a pointer called stack. The last step is to assign the memory location returned by the new operator to the stack pointer.

In this example, we used the default size for the stack, which is 10 elements. We can pass the Stack() constructor an integer to change the size of the stack.

The push() member function is called three times. Each time a different value is placed on the stack. Notice that the -> pointer is used instead of the dot operator. You must do this because stack is a pointer to an instance of the class and not the instance itself.

The last portion of the stackDemo.cpp program calls the pop() member three times. Each time a value is removed from the top of the stack and displayed on the screen.

//stackDemo.cpp
 void main() {
  Stack *stack = new Stack();
  stack->push(10);
  stack->push(20);
  stack->push(30);
  for(int i=0; i<3; i++)
  {
  cout << stack->pop() << endl;
  }
 }

Chapter 5: Queues Using anArray

You probably never thought that waiting in line in the supermarket would help you become a whiz at data structures, but it’s a big help: the checkout line at a supermarket is similar to the way data structures are organized. We’re the “things” organized by the supermarket line, and the same kind of organization is used for data within your program. The checkout line in your program is called a queue. In this chapter, you’ll learn the ins and outs of implementing a queue within your program.

A Queue

A queue is like the checkout line at the supermarket where the first customer is at the front of the line, the second customer is next in line, and so on until you reach the last customer who is at the back of the line. Customers check out of the supermarket in the order they arrive in the line. That is, the first customer is the first one to check out. This is referred to as first in, first out (fifo).

The same concept applies to a queue in your program. A queue is a sequential organization of data. Data is accessible using fifo. That is, the first data in the queue is the first data that is accessible by your program. In this chapter, you will explore the simplest type of queue, a fixed size, first in, first out queue using an array. In Chapter 8, you will learn how to build a priority queue using a linked list. With a priority queue, the elements are removed based on two factors, the order they were placed in the queue and the priority of the element.

A Simple Queue vs. Priority Queue

Programmers use one of two kinds of queues depending in the objective of the program, a simple queue or a priority queue. A simple queue organizes items in a line where the first item is at the beginning of the line and the last item is at the back of the line. Each item is processed in the order in which it appears in the queue. The first item in line is processed first, followed by the second item and then the third until the last item on the line is processed. There isn’t any way for an item to cut the line and be processed out of order.

A priority queue is similar to a simple queue in that items are organized in a line and processed sequentially. However, items on a priority queue can jump to the front of the line if they have priority. Priority is a value that is associated with each item placed in the queue. The program processes the queue by scanning the queue for items with high priority. These are processed first regardless of their position in the line. All the other items are then processed sequentially after high priority items are processed.

You’ll learn how to create and use a priority queue in Chapter 8. For now, we’ll keep things simple by creating and using a simple queue.

The Business of Queues

Queues are very important in business applications that require items to be processed in the order they are received. The supermarket checkout line is a queue that most of us have experienced, but you won’t be creating a supermarket checkout line in a program unless the program is designed to simulate a checkout line.

In the real world, queues are used in programs that process transactions. A transaction is a set of information such as an order form. Transaction information is received by a program and then placed in a simple queue waiting to be processed by another part of the program.

Let’s return to a supermarket to see how this works. The cash register is a computer that runs a transaction program that, among other things, processes the bar code on each product scanned at the checkout counter.

One of the first steps to processing the bar code is to look up the price. There could be 20 or more cash registers in a busy supermarket all trying to look up prices at the same time. However, the computer can process only one bar code at a time. The program that look ups prices manages the demand by using a simple queue in which each new request is placed at the back of the queue, and the program looks up the bar code that is at the front of the queue.

Many other applications use a simple queue to maintain the order in which to process items. These include programs that process stock and bond trades and those that process students registering for a course. Queues are also used within a computer to manage printing.

The Array and the Queue

Data organized by a queue may be stored in an array. The queue determines the array element that is at the front and back of the queue. The array is not the queue. Likewise, the queue is not the array. Both are two separate things. This is an important concept to grasp and one that may be difficult to understand at first.

Take a look at Figure 5-1 and you’ll see how an array and a queue are different and yet are linked together to organize data. The array is pictured as a block of elements. The queue is pictured as a circle. The empty boxes are where values are stored in the queue, and the numbers correspond to the index of the array that is associated with the queue. To the right of the circle are three values. The front and back values store the index of the front and back of the queue. The size value is the number of elements in the queue, which is 8 in this example.

Figure 5-1: The queue is different from the array used to store data that appears in the queue.

Enqueue

A value is placed in the queue by performing the enqueue process, which consists of two steps. The first step is to identify the array element that is at the back of the queue. However, this is not necessarily the last element of the array. Remember that the queue is not the array. The back of the queue is calculated by using the following formula:

back = (back+1) % size

Figure 5-2 shows how to use the formula and gives the values for the front, back, and size of the queue. The front and back variables are set to zero because the queue is empty, and size is set to 8 because the array has 8 elements.

Figure 5-2: The enqueue process places a new value at the back of the queue.

The next box shows the formula that identifies the back of the queue and assigns it the value 90. To the right of this box is the same formula with variable names replaced by actual values. Let’s take a closer look at this and see how the back of the queue is calculated.

The first operation occurs within the parentheses, where 1 is added to the value of the back variable. The modulus operator determines where the next element should be placed in the queue by performing an integer division and returning the remainder of the division.

Although we’ve described a queue as a checkout line in the supermarket, a queue is actually circular. This is illustrated in the calculation used to determine the back of the queue, as shown here:

(7 + 1) % 8

When you get to the last element in the array at index 7, the calculation returns 0 (8 divided by 8 is 1 and the remainder is 0). So after the last element in the array, you come around to the beginning of the array as the back of the queue. As you’ll see in the “Queues Using an Array in C++” section of this chapter, you check to see if you’re at the front of the queue before placing an item at the back of the queue so you don’t overwrite the item at the front and corrupt the queue.

The second step is to assign the value 90 to array element 1. That is, place the value 90 at the back of the queue. Remember that values are added to the queue from the back just as you go to the back of the checkout line to wait your turn at the supermarket. Notice that the value 90 is assigned to the array in Figure 5-2.

Dequeue

Dequeue is the process that removes a value from the front of the queue. It is important to understand that the value is removed from the queue, not the array. The value always remains assigned to the array until the value is either overwritten or the queue is abandoned. You’ll see how to do overwrite later in this chapter.

There are two steps in the dequeue process, as illustrated in Figure 5-3. The initial step is to calculate the index of the array element at the front of the queue using the following expression:

Figure 5-3: The dequeue process removes an item from the front of a queue.

front = (front+1) % 8

Notice that this expression is very similar to the expression used in the enqueue process to calculate the index of the array element at the back of the queue. The first operation in this expression increments the value of the front variable. As you can see in Figure 5-3, the front variable is assigned the initial value zero. Therefore, the result of the first operation is 1. The next operation is to apply the modulus operator, which is identical to the modulus operation performed in the enqueue process. The result of this operation is 1, meaning that the front of the queue is the array element whose index is 1. This value is then assigned to the front variable. Previously in this chapter, you learned that if you were at index 7 in the array, the result of this calculation would be 0 ((7+1)%8 = 0), so you would chase the queue around in a circle.

The final step in the dequeue process is to use the value located at the front of the queue. Typically, the dequeue process is a method, and the front of the queue is returned to the statement that called the method.

In Figure 5-3, the array element values[1] is at the front of the queue. The value assigned to this element is 90, which was placed at the back of the queue by the previous enqueue process.

Notice that the value 90 remains assigned to the values[1] array element in Figure 5-3 because values assigned to the array associated with a queue are not affected when a value is removed from the front of the queue. The queue keeps track of array elements that are at the front and back of the queue, not the front or back of the array. In this case, we’re using a simple integer array to illustrate the principles behind implementing the queue data structure. You may come across more complex implementations, where each element in the array is a pointer to a class object or structure. In these cases, you should be concerned about memory management when you perform enqueue and dequeue operations.

Queues Using an Array in C++

Now that you understand how queues work with an array, it is time to create a real queue. In this section, you’ll create a queue using C++. You’ll see the Java version of this program later in this chapter.

The C++ queue program is organized into three files: the queue.h file, the queue.cpp file, and the queueProgram.cpp file. The queue.h file, shown next, sets the default size of the array and defines the Queue class. The Queue class declares size, front, and back attributes that store the array size and the index of the front and back of the queue. The Queue class also declares a pointer that will point to the array. In addition to these, the Queue class defines a set of member functions that manipulate the queues. These are explained later in this section.

 //queue.h
 #define DEFAULT_SIZE 8
 class Queue{
  private:
  const int size;
  int front;
  int back;
  int* values;
  public:
  Queue(int size = DEFAULT_SIZE);
  virtual ~Queue();
  bool isFull();
  bool isEmpty();
  void enqueue(int);
  int dequeue();
 };

The queue.cpp file contains the implementation of the member functions for the Queue class. There are six member functions defined in this file: Queue(), ~Queue(), isFull(), isEmpty(), enqueue(), and dequeue().

The Queue() member function is a constructor, which is passed the size of the array when an instance of the Queue class is declared. If the constructor is called with no parameters, then the default size is used; otherwise, the value passed to the constructor is used. The value of the array size is assigned to the attribute size by the first statement within the constructor.

The second statement uses the new operator to declare an array of integers whose size is determined by the size passed to the constructor. The new operator returns a pointer to the array, which is assigned to the values pointer. The last two statements in the constructor initialize the front and back attributes to zero.

The ~Queue() member function is the destructor and uses the delete operator to remove the array from memory when the instance of the Queue class goes out of scope.

The isFull() member function (see Figure 5-4) determines if there is room available in the queue by comparing the calculated value of the back of the queue with the value of the front of the queue, as in shown Figure 5-4. Notice that the expression that calculates the back of the queue is very similar to the expression in the enqueue process (see the “Enqueue” section of this chapter), and both produce the same result. The queue is full when the back index is 1 behind the front. Placing another element in the queue would overwrite the front element and corrupt the queue. The modulus operator is used again to make this a circular queue, so when you’re at element 7 on the back, the next element to look at is element 0.

Figure 5-4: The isFull() member function determines if there is room to place another item on the back of the queue.

The isFull() member function is called by the enqueue() member function before an attempt is made to place a value on the back of the queue. The isFull() member function returns a true if no more room is available in the queue or a false if there is room available.

The isEmpty() member function determines (see Figure 5-5) if the queue is empty by comparing the back and front variables. If they have the same values, a true is returned; otherwise, a false is returned. The isEmpty() member function is called within the dequeue() member function before it attempts to remove the front item from the queue.

Figure 5-5: The isEmpty() member function determines if the queue contains any values.

The enqueue() member function places an item at the back of the queue, as described in the “Enqueue” section of this chapter. The enqueue() member function is passed the value that is to be placed in the queue. However, before doing so, the isFull() member function is called to determine if there is room available in the queue. Notice in the following example that the isFull() member function is called as the condition expression of the if statement. Also notice that the not operator reverses the bool value returned by the isFull() method. That is, a false is returned by the isFull() member function if room is available in the queue. The condition expression in the if statement reverses this logic to true so that statements within the if statement execute to place the new item on the back of the queue.

The dequeue() member function removes an item from the queue and returns that item to the statement within the program that calls the dequeue() member function. However, the isEmpty() member function is called in the condition expression of the if statement within the dequeue() member function, as shown in the next code listing.

The not operator in this expression reverses the logic returned by the isEmpty() member function. The isEmpty() member function returns a false if the queue is not empty. The not operator changes this to true, enabling statements within the if statement to remove the front item from the queue and return it to the statement that calls the dequeue() member function.

 //queue.cpp
 #include "queue.h"
 Queue::Queue(int size)
 {
  this->size = size;
  values = new int[size];
  front = 0;
  back = 0;
 }
 Queue::~Queue()
 {
  delete[] values;
 }
 bool Queue::isFull()
 {
  if( (back+1) % size == front)
  {
  return true;
  }
  else
  {
  return false;
  }
 }
 bool Queue::isEmpty()
 {
  if(back == front)
  {
  return true;
  }
  else
  {
  return false;
  }
 }
 void Queue::enqueue(int x)
 {
  if(!isFull())
  {
  back = (back+1) % size;
  values[back] = x;
  }
 }
 int Queue::dequeue()
 {
  if(!isEmpty())
  {
  front = (front+1) % size;
  return queue[front];
  }
  return 0;
 }

The queueProgram.cpp is where all the action takes place. It is here that an instance of the Queue class is declared and manipulated. As you can see in the next example, the first statement in the program uses the new operator to declare an instance of the Queue class and set the size to 8 elements. The new operator returns a pointer that is assigned to a pointer to an instance of the Queue class.

The next three statements call the enqueue() member function three times to place the values 10, 20, and 30 in the queue, respectively. The program concludes by calling the dequeue() member function three times to display the contents of the queue. Figure 5-6 shows the queue and the array after the last call to the enqueue() member function is made.

Figure 5-6: Here’s the queue and the array after the last call to the enqueue() member function is made.

 //queueProgram.cpp
 #include <iostream>
 using namespace std;
 void main(){
  Queue *queue = new Queue(8);
  queue->enqueue(10);
  queue->enqueue(20);
  queue->enqueue(30);
  for(int i=0; i<3; i++)
  {
  cout << queue->dequeue() << endl;
  }
 }

Оставьте свой комментарий !
Ваше имя: Комментарий: Оба поля являются обязательными  Автор   Комментарий к данной статье