Creating a Stack in C

Creating a Stack in C++

You can create a stack in C++ by defining a stack class and declaring an instance of the class. The Stack class requires three attributes and several member functions, which are defined as you learn about them. You ll begin by defining a basic stack class that has only the components needed to create the stack.

The class is called Stack , but you can call it any name you wish. This class definition is divided into a private access specifier section and a public access specifier section. The private access specifier section has attributes and member functions (although not in this example) that are accessible only by a member function defined in this class. The public access specifier section has attributes (although not in this example) and member functions that are accessible by using an instance of the class.

The private access specifier section of the Stack class defines three attributes: size , top , and values , all of which are integers. The size attribute stores the number of elements in the stack, the top attribute stores the index of the top element of the stack, and the values attribute is a pointer to the stack, which is an array. The stack in this example is a stack of integer values, but you can use an array of any data type, depending on the nature of your program.

Only one member function is defined in the Stack class, although we ll define other member functions for the class in upcoming sections of this chapter. For now, let s keep the example simple and easy to understand.

This member function is called Stack , which is the constructor of the class. A constructor is a member function that has the same name as the class and is called when an instance of the class is created. The code for this is on the next page.

Several things are happening in the constructor. First, the constructor receives an integer as an argument that is passed when the instance of the Stack class is declared. The integer determines the number of elements in the stack and is assigned to the size variable.

The first statement might look a bit confusing. It appears that the value of the size variable from the argument list is being assigned to itself, but that s not the case. Actually, the size variable from the argument list is local to the Stack member function. The this- > size combination refers to the size attribute of the Stack class, as shown here:

 this->size = size; 

Programmers use the this pointer within a member function to refer to the current instance of the class. In this example, the this pointer uses the pointer reference ( - >) to tell the computer to use the size attribute of the class. As you ll remember from your C++ programming class, the pointer reference is used when indirectly working with a class member, and the dot operator is used when you are directly working with a class member.

This allows the compiler to distinguish between a class variable and local variable that have the same name. This means that the value of the size variable that is passed as an argument to the Stack member function is assigned to the size attribute, making the value available to other members of the Stack class.

You can see how the size attribute is used in the next statement. This statement does two things. First, it allocates memory for the stack by using the new operator ( new int[size] ). The new operator returns a pointer to the reserved memory location. The size is the size attribute of the class and determines the size of the array. The array is an array of integers.

Next, the pointer to the array of integers is assigned to the values attribute of the class. The values attribute is a pointer variable that is defined in the private attribute section of the Stack class.

The last statement in the Stack member function assigns a “1 to the top attribute. The value of the top attribute is the index of the top element of the stack. A “1 means that that stack doesn t have any elements. Remember from your programming class that index values are memory offsets from the start of the array. Index 0 means move 0 bytes from the start of the array. So index “1 is just a convenient way to say that the stack is empty.

We ll expand on the definition of the Stack class in the next section, but for now let s create an instance of the Stack class. The instance is declared within the main() function of this example. Three things are happening here. First, the new operator is creating an instance of the stack in memory. The new operator returns a pointer to that memory location.

Next, the statement declares a reference to the stack, which is called myStack . The reference is a pointer. The final step is to assign the pointer returned by the new operator to the reference. You then use the reference ( myStack ) as the name of the instance of the Stack class throughout the program.

 public class Stack {  private:  int size;  int top;  int* values;  public:  Stack(int size)  {  this->size = size;  values = new int[size];  top = -1;  } }; void main(){  Stack *myStack = new Stack(10); } 

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; }