Definition of Queues

A queue is defined as a special type of data structure where elements are inserted from one end and elements are deleted from other end.

The end from where the elements are inserted is called rear end (r) and the end from where elements are deleted called front end (f). In a queue always elements are inserted from the rear end and elements are deleted from the front end.

Queue is a linear list for which all insertions are made at the end of the list; all deletions (and usually all accesses) are made at the other end. So queue is also called First in First out (FIFO) data.

Different types of queues

1. Ordinary queue
2. Double ended queue
3. Circular queue
4. Priority queue

1. Ordinary queue

 

This queue operates on the first come first serve basis. Items will be inserted from one end and they are deleted at the other end in the same order in which they are inserted. A queue can be represented by using an array by using an array as shown in the figure.


The operations that can be performed on these queues are

• Insert an item at the rear end
• Delete an item from the front end
• Display the contents of the queue

Disadvantage of Ordinary queue

In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1, so item cannot be inserted into the queue.

2. Double ended queue (Deque)

Another type of queue called double ended queue also called Deque. Deque is a special type of data structure in which insertions and deletions will be done either at the front end or at the rear end of the queue. The operations can be performed on Deques are

• Insert an item from front end
• Insert an item from rear end
• Delete an item from front end
• Delete and item from rear end
• Display the contents of queue

3. Circular queue

In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1 item cannot be inserted. But this disadvantage is overcome using circular queue. In circular queue an item can be published circularly. This can be achieved using the statement r = (r+1)%QUEUE_SIZE


The operations can be performed on circular queue are.

• Insert an item from rear end
• Delete an item from front end
• Display queue contents

4. Priority queue

Such a queue where a job is processed based on the priority is called a priority queue

Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

Definition of Stack

Stack is defined as a special type of data structure where items are inserted from one end called top of stack and items are deleted from the same end.

          Here, the last item inserted will be on top of stack. Since deletion is done from the same end, Last item is inserted is the First item to be deleted out from the stack and so, stack is also called Last In First Out (LIFO) data structure.

The various operations that can be performed on stacks are

         i.            Insert an item into the stack
       ii.            Delete an item from the stack
      iii.            Display the contents of the stack

·  Insert or push operation: Inserting an element in the stack is called push operation. This can be achieved by first increment top by 1 and then insert an item as shown below;
                top = top+1;
                s[top] = item;
These two statements can also be written as s[++top]= item
                             
When the stack is full the value of top will be [STACK SIZE -1] and it is not possible to insert any new item in the stack. This situation is called stack overflow.

·  Delete or Pop operation: Deleting the stack called pop operation. This can be achieved by first accessing the top element s[top] and then decremented top by one as shown below.

              Item = s[top--];

Each time, the item is deleted, top is decremented and finally, when the stack is empty the top will be -1. When the stack is empty, it is not possible to delete any item and this situation is called underflow of stack.

·      Display operation: Displaying the items of the stack is called display operation.

Applications of Stack:- A stack is very useful in situations when data have to be stored and then retrieved in the reverse order. Some applications of stack are listed below.
         i.            Function calls
       ii.            Large number Arithmetic
      iii.            Evaluation of arithmetic expressions

You Might also view the following Related Posts

• Fundamental of data structures
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

For more other Posts: Click Here

Fundamental of data structures

What is data Structure?

A data Structure is the organization of data in computers memory or in a file.

Some examples of data structures are: array, stack, queue, link list, binary tree hash table, heap and graph. Data structures are often used to build databases. Typically, data structures are manipulated using various algorithms.

Based on the concept of Abstract data types (ADT), we define data structure by the following three components.

1.       Operations: Specifications of external appearance of data structure.
2.     Storage Structures: Organizations of data implemented in lower-level data structures.
3.       Algorithms: Description on how to manipulate information in the storage structures to obtain the results defined for operations.

Implementation of Data Structure

There are three levels of implementation of data structure which are:
1. The Abstract Level: The abstract (or logical) level is the specifications of the data structure the “What” but not “how”. At this level. The user or data structure designer is free think outside the bounds of anyone programming language.

2. Application Level: At the application or user level, the user is modeling real-life data in a specific context.

3.  Implementation Level: The implementation level is where the model becomes compatible, executable code.

Abstract data types

                The data structure can only be accessed with defined operations. This set of operations is called interface and abstract data type is exported by the entity. An entity with the properties just described is called an abstract data type (ADT).

Properties of an abstract data type

Abstract data type is characterized by the following Properties.
1.       It exports a type.
2.       It exports a set of operations. This set is called interface.
3.       Operations of the interface are the one and only access mechanism to the type’s data structure.
4.       Axioms and preconditions define the application domain of type.

Parts of ADT description

1.       Data: This part describes the structure of the data used in the ADT in an informal way.
2.       Operations: This part describes valid operations for this ADT; hence, it describes its interface. We use special operation constructor to describe the actions which are to be performed once an entity of this ADT is created and destructed to describe the actions which are to be performed once an entity is destroyed.

You Might also view the following Related Posts

• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

For more other Posts: Click Here

Programming Language Definition

Programming Language Definition: A sequence of instructions that a computer can interpret and execute to complete task is called computer program. The language which is used to develop a computer program is called programming language. There are two types of programming language which are procedure oriented programming language and object oriented programming language.
1.       Procedure Oriented programming:Conventional programming, using high level languages such as COBOL, FORTAN and C is commonly known as procedure oriented programming (POP). In the procedure oriented approach, the problem is viewed as a sequence of things to be done such as reading, calculating and printing. Procedure oriented programming basically consists of writing a list of instructions (or actions) for the computer to flow and organizing these instructions into groups known as functions.

Characteristics of Procedure Oriented Programming
i)        Emphasis is on doing things (algorithms)
ii)       Large Programs are divided into smaller Programs Known as functions.
iii)     Most of the functions share global data
iv)     Data move openly around the system from function to function.
v)      Functions transform data from one to another.
vi)     Employs top-down approach in program design.

Drawbacks of Procedure Oriented Programming
i)        In large program it is very difficult to identify what data is used by which function. In case we need to revise an external data structure, we also need to revise all functions that access the data. This provides an Opportunity for bugs to creep in.
ii)       With the procedural approach is that it does not model real world problems very well. This is because functions are action oriented and do not really corresponding to the elements of the problem.

2.       Object-oriented Programming: Object oriented programming treats data as a critical element in the program development and does not allow it to flow freely around the system. It ties data more closely to the functions that operate on it, and protects it from accidental modification from outside functions. OOP allows decomposition of a problem into a number of entities called objects and then builds data and functions around these objects.

Characteristics of Object-Oriented programming
i)        Emphasis is on data rather than procedure.
ii)       Programs are divided into what are known as objects.
iii)     Data structures are designed such that they characterize the objects.
iv)     Functions that operate on the data of an object are tied together on the data structure.
v)      Data is hidden and cannot be accessed by external functions.
vi)     Objects may communicate with each other through functions.
vii)   New data and functions can be easily added whenever necessary. Follows bottom up approach is program design.

Benefits of Object Oriented Programming
i)        Through inheritance we can eliminate redundant code and extend the use of existing classes.
ii)       We can build programs from the standard working modules that communicate with one another, rather than having to start writing the code from scratch. This leads to saving of development time and higher productivity.
iii)     The principle of data hiding helps the programmer to build secure programs that cannot be invaded by code in other parts of the program.

Some terms used in Object Oriented Programming

Ø  Objects: Objects are basic run-time entities in an object oriented system.
Ø  Classes: A class is a collection of objects of similar type.
Ø  Data Abstraction and Encapsulation: The wrapping up of data and functions into a single unit is known as encapsulation.
Abstraction refers to the act of representing essential features to the act of representing essential features without including the background or explanations.
Ø  Inheritance: Inheritance is the process by which objects of one class acquire the properties of objects of another class.
Ø  Polymorphism: Polymorphism is another important OOP concept. Polymorphism, a Greek term means the ability to take more than one form. The operation may exhibit different instances the behavior depends upon the types of data is the operation.
Ø  Dynamic Binding: Binding refers to the linking of a procedure call to the code to be executed in response to the call. Dynamic binding (also known as late binding) means that the code associated with a given procedure call is not known until the time of the call at run time.
Ø  Message passing: A message for an object is a request for execution of a procedure and therefore will invoke a function (procedure) in the receiving object that generates the desired result.
 

Network Reference Models (Network Architectures)

The two most important reference modes are listed below

i) The OSI reference model and

ii) The TCP/IP reference model




i)        The OSI reference model

An ISO standard that covers all aspects of networks communications is the Open System Interconnection (OSI) model. An open system is a model that allows any two different systems to communicate regardless of their underlying architecture. Vendor specific protocols close off communication between different systems without requiring changes to the logic of the underlying hardware and software. An OSI model is a layered framework for the design of network systems that allows for communication across all types of computer systems. The purpose of each layer is to offer certain services to the higher layers. Layer n on one machine (source) carries on a conversation with layer n on another machine (destination).  The rules and conventions used in this conversation are collectively known as the layer n protocol. Basically, a protocol is an agreement between the two machines as how communication link should be established, maintained and released.
The users of computer network are located over a wide physical range i.e. all over the world. Therefore, to ensure that nationwide and worldwide data communication systems can be developed and are compatible to each other and international group of standards has been developed. These standards will fit into a framework which has been developed by the International Organization of Standardization (ISO). The OSI model is not a protocol rather it is a model of underlying designing a network architecture which is flexible, robust and interoperable.

ii)      The TCP/IP reference model

The TCP/IP reference model which was used earlier by ARPANET and then it is being used in the Internet. TCP/IP is a short form of transmission control protocol and interned protocol. ARPANET was a research network sponsored by the US department of Defense. It included many universities and government installations using the leased telephone lines. Later on, the satellites and radio networks were added to it. This inclusion could not be handled by the existing protocols at that time. So, new reference architecture was needed. This new architecture is known as TCP/IP reference model due to the use of the two protocols TCP and IP. While designing the new model, certain goals were to be achieved. Some of them were as follows:
i)           First design goal was to have an ability to connect multiple networks together in a seamless way.
ii)          Another goal was the network should be able to survive loss of subnet hardware with existing conversation not being broken.
iii)        Next, a flexible architecture was needed to deal successfully with the divergent requirements of various applications.

You Might also view the following Related Posts

• Networking Fundamental
• Network Topology
• Network Functions
• Network Reference Models (Network Architectures)
• Internet Security & IP Security (IPSec)
• Secure Socket Layer (SSL)

For more Posts: Click Here

Network Functions

Following are some of the important functions that a network needs to perform

1.       Switching
2.       Routing
3.       Flow control
4.       Speed
5.       Security
6.       Backup
7.       Failure monitoring
8.       Traffic monitoring
9.       Accountability
10.   Internetworking
11.   Network management

1.       Switching
Switching is defined as the ability of a network to connect different channels attached to each node to each other. This is essential for moving the traffic from incoming channel to the desired outgoing channels.

2.       Routing
Routing is defined as the ability of the network to select a path. The routing can be of different types, namely the fixed routing or alternative routing. The routing can also be classified as static routing or dynamic routing.

3.       Flow control
Flow control is the control over the rate of traffic. It is necessary in order to reduce the network congestion.

4.       Speed
The speed of different devices is different. Also the codes used by different devices are different from each other. In the digital networks, we have to allow the communication between all such devices.

5.       Security
Network security is defined as the ability of a network to disallow any unauthorized access to the network and the data travelling over it. We have to take the measures such as using passwords of use of data encryption and physical security.

6.       Backup
It is defined as the ability of a network to react to the component failures. Back up also includes sending to indicate failures or to route the traffic via some other path to avoid a failed component.

7.       Failure monitoring
It is the ability of the network to keep track of faulty and working components.

8.       Traffic monitoring
It is defined as the ability of the network to keep track of traffic levels. It is useful for the network design.

9.       Accountability
It is the ability of the network to keep a track of who is actually using the network. This is possible through the billing and charge back process. It gives us an understanding of the various users of a network. This is different from the traffic monitoring.

10.   Internetworking
When two or more networks are connected they are called internetwork of internet. Individual networks are joined into internetworks by the internetworking devices like bridges, routers and gateways.
The term internet (lower case i) is a generic term used to mean and interconnection of networks and Internet (upper case I) is the name of specific worldwide network. A common form of internet is a collection of LANs connected by a WAN. Internetworking is defined as performing the function needed for communicating with other networks in as internetwork.
The internetworking includes the following functions:
i)                    To provide routes for traffic.
ii)                   To allocate resources such as buffers and links

11.   Network management
The network management is not a one single function. It is instead a combination of many functions. It includes the following functions:
i)        To maintain the user’s list.
ii)       To maintain the addresses of the devices.
iii)     To keep an eye on changes in schedules of network.
iv)     Fault isolation.
Some of the network functions are carried out at each node and the others are needed to be carried our only by the first and the last node.

You Might also view the following Related Posts

• Networking Fundamental
• Network Topology
• Network Functions
• Network Reference Models (Network Architectures)
• Internet Security & IP Security (IPSec)
• Secure Socket Layer (SSL)

For more Posts: Click Here

Network Topology

Network topology describes the layout or appearance of a network that is, how the computers, cables and other components within a data communication network are interconnected, both physically and logically. The physical topology describes the way in which a network is physically laid out, and the logical topology describes how data actually flow through the network. In data communication network, two or more devices are connected to from a link whereas two or more links from a topology. The topology of a network is the geometric representation of the relationship of all the links connecting the devices.

Types of Network Topology:

1.      Bus Topology: A bus topology is a multipoint data communication circuit that makes it relatively simple to control data flow between and among the computers because this configuration allows all stations to receive every transmission over the network. 

          The bus topology is usually used when a network installation is small, simple or temporary. On a typical bus network, the cable is just one or more wires, with no active electronics to amplify the signal or pass it along from computer to computer. 

         The speed of the bus topology is slow because only one computer can send a message at a time. A computer must wait until the bus is free before it can transmit. The bus topology requires a proper termination at both ends of the cable. Since, the bus is passive topology; the electrical signal from a transmitting computer is free to travel the entire length of the cable. Without termination when the signal reaches the end of the cable, it returns back and travels break up the cable. 

Advantages of Bus Topology

i) The bus topology is easy to understand, install and use for small networks.

ii) The cabling cost is less as the bus topology requires the least amount of cable to connect the computers.

iii) The bus topology is easy to expand by joining two cables with a BNC barrel connector.

iv) In the expansion of bus topology, repeaters can be used to boost the signal and increase the distance.

Drawbacks of Bus Topology

i) Heavy network traffic slows down the bus speed. In bus topology, only one computer can transmit and         others have to wait till their turn comes and there is no co-ordination between computers for reservation of transmitting time slot. 

ii) The BNC connectors used to expansion of the bus attenuates the signal considerably. 

iii) A cable breaks or loses BNC connector causes reflection and brings down the whole network causing all network activity to stop.

2. Ring Topology: In a ring topology, each computer is connected to the next computer, with the last one connected to the first. Rings are used in high-performance networks where large bandwidth is essential, e.g. time attractive features such as video and audio. In other words, a ring topology is a multipoint data communication network where all stations are interconnected is series to form a closed loop or circle. A ring topology is sometimes called a loop. Each station is the loop is joined by point-to-point links to two other stations. 

        The messages flow around the ring in one direction. There is no termination because there is no end to the ring. Some ring networks do token passing. A short message called a token is passed around the ring until a computer wishes to send information to another computer. That computer modifies the token, adds an electronic address and data and sends it around the ring. Each computer is sequence receives the token and the information and passes them to the next computer until either the electronic address matches the address of a computer or the token returns to its origin. The receiving computer returns a message to the originator indicating that message has been received. 

Advantages of Ring Topology

i) No one computer can monopolize the network because every computer is given equal access to the token.

ii) The fair sharing of the network allows the network continue function in a useful, if slower, manner rather than fail once capacity is exceeded as more users are added.

Drawbacks of Ring Topology

i) Failure of one computer on the ring can affect the whole network.

ii) It is difficult to troubleshoot the ring.

iii) Adding or removing the computers disturbs the network activity.

3. Star Topology: In star topology, all the cables run from the computers to a central location where they are all connected by a device called a hub. Stars are used to concentrated networks, where the endpoints are directly reachable from a central location when network expansion is expressed and when the greater reliability of a star topology is required. 

           Each computer on a star network communicates with a central hub that re-sends the message either to all the computers is a broadcast star network or only to the destination computer in a switched star network. The hub is a broadcast star network can be active or passive. An active hub generates the electrical signal and sends it to all the computers connected to it. This type of hub is usually called a multiport repeater. Active hubs require external power supply. A passive hub is a wiring panel or punch down block which acts as a connection point. It does not amplify or regenerate the signal. Passive hubs do not require electrical power supply. Several types of cables can be used to implement a star network. 

Drawbacks of Star Topology

i) If the central hub fails, the whole network fails to operate.

ii) Many star networks require a device at the central point to rebroadcast or switch the network traffic.

iii) The cabling cost is more since cables must be pulled from all computers to the central hub.

4. Mesh Topology: In a mesh topology, every device has a dedicated point-to-point link to every other device. The term dedicated means that the link carries traffic only between two devices if connects. A fully connected mesh network therefore has n(n-1)/2 physical channels to link hn devices. To accommodate those links, every device on the network must have n-1 input/output ports. 

Advantages of Mesh Topology

i) The use of dedicated links guarantees that each connection can carry its own data load, thus eliminating traffic problems.

ii) A mesh topology is robust because the failure of single computer does not bring down the entire network.

iii) It provides security and privacy because every message sent travels along a dedicated line.

iv) Point to point links make fault diagnose easy.

Drawbacks of Mesh Topology

i) Since every computer must be connected to every other computer installation and configuration is difficult.

ii) Cabling cost is more.

iii) The hardware required connecting each link input/output and cable is expensive.

5. Tree Topology: A tree topology is the variation of a star. As in a star, nodes in a tree are linked to a central hub that controls the traffic to the network. However, not every computer plugs into the central hub, majority of them are connected to a secondary hub which, in turn, is connected to the central hub. The central hub in the tree is an active hub which contains repeater. The repeater amplifies the signal and increases the distance a signal can travel. The secondary hubs may be active or passive. A passive hub provides a simple physical hub provides a simple physical connection between the attached devices.

Advantages of Tree topology

i) It allows more devices to be attached to a single hub and can therefore increase the distance of a signal can travel between devices.

ii) It allows the network to isolate and priorities communications from different computers.

Drawbacks of Tree Topology

i) If the central hub fails, the system breaks down.

ii) The cabling cost is more.

You Might also view the following Related Posts

• Networking Fundamental
• Network Topology
• Network Functions
• Network Reference Models (Network Architectures)
• Internet Security & IP Security (IPSec)
• Secure Socket Layer (SSL)

For more Posts: Click Here