UNIT 2 ADS




                                                                         UNIT 2


1)      Stack and Queue ADT:
Stack:  a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop.[1] The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. In a LIFO data structure, the last element added to the structure must be the first one to be removed.
   
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 overflow\n", 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 underflow\n", stderr);
        abort();
    } else
        return ps->items[--ps->size];
}

Queue:
 a queue (/ˈkjuː/ kew) is a particular kind of abstract data typeor 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, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. 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 once a new element is added, all elements that were added before have to be removed before the new element can be removed.

2)      Recursion:
Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.
We will begin our investigation with a simple problem that you already know how to solve without using recursion. Suppose that you want to calculate the sum of a list of numbers such as: [1,3,5,7,9]. An iterative function that computes the sum is shown in ActiveCode 1. The function uses an accumulator variable (theSum) to compute a running total of all the numbers in the list by starting with 0 and adding each number in the list.
1

def listsum(numList):
    theSum = 0
    for i in numList:
        theSum = theSum + i
    return theSum

print(listsum([1,3,5,7,9]))


Indirect recursion[edit]

Main article: Mutual recursion
Most basic examples of recursion, and most of the examples presented here, demonstrate direct recursion, in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.
Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a different of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.

Anonymous recursion[edit]

Main article: Anonymous recursion
Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion.
3)      Convert Infix Expression to Post-Fix Expression
4)      Conventional notation is called infix notation. The arithmetic operators appears between two operands. Parentheses are required to specify the order of the operations. For example: a + (b * c).
5)      Post fix notation (also, known as reverse Polish notation) eliminates the need for parentheses. There are no precedence rules to learn, and parenthese are never needed. Because of this simplicity, some popular hand-held calculators use postfix notation to avoid the complications of multiple sets of parentheses. The operator is placed directly after the two operands it needs to apply. For example: a b c * +
6)      This short example makes the move from infix to postfix intuitive. However, as expressions get more complicated, there will have to be rules to follow to get the correct result:
7)       
8)     
Simple heuristic algorithm to visually convert infix to postfix

 •  Fully parenthesize the expression, to reflect correct operator precedence
 •  Move each operator to replace the right parenthesis to which it belongs
 •  Remove paretheses
9)       
10)  Evaluating expressions

A stack is used in two phases of evaluating an expression such as

       3 * 2 + 4 * (A + B)
11)  •Convert the infix form to postfix using a stack to store operators and then pop them in correct order of precedence.
•Evaluate the postfix expression by using a stack to store operands and then pop them when an operator is reached. 
12)  Infix to postfix conversion
Scan through an expression, getting one token at a time.

1 Fix a priority level for each operator. For example, from high to low:

    3.    - (unary negation)
    2.    * /
    1.    + - (subtraction)
13)  Thus, high priority corresponds to high number in the table.

2 If the token is an operand, do not stack it. Pass it to the output.

3 If token is an operator or parenthesis, do the following:

   -- Pop the stack until you find a symbol of lower priority number than the current one. An incoming left parenthesis will be considered to have higher priority than any other symbol. A left parenthesis on the stack will not be removed unless an incoming right parenthesis is found.
The popped stack elements will be written to output.

   --Stack the current symbol. 
14)     -- If a right parenthesis is the current symbol, pop the stack down to (and including) the first left parenthesis. Write all the symbols except the left parenthesis to the output (i.e. write the operators to the output).

   -- After the last token is read, pop the remainder of the stack and write any symbol (except left parenthesis) to output. 
15)  Example: 
16)  Convert A * (B + C) * D to postfix notation. 
Move
Curren Ttoken
Stack
Output
1
A
empty
A
2
*
*
A
3
(
(*
A
4
B
(*
A B
5
+
+(*
A B
6
C
+(*
A B C
7
)
*
A B C +
8
*
*
A B C + *
9
D
*
A B C + * D
10
empty

Notes:
In this table, the stack grows toward the left. Thus, the top of the stack is the leftmost symbol.
In move 3, the left paren was pushed without popping the * because * had a lower priority then "(".
In move 5, "+" was pushed without popping "(" because you never pop a left parenthesis until you get an incoming right parenthesis. In other words, there is a distinction between incoming priority, which is very high for a "(", and instack priority, which is lower than any operator.
In move 7, the incoming right parenthesis caused the "+" and "(" to be popped but only the "+" as written out.
In move 8, the current "*" had equal priority to the "*" on the stack. So the "*" on the stack was popped, and the incoming "*" was pushed onto the stack.
4) Array and linked list:


5) Circular queue:
A circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-sizebuffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams
                     
The useful property of a circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited as aFIFO buffer while a standard, non-circular buffer is well suited as a LIFO buffer.

How it works[edit]

A circular buffer first starts empty and of some predefined length. For example, this is a 7-element buffer:
Assume that a 1 is written into the middle of the buffer (exact starting location does not matter in a circular buffer):
Then assume that two more elements are added — 2 & 3 — which get appended after the 1:
If two elements are then removed from the buffer, the oldest values inside the buffer are removed. The two elements removed, in this case, are 1 & 2, leaving the buffer with just a 3:
If the buffer has 7 elements then it is completely full:
A consequence of the circular buffer is that when it is full and a subsequent write is performed, then it starts overwriting the oldest data. In this case, two more elements — A & B — are added and they overwrite the 3 & 4:
Alternatively, the routines that manage the buffer could prevent overwriting the data and return an error or raise an exception. Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer.
Finally, if two elements are now removed then what would be returned is not 3 & 4 but 5 & 6 because A & B overwrote the 3 & the 4 yielding the buffer with:



6)  Dequeue ADT:

7) Priority Queue ADT:
 a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

Operations[edit]

A priority queue must at least support the following operations:
·         insert_with_priority: add an element to the queue with an associated priority.
·         pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it.
This is also known as "pop_element(Off)", "get_maximum_element" or "get_front(most)_element".
Some conventions reverse the order of priorities, considering lower values to be higher priority, so this may also be known as "get_minimum_element", and is often referred to as "get-min" in the literature.
This may instead be specified as separate "peek_at_highest_priority_element" and "delete_element" functions, which can be combined to produce "pull_highest_priority_element".

Priority Queues and Heaps:
                                   

8) java.util package array list:
java.lang.Object
        java.util.AbstractCollection
                java.util.AbstractList
                        java.util.ArrayList
public class ArrayList
implements List, Cloneable, Serializable
extends AbstractList
Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for theLinkedList implementation.
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.
Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedListmethod. This is best done at creation time, to prevent accidental unsynchronized access to the list:
      List list = Collections.synchronizedList(new ArrayList(...));
Constructor Index
Constructor
Description
ArrayList()
Constructs an empty list.
ArrayList(Collection)
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
ArrayList(int)
Constructs an empty list with the specified initial capacity.

Method Index
Method
Description
void add(int, Object)
Inserts the specified element at the specified position in this list.
boolean add(Object)
Appends the specified element to the end of this list.
boolean addAll(Collection)
Appends all of the elements in the specified Collection to the end of this list, in the order that they are returned by the specified Collection's Iterator.

Class java.util.LinkedList

java.lang.Object
        java.util.AbstractCollection
                java.util.AbstractList
                        java.util.AbstractSequentialList
                                java.util.LinkedList
public class LinkedList
implements List, Cloneable, Serializable
extends AbstractSequentialList
Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque).
All of the stack/queue/deque operations could be easily recast in terms of the standard list operations. They're included here primarily for convenience, though they may run slightly faster than the equivalent List operations.
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the begining or the end, whichever is closer to the specified index.
Note that this implementation is not synchronized. If multiple threads access a list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:
     List list = Collections.synchronizedList(new LinkedList(...));
Constructor Index
Constructor
Description
LinkedList()
Constructs an empty list.
LinkedList(Collection)
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Method Index
Method
Description
void add(int, Object)
Inserts the specified element at the specified position in this list.
boolean add(Object)
Appends the specified element to the end of this list.

Class java.util.Vector

java.lang.Object
        java.util.AbstractCollection
                java.util.AbstractList
                        java.util.Vector
public class Vector
implements List, Cloneable, Serializable
extends AbstractList
The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.
Each vector tries to optimize storage management by maintaining a capacity and a capacityIncrement. The capacity is always at least as large as the vector size; it is usually larger because as components are added to the vector, the vector's storage increases in chunks the size ofcapacityIncrement. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation.

Class java.util.Stack

java.lang.Object
        java.util.AbstractCollection
                java.util.AbstractList
                        java.util.Vector
                                java.util.Stack
public class Stack
extends Vector
The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack isempty, and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.
Constructor Index
Constructor
Description
Stack()
Creates an empty Stack.

Method Index
Method
Description
boolean empty()
Tests if this stack is empty.
Object peek()
Looks at the object at the top of this stack without removing it from the stack.

java.util 
Interface Iterator<E>

All Known Subinterfaces:
ListIterator<E>, XMLEventReader
All Known Implementing Classes:
BeanContextSupport.BCSIterator, EventReaderDelegate, Scanner

public interface Iterator<E>
An iterator over a collection. Iterator takes the place of Enumeration in the Java collections framework. Iterators differ from enumerations in two ways:
  • Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
  • Method names have been improved.
This interface is a member of the Java Collections Framework.
Since:
1.2
See Also:
Collection, ListIterator, Enumeration

Method Summary
 boolean
hasNext() 
          Returns true if the iteration has more elements.
 E
next() 
          Returns the next element in the iteration.
 void
remove() 
          Removes from the underlying collection the last element returned by the iterator (optional operation).

Method Detail

hasNext

boolean hasNext()
Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)
Returns:
true if the iterator has more elements.

next

E next()
Returns the next element in the iteration.
Returns:
the next element in the iteration.
Throws:
NoSuchElementException - iteration has no more elements.

remove

void remove()



No comments:

Post a Comment

Subscribe to: Posts (Atom)