Operations of Data Structure and Queues
There are some specified operations in which the processing of the visible data in the data structure is done. The operations which are used for doing so are called as the data structure operations. These play a vital role in the processing of the data in the structure. The name and the definition of those operations are as follows-
1. Traversing- traversing is visiting each and every node of the data structure and that too exactly once.
2. Insertion- Addition or the insertion of the new record into the data structure is called insertion.
3. Deletion- Removing or deletion of the record from the data structure is called the deletion operation.
4. Searching- It is done in order to find the record in the specific location in the data structure.
There are two more operations in the data structure, but they are used in some special conditions.
1. Sorting- The arrangement of the available records of the data structure in the form of a logical manner is called sorting. For example, the arrangement of the list of digits in the decreasing or increasing manner or the organization of the letters in the alphabetical order can also be an example of a sorting operation.
2. Merging- The combination of the records of the two sorted files into another file of sorted elements is called merging.
Before proceeding further, read the introduction to the data structures.
A linear list of the elements in which they can be inserted as well as deleted but at the end only is called a stack or the top of the stack. The first element to come out of the stack is the one which was lastly inserted into it. That is why it is called as LIFO system. In this system, the deletions and the new insertions take place only at the end of the stack, which in turn is the top of the stack. Push and Pop are the two special terminologies which are associated with the stacks.
The process of inserting a new element in the stack is called pushing.
It is the counterpart of the push operation. Here, the deletion of the element takes place.
It is a special term which is used when there is a requirement of accessing the top-elements of the stack. We have one condition, there should be the removal of the element from the stack. That is why peek is the term used for this operations’ performance.
POLISH AND INFIX NOTATION
• Infix Notation-
In an arithmetic expression, the two operands have the operator symbol in between them.
A/B, M*N, C-D is one of the examples of the infix notation.
• Polish Notation-
It is the notation in which the operands place the operator symbol before them.
/AB, *MN, -CD is the example. For the polish notation, prefix notation is used to describe it.
• Reverse Polish Notation-
It is a notation in which the two operands the operator symbol after them. This is called the Reverse Polish Notation.
AB/, MN*, CD-
This is called the suffix or postfix of the notation.
FIFO system is the name of the system used to define the queues. Here, the deletion of the element occurs only at one end, and this is called the front. Whereas, the end from which the insertions of the elements take place is called the rear. There is a requirement of two variables for the representation of the queue. The first points to the front element and the second at the rear queue element.
• Linear queue
The one and the most prominent limitation of the linear queue is that we cannot add more elements to it when its last room has already been filled. It does not matter whether there are certain positions vacant in the list before the last node, we are unable to insert anything. For overcoming the problem, the elements of the queue are forwarded to make the shift of the elements towards the rear end. As the elements get shifted in the rear ends, there is a proper adjustment of the front and the rear of the linear queue. As a result, further insertions are possible.
• Circular Queue
When we have an array of elements which are n in number, and when the first room comes last room then it is called the circular queue. When we have to insert any new element in the circular queue, then the insertion takes place in the position of the first element. It is unlike the linear queue where the elements are moved forward for the insertion process to occur. Yes, the former process which defines the circular queue consumes less time as compared to the forward movement of the elements.
• Priority Queue
It is a queue where every element come with the associated priority. The determination of the order of the exiting from the queue takes place as per the associated priority. The elements which come with the highest priority are the first to be removed. For the deletion and the other processes, read below-
1. The elements which have lower priority are processed after the high priority elements.
2. If the two elements of the queue have the same processing priority, then the order is decided as per the order in which they were added to the queue.
For the implementation of the queue, there is a usage of the two arrays. The first array stores each element’s priority, and in the second array, part of the information is stored.
It is a type of the linear list where there is no insertion and deletion from the middle of the queue, but it takes place at either end. There are different ways to represent the deque. The circular array elements maintain the deque with the help of the LEFT and RIGHT pointers. They both initially point to the two ends of the deque. The insertion and deletion can take place from either end.
When there is a circular queue, insertion of the elements takes place from the LEFT pointer and that too in a clockwise manner. Whereas, the deletion of the elements occurs from the RIGHT pointer and in the anticlockwise direction. We can also adopt the vice-versa procedure as well.
Input restricted queue and output restricted queue are the two variations of a deque.
1. Input Restricted Deque-
In this type of deque, the insertion takes place from only on end of the list. But it allows the deletion of the elements from both the ends of the list.
2. Output Restricted Queue-
The deque works oppositely from the other variation of the deque. Here, the deletions of the items take place from one end of the list, but both the ends of the list are used for insertions.
The function which contains call statements, either by itself or another function is called a recursion function. The result of the function is the call statement to that function. The nature of the function is stack making. All the variables belonging to that function which are auto are called every time the function calls itself. The function and the variables are pushed onto a stack, and then it results in the new virtual instance of that function. After this, it begins its execution for the set of auto variables.