Role Of Data Structures In Programming Languages

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. It is also known as the logical or mathematical model of a particular organization of data.

Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by an address – a bit string that can be itself stored in memory and manipulated by the program. Thus the record and array data structures are based on computing the addresses of data items with arithmetic operations; while the linked data structures are based on storing addresses of data items within the structure itself. Many data structures use both principles, sometimes combined in non-trivial ways

Choice of particular data model depends on 2 considerations:-

It must be rich enough in structure to mirror the actual relationships of the data in real world.

Structure should be simple enough that one can effectively process the data when necessary.

Classification of data structure

Primitive and Non-primitive : primitive data structures are basic data structure and are directly operated upon machine instructions.Example Integer,character. Non-primitive data structures are derived data structure from the primitive data structures.Example Structure,union,array.

Homogeneous and heterogeneous : In homogeneous data structures all the elements will be of same type.Example array. In heterogeneous data structure the elements are of different types.Example structure.

Static and Dynamic data structures :In some data structures memory is allocated at the time of compilation such data structures are known as static data structures . If the allocation of memory is at run-time then such data structures are known as Dynamic data structures.Functions such as malloc, calloc,etc.. are used for run-time memory allocation.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

Linear and Non-linear data structures : Linear data structure maintain a linear relationship between its elements and whose elements form a sequence and every element in structure has unique predecessor and successor. Example array. Non-linear data structures does not maintain hierarichal relationship between the elements. Example tree

Some Data Structures

And

Their role in Programming Languages

Stack

In computer science, a stack is a last in, first out (LIFO) data structure.

History

The stack was first proposed in 1955, and then patented in 1957, by the German Friedrich L. Bauer. The same concept was developed independently, at around the same time, by the Australian Charles Leonard Hamblin..

Operations on stacks

A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

Simple representation of a stack

A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are typically those that have been in the list the longest.

In modern computer languages, the stack is usually implemented with more operations than just “push” and “pop”. Some implementations have a function which returns the current length of the stack. Another typical helper operation top (also known as peek) can return the current top element of the stack without removing it.

Basic architecture of a stack

Role of stacks in programming languages

Languages such as Adobe PostScript are also designed around language-defined stacks that are directly visible to and manipulated by the programmer.

C++’s Standard Template Library provides a “stack” templated class which is restricted to only push/pop operations. Java’s library contains a stack class that is a specialization of vector—this could be considered a design flaw, since the inherited get() method from vector ignores the LIFO constraint of the stack.

The simple model provided in a stack-oriented programming language allows expressions and programs to be interpreted simply and theoretically evaluated much more quickly, since no syntax analysis needs to be done, only lexical analysis. The way programs are written lends itself well to being interpreted by machines, which is why PostScript suits printers well for its use. However, the slightly artificial way of writing PostScript programs can result in an initial barrier to understanding the PostScript language and other stack-oriented programming languages.

Whilst the capability of shadowing by overriding inbuilt and other definitions can make things difficult to debug – and irresponsible usage of this feature can result in unpredictable behaviour – it can make certain functionality much simpler. For example, in PostScript usage, the showpage operator can be overridden with a custom one that applies a certain style to the page, instead of having to define a custom operator or to repeat code to generate the style.

Implementation

In most high level languages, a stack can be easily implemented through an array. What identifies the data structure as a stack in either case is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations. The following will demonstrate both implementations, using C.

Array

The array implementation aims to create an array where the first element (usually at the zero-offset) is the bottom. That is, array[0] is the first element pushed onto the stack and the last element popped off. The program must keep track of the size, or the length of the stack. The stack itself can therefore be effectively implemented as a two-element structure in C:

typedef struct {

int size;

int items[STACKSIZE];

} STACK;

The push() operation is used both to initialize the stack, and to store values to it. It is responsible for inserting (copying) the value into the ps->items[] array and for incrementing the element counter (ps->size). In a responsible C implementation, it is also necessary to check whether the array is already full to prevent an overrun.

void push(STACK *ps, int x)

{

if (ps->size == STACKSIZE) {

fputs(“Error: stack overflown”, stderr);

abort();

} else

ps->items[ps->size++] = x;

}

The pop() operation is responsible for removing a value from the stack, and decrementing the value of ps->size. A responsible C implementation will also need to check that the array is not already empty.

int pop(STACK *ps)

{

if (ps->size == 0){

fputs(“Error: stack underflown”, stderr);

abort();

} else

return ps->items[–ps->size];

}

Procedures

A procedure in a stack-based programming language is treated as a data object in its own right. In PostScript, procedures are denoted between { and }.

For example, in PostScript syntax,

{ dup mul }

represents an anonymous procedure to duplicate what is on the top of the stack and then multiply the result – a squaring procedure.

Since procedures are treated as simple data objects, we can define names with procedures, and when they are retrieved, they are executed directly.

Dictionaries provide a means of controlling scoping, as well as storing of definitions.

Since data objects are stored in the top-most dictionary, an unexpected capability arises quite naturally: when looking up a definition from a dictionary, the topmost dictionary is checked, then the next, and so on. If we define a procedure that has the same name as another already defined in a different dictionary, the local one will be called.

Anatomy of some typical procedures

Procedures often take arguments. They are handled by the procedure in a very specific way, different from that of other programming languages.

Let us examine a Fibonacci number program in PostScript:

/fib

{

dup dup 1 eq exch 0 eq or not

{

dup 1 sub fib

exch 2 sub fib

add

} if

} def

We use a recursive definition, and do so on the stack. The Fibonacci number function takes one argument. We first test whether it is 1 or 0.

Let us decompose each of the program’s key steps, reflecting the stack. Assume we calculate F(4).

stack: 4

dup

stack: 4 4

dup

stack: 4 4 4

1 eq

stack: false 4 4

exch

stack: 4 false 4

0 eq

stack: false false 4

or

stack: false 4

not

stack: true 4

Since the expression evaluates to true, the inner procedure is evaluated.

stack: 4

dup

stack: 4 4

1 sub

stack: 3 4

fib

(we recurse here)

stack: F(3) 4

exch

stack: 4 F(3)

2 sub

stack: 2 F(3)

fib

(we recurse here)

stack: F(2) F(3)

add

stack: F(2)+F(3)

which is the result we wanted.

This procedure does not use named variables, purely the stack. We can create named variables by using the

/a exch def

construct. For example,

{/n exch def n n mul}

is a square procedure with a named variable n. Assume that

/sq {/n exch def n n mul} def

and

3 sq

is called. Let us analyse this procedure.

stack: 3 /n

exch

stack: /n 3

def

stack: empty (it has been defined)

n

stack: 3

n

stack: 3 3

mul

stack: 9

which is the result we wanted.

Expression evaluation and syntax parsing

Calculators employing reverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context free languages allowing them to be parsed with stack based machines.

Example in C

#include

int main()

{

int a[100], i;

printf(“To pop enter -1n”);

for(i = 0;;)

{

printf(“Push “);

scanf(“%d”, &a[i]);

if(a[i] == -1)

{

if(i == 0)

{

printf(“Underflown”);

}

else

{

printf(“pop = %dn”, a[–i]);

}

}

else

{

i++;

}

}

}

Runtime memory management

A number of programming languages are stack oriented, meaning they define most basic operations (adding two numbers, printing a character) as taking their arguments from the stack, and placing any return values back on the stack. For example, Postscript has a return stack and an operand stack, and also has a graphics state stack and a dictionary stack.

Forth uses two stacks, one for argument passing and one for subroutine return addresses. The use of a return stack is extremely commonplace, but the somewhat unusual use of an argument stack for a human-readable programming language is the reason Forth is referred to as a stack based language.

Almost all computer runtime memory environments use a special stack (the “call stack”) to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. They follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls. This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.

Some programming languages use the stack to store data that is local to a procedure. Space for local data items is allocated from the stack when the procedure is entered, and is deallocated when the procedure exits. The C programming language is typically implemented in this way. Using the same stack for both data and procedure calls has important security implications (see below) of which a programmer must be aware in order to avoid introducing serious security bugs into a program.

Linked Lists

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference(i.e., a link) to the next record in the sequence.

A linked list whose nodes contain two fields: an integer value and a link to the next node

Linked lists can be implemented in most languages. Languages such as Lisp and Scheme have the data structure built in, along with operations to access the linked list. Procedural languages, such as C, or object-oriented languages, such as C++ and JAVA, typically rely on mutable references to create linked lists.

History

Linked lists were developed in 1955-56 by Allen Newell, Cliff Shaw and Herbert Simon at RAND Corporation as the primary data structure for their Information Processing Language.

Role of linked lists in programming languages

Many programming languages such as Lisp and Scheme have singly linked lists built in. In many functional languages. In languages that support Abstract Data types or templates, linked list ADTs or templates are available for building linked lists. In other languages, linked lists are typically built using references together with records. Here is a complete example in C:

#include /* for printf */

#include /* for malloc */

typedef struct node {

int data;

struct node *next; /* pointer to next element in list */

} LLIST;

LLIST *list_add(LLIST **p, int i);

void list_remove(LLIST **p);

LLIST **list_search(LLIST **n, int i);

void list_print(LLIST *n);

LLIST *list_add(LLIST **p, int i)

{

if (p == NULL)

return NULL;

LLIST *n = malloc(sizeof(LLIST));

if (n == NULL)

return NULL;

n->next = *p; /* the previous element (*p) now becomes the “next” element */

*p = n; /* add new empty element to the front (head) of the list */

n->data = i;

return *p;

}

void list_remove(LLIST **p) /* remove head */

{

if (p != NULL && *p != NULL)

{

LLIST *n = *p;

*p = (*p)->next;

free(n);

}

}

LLIST **list_search(LLIST **n, int i)

{

if (n == NULL)

return NULL;

while (*n != NULL)

{

if ((*n)->data == i)

{

return n;

}

n = &(*n)->next;

}

return NULL;

}

void list_print(LLIST *n)

{

if (n == NULL)

{

printf(“list is emptyn”);

}

while (n != NULL)

{

printf(“print %p %p %dn”, n, n->next, n->data);

n = n->next;

}

}

int main(void)

{

LLIST *n = NULL;

list_add(&n, 0); /* list: 0 */

list_add(&n, 1); /* list: 1 0 */

list_add(&n, 2); /* list: 2 1 0 */

list_add(&n, 3); /* list: 3 2 1 0 */

list_add(&n, 4); /* list: 4 3 2 1 0 */

list_print(n);

list_remove(&n); /* remove first (4) */

list_remove(&n->next); /* remove new second (2) */

list_remove(list_search(&n, 1)); /* remove cell containing 1 (first) */

list_remove(&n->next); /* remove second to last node (0) */

list_remove(&n); /* remove last (3) */

list_print(n);

return 0;

Queue

A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes the queue a First In First Out. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked. A queue is an example of a linear data structure.

Representation of a Queue

Example C Program

#include

int main(){

int a[100],i,j;

printf(“To DQueue Enter -1n”);

for(i=0;;){

printf(“NQueue “);

scanf(“%d”,&a[i]);

if(a[i]==0)

break;

if(a[i]==-1){

a[i]=0;

if(i==0){

printf(“Wrongn”);

continue;

}

printf(“DQueue = %dn”,a[0]);

for(j=0;ja[j]=a[j+1];

i–;

}

else

i++;

}

for(j=0;jprintf(“%d “,a[j]);

return 0;

}