CHAPTER 14

 

DATA STRUCTURES

 

 

Data structures is about how data is organized, structured, and stored in memory, as well as how this data is retrieved and manipulated. Since computer programming began, many data structures have been developed, each having its own name, properties, and characteristics. Understanding the existing data structures enables a programmer to choose the proper data structures to solve a problem. The programmer has to decide if what has to be done can be accomplished by reusing or modifying existing data structures, rather than reinventing the wheel. Let us start this way, in building a program a piece of data does not stand-alone and there is a major concern as to how the data are related to each other in a program. For each kind of relationship, there is a predefined structure, which conceptually (abstraction) or functionally (implementation), expresses how the data is stored, retrieved, or manipulated. Data can be structured as an array, struct, or a file; and these are the first data structures that programmers are exposed to. However, talking about data structures is more about major concepts such as stacks, queues, trees, hashing, sets, and graphs. The understanding of different data structures enables the programmer to solve a problem efficiently (time and space), such as applying and/or reusing the existing, tested algorithms. A large library of algorithms for data structure usage has existed for many years and still developing new algorithms, or optimizations of the existing ones, is a major topic of advanced computing. Let’s put it this way, in the field of computer science there are a series of important algorithms for solving certain problems, each having its own method of organizing data so that variables (objects) are created; this way of creating objects is known as data structures. You will observe that algorithms and data structures are very closely related and, in fact, a program is created by the combination of algorithms and data structures. In many occasions, as soon as the choice for the data structure is made, the rest of the program will easily follow. The storage for a data structures could be allocated during compile time- static data structures or during run time – dynamic data structures. The major data structures are stacks, queues, trees and graphs. However, each of these data structures can be implemented either statically, for example by arrays, or dynamically by linked lists. There are trade-offs in selecting a static data structure versus a dynamic data structure that will be discussed in detail.

 

DATA STRUCTURE IMPLEMENTATION: STATIC VERSUS DYNAMIC

 

There are two ways data structures can be implemented (built), statically and dynamically.  The memory for static data structures is of a fixed size and is allocated during the compilation time, meaning that the size of the array or structure is known in advance. In dynamic data structures, the size of the data structure grows and shrinks; meaning memory space is allocated during the execution time. In dynamic data structures, an array may be built one by one. There are advantages and disadvantages in choosing either static or dynamic data structures. It all depends on the situation and the problem. That is why the study of data structures becomes important. Again, note that the static data structures are implemented by fixed sized arrays, and dynamic data structures are built with pointers and dynamic allocation of memory.

 

 

ADVANTAGES OF STATIC DATA STRUCTURES

 

Faster: The memory for static data is allocated during the compilation time, which makes the program run faster rather than if it had to stop and allocate the required memory each time. An array index can randomly access any element of an array.

Easier to understand: It is easier to define and to use a static data structure rather than its counter part dynamic data structure.

 

 

DISADVANTAGES OF STATIC DATA STRUCTURES VERSUS DYNAMIC

 

Insufficient memory space:  Declaring an array with a fixed size leads to a situation where the size of the array is less than what we intended to use. In other words, there is insufficient memory for the program to run with all data. Another situation requesting a large consecutive block may not be granted

e.g. int x[5]; has 5 element but program needs 6.

Memory waste: Declaring an array with a large size winds up to be a memory waste. For example, if we declare an array of 100 and only a small portion are used.

Slow: There are algorithms that, done statically, would be slower than if it were done dynamically. How would you combine two lists? The solution with static arrays is to define a bigger array and copy the two arrays into the bigger array.   

Not natural: There are algorithms that are more suitable to be implemented dynamically rather than implemented statically.

 

 

ADVANTAGES OF DYNAMIC DATA STRUCTURES

 

Saving memory space: The memory space for dynamical data structures is allocated at run time; you make a request for the memory and you get the space. There is no need to reserve memory ahead of time (too little or too big). It seems as if the programmer possesses the entire memory, takes a chunk of memory, uses it, and when finished, releases it so it can be used again. This use and release of memory enables the program to run larger programs without running out of memory.

Faster: Certain algorithms run faster using dynamic data structures rather than static data structures. How do you connect two lists together? Dynamically, one operation is sufficient to connect two lists versus numerous code writing if using static data structures.

Preserve naturalness: Using dynamic data structures enables the programmer to implement the algorithms as they are rather than simulating them. For example, connecting one list to another would require fewer operations –the last element of the first list would point to the first element of the second list.

 

 

 

 

DISADVANTAGES OF DYNAMIC DATA STRUCTURES

 

Difficult to understand: In dynamic data structures, the program has to allocate and de-allocate memory by providing the keywords new and delete and appropriate syntax.  In addition, the data type must be declared properly. The knowledge of pointers is a must.

Slow: The fact that memory is allocated and de-allocated during run time makes the program slower than if the program memory was allocated during compilation time. 

 

 

MOST FREQUENT DATA STRUCTURES

 

The most frequently used data structures are stacks, queues, trees, and graphs. Other data structures such as sets, lists, and symbol tables are important as well. However, it is possible that your data structure is not one of the above frequently used ones and you may want to build a new or customized data structure.

 

 

WHAT IS A STACK?

 

A stack is a data structure in which the last data stored is accessible first, in other words, last-in first-out (LIFO). An example of a stack in real life would be placing a tray or a plate on the pile and similarly removing a tray or a plate from the pile. Therefore, insertion and deletion in stacks is done at one end of the stack, which is called the top of the stack, or simply, top. Inserting an element into the stack is called push and deleting an element from the stack is called pop.

 

 

APPLICATION OF STACKS

 

The main customer of stacks is the computer itself. The compiler uses stacks to keep track of variables; in fact, machine language uses stacks to perform operations. Functions use stacks to keep track of variables and return addresses.  The address of the recursion function will be pushed into a stack, which on return, will be popped out. The following is the list of where the stack is frequently used:

 

·         Evaluation of arithmetic expressions (implying precedence rules)

·         Conversion of infix notations to postfix or prefix notation

• Evaluation of postfix notations

·         Implementing email or voice mail as a stack (last come to retrieve first)

• Conversion of a recursion function to its non-recursive equivalent (simulation)

·         Program to balance the matches (opening and closing: windows, parenthesis, quotation)

• In Compiler design to match: braces, else with if, nested if and nested loops.

 

 

 

 

 

STACK AND SYSTEM PROGRAMMING

 

Stacks are best used in algorithms where the action needs to be delayed until certain other conditions occur. For example, to hold onto the input until some other input is reached (look ahead).  Many system-programming algorithms rely on the stack concept in operating systems (memory management, CPU scheduling) and compilers (parsers and translators). At this moment you don’t have to know all of these; I want to illustrate how important the knowledge of stacks could be.  

 

 

HOW TO IMPLEMENT A STACK

 

There are a variety of ways that we can implement a stack, which all do the same job. It all depends on the purpose of the application. Here is the list of different ways you can implement a stack:

 

1)      stack by using an array 

2)      stack by using a structure

3)      stack by using a linked list

4)      stack by using a class

5)      stack by using STL(Standard Template Libraries)

 

Similarly, other data structures such as queues and trees can be implemented as the above. Learning how to implement one will lead to the understanding of the remaining data structures. For a beginner, the array is the easiest, but at the same time could be confusing, especially when an element is removed from the stack.

 

 

IMPLEMENTING STACKS USING ARRAYS

 

For the beginners who have just learned the array, now they can implement a stack by using an array. There are certain terminologies that one should know before working with stacks. Terms used when dealing with stacks are: top, push, pop, empty, and full. The following program implements a stack of integers using an array called stack. However, the naming is conventional and it can be called any other name. In addition, we could have a stack of other types such as characters, doubles, or even pointers. You may argue that the stack is nothing more than a regular array. You are right. Arrays can be used to build any data structure by restricting the way you put the data into and get the data from (access) the array. What makes an array become a stack? An array becomes a stack when we restrict access of the array to the index of the last element put into the stack. In a stack, you are not allowed to access the middle element or anywhere else except the last element you put in. The index of the last element of a stack has a special name- top. The stack access is done only through the top. The top of a stack is initialized to a value, usually –1 or 0, indicating that the stack is empty.

 

 

  

 

 

 

 

 

 

  

 

 

 

 

OPERATIONS ON A STACK

 

What are the operations on a stack? The following is a list of what can be done to a stack:

·         push – insert an element into a stack

·         pop - remove an element from a stack

·         full – to check if stack is full so no more insertion can be done

·         empty – to check if the stack is empty so no more pops can be done.

 

For each of the above stack operations, we are going to build a function to perform the task. However, we are going to initialize the stack by setting the top to either 0 or –1. Just remember, the above names, such as push, pop, and top, are not reserved words. The words push, pop, and top are simply used by convention since they easily identify the tasks of the stack operations. One more thing, all the operations are done through the top of the stack. 

 

 

INITIALIZING THE STACK

 

How do you identify that the stack is empty? If you have not yet pushed any element into the stack, the stack is empty. We can set the top to –1, indicating that the stack is empty and top will be incremented as soon as we need to push an element into the stack. Since the array in C++ starts from 0, this convention is a good one. An alternative to initializing the stack is to set the top to zero, making the stack ready for a push. Which stack initialization is better, top to zero or –1? Setting top to zero makes the empty test natural, while setting the top to –1 makes the pop natural by accessing the top element instead of subtracting top by one first.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

 

 

STACK PUSH

How does the stack push work? The item is inserted into the stack array by its top index. After the assignment of an item into the stack, the top index is incremented by one.  In order to push an item into the stack, it is necessary to make sure that there is room in the stack, that the stack is not full. The check has to be done before the item is pushed into the stack. Again, since top is initialized to 0 and index 0 is the first element of the array, top is incremented after the insertion of the item into the stack. The following program will illustrate how an item is inserted into a stack and check to make sure there is room before the insertion is done. For simplicity, the stack push is shown as a main program as a unit by itself, instead of a function or as part of a class, which will be examined at later time.

 

 

 

 

 

 

 

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

STACK POP

The only element that can be removed from the stack is the top element, which will be assigned to a variable for further use. However, the top should be decremented by one since the strategy to initialize the empty stack is 0 as an alternative to –1.You can realize that popping an element is the opposite of pushing an element. One problem for beginners in regards to pop is that the deleted element is still in the array, only the top has moved down so that it would not be accessible. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

STACK EMPTY

It is important to check whether a stack is empty or not. If the stack is empty, then no popping from the stack should take place and an error message should be displayed or an exception handler should take charge. Since the stack is initialized to zero, the top of stack is checked against zero.

 

 

 

 

 

 

 

 

 

 

STACK FULL

To check whether the stack is full is important so that no insertion will take place. If someone tries to insert an item when the stack is full, there should be an error message to alert or an exception handler should activate. The top of the stack is compared to the maximum size of the array allocated for the stack. In this example, the maximum size of the stack is defined as a constant identifier, which is initialized at the beginning of the program.

 

 

 

 

 

 

 

 

 

 

 

 

SIMPLE STACK MENU: USING ARRAYS AND FUNCTIONS

The following program puts operations of stacks together so that each function is tested separately. A main program with a menu will call to each function: push( ), pop( ), isfull( ), and isempty( ).  An array is used as a static data structure to implement the stack. For efficiency, the stack and its top variable are not declared as external variables, instead they are declared as local variables within the main program and are passed through the functions by reference so that the changes on them will impact back. The function: void push(int mystack[],int &mytop,int item); takes three arguments, stack, top, and item to be pushed with no return value. The function: int pop(int mystack[], int &mytop); takes two arguments and returns the item on top of the stack. The function: int isfull(top); takes two arguments- top and MAXSIZESTACK as value parameters to determine if the stack is at its maximum size. The function isempty(int mytop); takes one argument -top to determine whether the stack is empty. Both functions isfull( ) and  isempty( ) could return a boolean value (true/false)  instead of an integer, for instance, bool isfull(top). In the program, the variables stack and top are preceded with the word my to reemphasized that these names are not reserved words, they are your words and can be any legal identifier name. For simplicity, the variable names used in the function (formal parameters) and names used in the calling program (actual names) are kept the same. 

 

 

#include <iostream>

using namespace std;

void push(int mystack[],int &mytop,int item){

            mystack[mytop]=item;

            mytop=mytop+1;  }//PUSH

int pop(int mystack[],int &mytop){

            mytop=mytop-1;

            int item=mystack[mytop];

            return item;  }//POP

int isempty(int mytop){

             if(mytop==0) return 1;

             else return 0; }// ISEMPTY

int isfull(int mytop,const int MAXSTACKSIZE){

             if(mytop==MAXSTACKSIZE) return 1;

             else return 0; }// ISFULL

int main(){

            const int MAXSTACKSIZE=5;

            int mystack[MAXSTACKSIZE]; int mytop,x, option;

            mytop=0; // STACK TOP INITILIZATION

            do{ cout<<"SELECT ONE OF THE FOLLOWING OPTIONS:"<<endl;

                   cout<<"1-PUSH 2-POP 3-ISEMPTY 4-ISFULL 5-QUIT: ";

                   cin>>option;

                   switch(option){

                        case 1: if (isfull(mytop,MAXSTACKSIZE))

                                             cout<<"YOU CAN'T PUSH"<<endl;

                                    else{ cout<<"ENTER THE NUMBER THAT WILL BE PUSHED: ";

                                             cin>>x;

                                             push(mystack,mytop,x);}//ELSE

                                             break;

                        case 2: if(isempty(mytop))

                                              cout<<"YOU CAN'T POP"<<endl;

                                    else{ cout<<"THE NUMBER POPPED IS: "<<pop(mystack,mytop);

                                             cout<<endl;}//ELSE

                                             break;

                        case 3: if(isempty(mytop)==1)

                                             cout<<"STACK EMPTY."<<endl;

                                    else cout<<"STACK IS NOT EMPTY."<<endl;

                                             break;

                        case 4: if(isfull(mytop,MAXSTACKSIZE)==1)

                                             cout<<"STACK FULL."<<endl;

                                    else cout<<"STACK IS NOT FULL."<<endl;

                                             break;

                        case 5: cout<<"THANK YOU FOR USING OUR MENU!"<<endl;

                                    break;

                                    default: cout<<"ENTER CORRECT OPTIONS"<<endl;    } // SWITCH

                        } while (option !=5);

                         return 0;

}//MAIN