Circular Queue

Linear queues using arrays have certain drawbacks listed as follows:

1. The linear queue is of a fixed size.

2. Poor utilization of memory. (Ex: using only 20 but declaring max size 100)

3. Array implementation of linear queues leads to the Queue_Full state even though the queue is not actually full.

A more efficient queue representation is obtained by implementing the array as circular. Elements are added to queue until the end of the array is reached and next element is stored in the first slot of the array if it is empty. The empty slots are filled with new incoming elements even if rear=n-1 (size of array is n). The queue is said to be full only when there are n elements in the queue.

The functions to add and delete elements are:

 

void Cqueue :: Add(int Element)

{

if(!Full())

Rear = (Rear + 1) % Max;

Queue[Rear] = Element;

Size++;

}

 

int Cqueue :: Delete()

{

if(!Empty())

Front = (Front + 1) % Max;

Size--;

return(Queue[Front]);

}

 

Advantages of Using Circular Queues

1. Data shifting is avoided as the front and rear are modified by using the mod() function. The mod() operation wraps the queue back to its beginning.

2. If the number of elements to be stored in the queue is fixed, the circular queue is advantageous.

3. Many practical applications such as printer queue, priority queue, and simulations use the circular queue.

Queues

A queue is a special type of data structure that performs insertions at one end called the rear and deletions at the other end called the front.

A queue is a common example of a linear list or an ordered list where data can be inserted at and deleted from different ends.

A queue is a first in first out (FIFO) or last in last out (LILO) structure.

Queues are one of the most common data processing structures frequently used in most system software such as operating systems, network and database implementations, and other areas. Queues are very useful in time-sharing and distributed computer systems where many widely distributed users share the system simultaneously.

Queue as Abstract Data Type (ADT)

To realize a queue as an abstract data type (ADT), a suitable data structure for storing the elements in the queue and the functions operating on it are needed.

A minimal set of operations on a queue is as follows:

1. create()—creates an empty queue, Q

2. add(i,Q)—adds the element i to the rear end of the queue, Q and returns the new queue

3. delete(Q)—takes out an element from the front end of the queue and returns the resulting queue

4. getFront(Q)—returns the element that is at the front position of the queue

5. Is_Empty(Q)—returns true if the queue is empty; otherwise returns false.

Since a queue is a linear data structure, it can be implemented using either arrays or linked lists.

Implementation of Queue using Arrays

An array is not a suitable data structure for frequent insertion and deletion of data elements. Another drawback of arrays is that they use static memory allocation, and so they can store only a fixed number of elements.

The implementations of the various operations on the queue using arrays are:

Create

This operation should create an empty queue. Here max is the maximum initial size that is defined.

#define max 50

int Queue[max];

int Front = Rear = −1;

The two variables Front and Rear are initialized to represent an empty queue. The condition Front = Rear indicates an empty queue. As our array index ranges between 0 and (max − 1), the front and rear are initialized to -1.

Is_Empty

This operation checks whether the queue is empty or not. It is done by comparing the values of Front and Rear. If Front = Rear, then Is_Empty returns true, else returns false.

bool Is_Empty()

{

if(Front == Rear)

return 1;

else

return 0;

}

Is_Full

Before insertion of element, the queue must be checked for the Queue_Full state. When Rear points to the last location of the array, it indicates that the queue is full and there is no space to accommodate any more elements.

bool Is_Full()

{

if(Rear == max − 1)

return 1;

else

return 0;

}

Add

This operation adds an element in the queue if it is not full. As Rear points to the last element of the queue, the new element is added at the (rear + 1)^th location.

void Add(int Element)

{

if(Is_Full())

cout << “Error, Queue is full”;

else

Queue[++Rear] = Element;

}

Delete

This operation deletes an element from the front of the queue and sets Front to point to the next element. First Front has to be incremented then element is removed.

int Delete()

{

if(Is_Empty())

cout << “Sorry, queue is Empty”;

else

return(Queue[++Front]);

}

Code: Implementation of Queue using Array

class queue

{

private:

int Rear, Front;

int Queue[50];

int max;

int Size;

public:

queue()

{

Size = 0; max = 50;

Rear = Front = −1 ;

}

int Is_Empty();

int Is_Full();

void Add(int Element);

int Delete();

};

 

int queue :: Is_Empty()

{

if(Front == Rear)

return 1;

else

return 0;

}

 

int queue :: Is_Full()

{

if(Rear == max − 1)

return 1;

else

return 0;

}

 

void queue :: Add(int Element)

{

if(!Is_Full())

Queue[++Rear] = Element;

Size++;

}

 

int queue :: Delete()

{

if(!Is_Empty())

{

Size−−;

return(Queue[++Front]);

}

}

 

void main(void)

{

queue Q;

Q.Add(11);

Q.Add(12);

Q.Add(13);

cout << Q.Delete() << endl;

Q.Add(14);

cout << Q.Delete() << endl;

cout << Q.Delete() << endl;

cout << Q.Delete() << endl;

cout << Q.Delete() << endl;

Q.Add(15);

Q.Add(16);

cout << Q.Delete() << endl;

}

Simulating recursion using stack (Eliminating recursion)

If a programming language does not support recursion or one needs a non-recursive code, then a recursive code can be translated to a non-recursive one. Once a recursive function is written and is verified for its correctness, one can remove recursion for efficiency.

Eliminating recursion can be done using the following rules:

1. At the beginning of the recursive function, a code is inserted to create an empty stack. This stack is to be used to hold the values of parameters, the local variables, the function value, and the return address for each recursive call.

2. The jump label is attached to the first executable statement (say label_1). Now, replace each recursive call by a set of instructions that perform the following:

            (a) Push the values of all parameters and local variables on the stack.

(b) Create the ith new label, label_i and store i in the stack. The value i of this label will be used to compute the return address.

(c) Evaluate the arguments of this call, which may be part of the expression. Assign these values to the appropriate formal parameters.

(d) Insert an unconditional branch to the beginning of the function.

(e) Attach the label created in step 2(b) to the statement immediately following the

unconditional branch.

3. Once all the recursive calls have been eliminated, replace all the return statements using the following steps:

(a) If the stack is empty, then execute a normal return.

(b) Otherwise, take the current value of all the output parameters (explicitly or implicitly understood to be of type output or input) and assign these values to the corresponding variables that are on top of the stack.

(c) Now, insert a code that removes the index of the return address from the stack if any has been placed there. Assign this address to some unused variable.

(d) Remove the values of all local variables and parameters from the stack and assign them to their corresponding variables.

(e) If this is a function, insert instructions to evaluate the expression immediately following return() and store the result on the top of the stack.

(f) Use the index of the label of the return address to execute a branch to that label.

If all these rules are followed carefully, one can convert recursion to an iterative code.

Iteration versus Recursion

Recursion is a top–down approach of problem solving. It divides the problem into pieces or selects one key step, postponing the rest.

On the other hand, iteration is more of a bottom–up approach. It begins with what is known and from this constructs the solution step by step.

It is hard to say that the non-recursive version is better than the recursive one or vice versa. Few languages do not support writing recursive code. The non-recursive version is more efficient as the overhead of parameter passing in most compilers is heavy.

Demerits of Recursive Algorithms

Although recursive algorithms have many merits, they have their limitations. They are:

1. Many programming languages do not support recursion; hence, recursive mathematical function is to be implemented using iterative methods.

2. Even though mathematical functions can be easily implemented using recursion, it is always at the cost of additional execution time and memory space.

3. A recursive function can be called from within or outside itself, and to ensure proper functioning, it has to save the return addresses in some order so that the return to the proper location will yield the desired result when the return to a calling statement is made.

Demerits of Iterative Methods

Although the iterative method has various merits, it has its own limitations such as:

1. Iterative code is not readable and hence not easy to understand.

2. In iterative techniques, looping of statements is necessary and needs a complex logic.

3. The iterations may result in a lengthy code.

Recursive Functions

Any function written using an iterative code can be converted into a recursive code. This does not guarantee that the resulting program will be easy to understand but often, the program results in a compact and readable code.

Recursive functions are often simple and elegant, and their correctness can be easily verified.

Many mathematical functions are defined recursively, and their translation into a programming language is often easy.

If used carelessly, recursion can sometimes result in an inefficient function.

Algorithms that are by nature recursive, such as the factorial, Fibonacci, or power, can be implemented as either iterative or recursive code. However, recursive functions are generally smaller and more efficient than their looping equivalents.

Recursion is also useful when the data structure that the algorithm is to operate on is recursively defined. Examples of such data structures are linked lists and trees.

Recursion is valuable is when we use ‘divide and conquer’ and ‘backtracking’ as algorithm design paradigms.

Writing Recursive Code

The general approach to writing a recursive function is

1. Write the function header  to make sure what the function will do and how it will be called.

2. Decompose the problem into sub-problems. Identify clearly the non-recursive case of the problem (end case or base case).

3. Write recursive calls to solve those sub-problems whose form is similar to that of the original problem.

4. Write the code to combine, enhance, or modify the results of the recursive call(s).

5. Write the end condition(s) to handle any situations that are not handled properly by the recursive portion of the program.

Correctness of recursion

The following five conditions must hold true for recursion to work.

1. A recursive function must have at least one end condition and one recursive case.

2. The test for the end condition has to execute prior to the recursive call.

3. The problem must be broken down in such a way that the recursive call is closer to the base case. The base case is reached in a finite number of recursive calls.

4. The recursive call must not skip over the base case.

5. Verify that the non-recursive code of the function is operating correctly.

Recursion

In C/C++, a function calling itself is called a recursive function.

Recursion is a technique that allows us to break down a problem into one or more sub-problems that are similar in form to the original problem.

A program becomes compact and readable with recursive functions. Recursion is extremely powerful as it enables the programmer to express complex processes easily. Recursive programs are used in a variety of applications ranging from calculating the factorial of a number to playing complex games against human intelligence.

A recurrence is a well-defined mathematical function where the function being defined is applied within its own definition.

The factorial we defined as n! = n \ (n - 1)! is an example of recurrence with 1! = 1 as the end condition.

Use of stack in recursion

The stack is a special area of memory where temporary variables are stored. It acts on the LIFO principle.

The following points are to be noted when recursion is used:

1. The number of times a function calls itself is known as the recursive depth of that function.

2. Each time the function calls itself, it stores one or more variables on the stack. Since stacks hold a limited amount of memory, the functions with a high recursive depth may crash because of non-availability of memory. Such a situation is known as stack overflow.

3. Recursive functions should have a terminating (or end) condition.

4. All recursive functions go through two distinct phases. The first phase, winding, occurs when the function calls itself and pushes values onto the stack. The second phase, unwinding, occurs when the function pops values from the stack, usually after the end condition.

 Variants of Recursion

The recursive functions based on characterization are categorized as

1. Direct, 2. Indirect, 3. Linear, 4.Tree, and 5.Tail recursions.

1. Direct recursion

Recursion is when a function calls itself. Recursion is said to be direct when a function calls itself directly.

int Power(int x, int y)

{

if(y == 1)

return x;

else

return (x * Power(x, y - 1));

}

2. Indirect recursion

A function is said to be indirectly recursive if it calls another function, which in turn calls it.

int Fact(int n)

{

if(n <= 1)

return 1;

else

return (n * Dummy(n - 1));

}

void Dummy(int n)

{

Fact(n);

}

3. Linear Recursion

A recursive function is said to be linearly recursive when no pending operation involves another recursive call.

4. Tree Recursion

In a recursive function, if there is another recursive call in the set of operations to be completed after the recursion is over, this is called a tree recursion.

 5. Tail recursion

A recursive function is said to be tail recursive if there are no pending operations to be performed on return from a recursive call. Tail recursion is also used to return the value of the last recursive call as the value of the function. Tail recursion is advantageous as the amount of information that must be stored during computation is independent of the number of recursive calls.

Applications of stack

The stack data structure is used in a wide range of applications such as

1. Converting infix expression to postfix and prefix expressions

2. Evaluating the postfix expression

3. Checking well-formed (nested) parenthesis

4. Reversing a string

5. Processing function calls

6. Parsing (analyse the structure) of computer programs

7. Simulating recursion

8. In computations such as decimal to binary conversion

9. In backtracking algorithms (often used in optimizations and in games)

1. EXPRESSION EVALUATI ON AND CONVERSION

The most frequent application of stacks is in the evaluation of arithmetic expressions. An arithmetic expression is made of operands, operators, and delimiters.

Operator Precedence:

1. Exponentiation (^), Unary (+), Unary (-), and not (~)

2. Multiplication (\) and division (/)

3. Addition (+) and subtraction (-)

4. Relational operators  (<, <= , =,  ≥, >)

5. Logical AND

6. Logical OR

The order of evaluation, from left to right or right to left, is called associativity. Exponentiation is right associative and all other operators are left associative. In the parenthesized expressions, the innermost parenthesized expression is evaluated first.

Let us consider the expression

X = A/B ^ C + D X E - A X C

By using priorities and associativity rules, the expression X is rewritten as

X = A/(B ^ C) + (D X E) - (A X C)

The Polish Mathematician Han Lukasiewicz suggested a notation called Polish notation, which gives two alternatives to represent an arithmetic expression, namely the postfix and prefix notations.

The advantage is that a parenthesis is not required while writing expressions in Polish notation. The order in which the operations are to be performed is determined by the positions of the operators and operands in the expression.

The conventional way of writing the expression is called infix, because the binary operators occur between the operands, and unary operators precede their operand.

For example, the expression ((A + B) X C)/D is an infix expression. In postfix notation, the operator is written after its operands, whereas in prefix notation, the operator precedes its operands.

The postfix and prefix expressions possess many advantages as follows:

1. The need for parenthesis as in an infix expression is overcome in postfix and prefix notations.

2. The priority of operators is no longer relevant.

3. The order of evaluation depends on the position of the operator but not on priority and associativity.

4. The expression evaluation process is much simpler than attempting a direct evaluation from the infix notation.

Postfix Expression Evaluation

The postfix expression may be evaluated by making a left-to-right scan, stacking operands, and evaluating operators using the correct number from the stack as operands and again placing the result onto the stack. This process continues till the stack is not empty or on occurrence of the character #, which denotes the end of the expression.

Algorithm for evaluation of postfix expression

1. Let E denote the postfix expression

2. Let Stack denote the stack data structure to be used & let Top = −1

3. while(1) do

begin

X = get_next_token(E) // Token is an operator, operand, or delimiter

if(X = #) {end of expression}

then return

if(X is an operand)

then push(X) onto Stack

else {X is operator}

begin

OP1 = pop() from Stack

OP2 = pop() from Stack

Tmp = evaluate(OP1, X, OP2)

push(Tmp) on Stack

end

end

4. stop

Example:

Let us consider an example postfix expression E = AB + C X#.

Scan this expression from left to right, character by character. The following push and pop operations are performed using stack to evaluate the given postfix expression.

An expression in one form can be converted to the other two forms.

1. Infix expression to postfix expression

2. Infix expression to prefix expression

3. Prefix expression to infix expression

4. Prefix expression to postfix expression

5. Postfix expression to infix expression

6. Postfix expression to prefix expression

II. Processing of function calls

One natural application of stacks in computer programming is the processing of function calls and their terminations.

The program must remember the place where the call was made so that it can return there after the function is complete.

For example let ABC, PQR, XYZ are three functions along with one main function. The main function invokes ABC, ABC invoke PQR, and PQR in turn invoke XYZ.

main function is the first to start work, but it is the last to be finished. 

Use of stack for processing of function calls

III. Reversing a String with a Stack

The LIFO (Last In First Out) property of the stack access guarantees the reversal.

Suppose the sequence ABCDEF is to be reversed. With a stack, simply scan the sequence, pushing each element onto the stack until the end of the sequence is reached.

Then stack is popped repeatedly, with each popped element sent to the output, until the stack is empty