Stacks and Queues are the most important chapters in Data Structure.
Stack & Queue :
- Stacks: A stacks is an abstract data type. Which declares two methods PUSH and POP.? Stacks are implemented either by an array or by a linked list.
- The PUSH operation allows us to insert data at the end of an array or linked list. The POP operation allows us to remove data from the end of and array or linked list. A STACK is called linked stack.
- A stack may be represented by a linked list. The first node of the will be the topmost element of the stack and is pointed by a top pointer. This type of stack representation is called linked list. The stack can be declared as follows:
typedef struct linked_list
{
int data;
struct linked_list *next;
} lstack;
lstack *top;
- Various types of expression: A mathematical expression involves constants (operands) and operations (operators).
Infix notation: operand l operator operand 2, A+B
Prefix notation: operator operand l operand 2, +AB
Postfix notation: operand l operand 2 operator, AB+
- Conversion from INFIX TO POSTFIX expression: In order to convert the infix to its corresponding postfixes form; we need to do the following steps:
Fully parenthesize the expression according to do the priority of different operators.
Move all operators so that they replace their corresponding right parentheses.
Delete all parentheses.
The priorities of differents operators:
| Operators | Priority |
| Unary -, unary +, not ( ! ) | 4 |
| * , / , % , and ( & / && ) | 3 |
| + , – , or ( | / || ) | 2 |
| < , <= , > , >= , == , != | 1 |
- Priority Queue: A priority queue is essentially a list of items in which each item has associated with it a priority. In general, different items may have different priorities and we speak of one item having a higher priority than another. Given such a list we can determine which is the highest (or the lowest) priority item in the list. Items are inserted into a priority queue in any, arbitrary order. However, items are withdrawn from a priority queue in order of their priorities started with the highest priority item first. Two elements with the same priority are processed according to the order in which they were added to the queue.
- De-queue: De-queue is a linear data structure, where insertions and deletions are made to or from either end of the structure.
What is Max-Heap?
A heap is a tree-based data structure that satisfies the heap property: if B is a child node of A then key(A) >= key (B). This implies that an element with the greatest key is always in the root node. and so such a heap is sometimes called max-heap.
Convert the following infix expression into equivalent postfix expression using stack: (A+B)*C-(D-E)/(F+G).
Evaluate the following postfix expression: 4,5,4,2,^,+,*,2,2,^,9,3,/,*,-
4,5,4,2,^,+,*,2,2,^,9,3,/,*,-
= 4,5,16,+,*,2,2,^,9,3,/,*,-
=4,21,*,2,2,^,9,3,/,*,-
=84,2,2,^,9,3,/,*,-
=84,4,9,3,/,*,-
=84,4,3,*,-
=84,12,-
=76
How many types of priority queues are there?
Mainly there are two kinds of priority queue: Static priority queue, Dynamic priority queue.
Stack can be considered as Priority queue where the priorities of each element being inserted are considered higher than the previous one. This will let it behave like a LIFO structure (i.e. stack).
What is input restricted Dequeue?
An input restricted Dequeue is one where deletion can be made from both ends, but input can only be made at one end.
What is a Stack ADT?
A stack ADT is a (ordered) collection of items, where all insertions are made to the end of the sequence and all deletions always are made from the end of the sequence. In principle a stack is a container of data items, from which we gate data items out in reverse order compared to the order they have been put into the container. We can also say that the item that has been put last in is coming first out. That’s why a stack is also called LIFO (Last In First Out list). We can ass well say that the item, which is put first in the container is get last out (First In Last Out: FILO).
What is Circular queue ?
The two algorithms QINSERT & QDELETE can be verry wasteful of storage if the front pointer F never manages to catch up the rear pointer. Actually an Arbitrary largee amount of memory would be required to accommodate the elements. The method of performing operations on a Queue should only be used whene the queue is emptied at certain intervals.
Let us cosider the following sequence of operations. F and R represented the front and rear pointers.
To avoid this problem we can think an alternative representation of a queue, which prevents an excessive use of memory. In this represeentation elements are arranged as in a circular fashion where the rear again points to the front. This type of queue is known circular queues.
So the above sequence of operations can be represented are shown bellow (in circular queue).
As we can see that the overflow issue in the previous case while inserting E is resolved by redirecting the rear to the front. This is the essence of circular queue.
Write an algorithm to insert an item in circular queue.
void QInsert(int item)
{
if (rear == N-1)
{
printf("Queue Is Full");
return;
}
CQ[++rear] = item;
if (front == -1)
front = 0;
}