nikoo28

Question: Give an algorithm to reverse a queue. You can only use generic functions of the Queue ADT. Input: 4, 8, 15, 16, 23, 42 Output: 42,23,16,15,8,4 To solve this question will take the help of an auxiliary stack. The steps involved will be:- Create an auxiliary stack S. Until the queue Q is not empty, push the elements of the queue, in the stack S. Now we have a stack in which the last element of the Queue is at the TOP. Until the stack is empty POP(S) and …

Before implementing a queue, we must know the basic operations that should be available for a queue. Main Queue Operations:- enQueue(int data) :- Inserts an element at the end of the queue. int deQueue():- Removes and returns the element at the front of the queue. Auxiliary Queue Operations:- int front():- Returns the first element at the queue, without removing it. int queueSize():- Returns the size of the queue. int isEmptyQueue():- Indicates whether no elements are present. We can implement a queue using an ADT (Abstract Data Type). To implement a …

A queue is a linear data structure that stores data (similar to Linked Lists and Stacks). In a queue, the order in which the data arrives is important. Definition: A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element that you insert, is the first one that is removed. This makes it a First In First Out (FIFO) or Last In Last Out (LILO) list. Basic Operations: The basic operations on this data structure …

Question: Find spans in an array. Given an array arr[], the SPAN s[i] of arr[i] is the maximum number of consecutive elements arr[j] immediately before arr[i] such that arr[j] <= arr[i]. Let us try to understand the question once again. This is a very common problem in stock markets to find the peaks. Spans have applications to financial analysis(Example:- You might have heard a saying “STOCKS AT 52 WEEK HIGH”). The span of a stocks price on certain day, i , is the maximum number of consecutive days (up-to the …

This is one of the very basic pointer usage in C and to understand it let us start with a very simple example. Suppose we have a program like:- In this case the first statement: declares p as a pointer to char. When we say “pointer to a char“, what does that mean? It means that the value of p is the address of a char; p tells us where in memory there is some space set aside to hold a char. The statement also initializes p to point to …

Question: How do we implement 2 stacks using only one array? Our stack routines should not indicate an exception unless every slot in the array is used? SOLUTION: Algorithm: Start with two indexes, one at the left end and other at the right end The left index simulates the first stack and the right index simulates the second stack. If we want to push an element into the first stack then put the element at left index. Similarly, if we want to push an element into the second stack then …

Question: You are given a stack and you have to reverse it, using only stack operations push and pop. The algorithm for the above problem can be given in this way:- First POP all elements of the stack till it becomes empty Now for each upward step in the recursion, push the elements at the bottom of the stack.

Question: Given an array of characters formed by a’s and b’s. The string is marked with special character ‘X’ which represents the middle of the list (for example ababa…ababXbabab…baaa). Check whether the string is palindrome or not? Input: ababXbaba Output: PALINDROME Input: ababababababbbbbXbbbbabababababa Output: PALINDROME Input: abababbbabbXabbbabbabbb Output: NOT PALINDROME This is one of the simplest algorithms. What we do is, start two indexes – one at the beginning of the string and other at the ending of the string. Each time compare whether the values at both the indexes …

Suppose we want to find the minimum element available in a stack at any point of time. The most trivial and common method would be to traverse the entire stack and keep a record of the least element encountered. At the end, we can return this element. This method no doubt is easy, but it consists of traversing the entire stack again and again, which can lead to time complexities. Thus, we need to optimize it, and it can be done with a very neat little trick:- ALGORITHM:- Take an …

Post-fix expressions have a very special place in computer science. Most of the computations are performed using stacks. In-fact a very simple calculator works on the principle of post-fix evaluation to get the answer. A post-fix notation is also known as the reverse Polish notation. The steps involved in evaluating a post-fix expression can be defined as follows. We use the concept of stacks to evaluate the same. ALGORITHM: Scan the post-fix string from left to right. Initialize an empty stack. Repeat the below steps 4 and 5 till all …