Home Tags Posts tagged with "Stack"
Tag:

# Stack

Algorithms involving stacks

• Strings

## [Hackerrank] – Super Reduced Strings

Let us try to understand this problem statement first. We have some strings that needs to be super reduced in size. The string consists of english alphabets from a to z, and they can be duplicated at some places. If we see two adjacent characters that are same, they can be eliminated. Following this pattern we have to return a super compressed/reduced string. Let us look at some sample test cases: Input: aabcccddOutput: “bc”Explanation:aabcccdd -> bcccdd -> bcdd -> bc(we eliminate two same adjacent characters at each step) Input: abbaOutput: …

• Arrays

## [Hackerrank] – Queue using two stacks

A queue is a linear data structure which maintains the order in which the elements appear. You need to implement a queue, using two stacks such that it behaves in the same way. If you are unfamiliar with the queue data structure and the stack data structure, it would be a good idea to learn them before approaching this problem. Problem Statement: The basic crux of the problem is that you are to implement a queue and its operations using stacks. It may seem unnecessary in the beginning, as a …

• Arrays

## [Hackerrank] – Equal Stacks Solution

Question: Given 3 arrays, where each element represent the height of a cylinder. Find the maximum possible height of equal stacks by removing one or more cylinders from the original stack. Example: Input: n1[] = {3, 2, 1, 1, 1}n2[] = {4, 3, 2}n3[] = {1, 1, 4, 1} Output: 5 Problem Statement Let us try to simplify the problem statement first. The problem states that you are provided with 3 sets of arrays. Each element in the array represents the height of a cylinder. Now, all these cylinders are …

• Arrays

## Next Greater Element in an array. [NGE]

Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that each element in Output[i] will tell the next greater element to the right in the original array. If there is no greater number to the right, then the output array should contain -1 in that position.Array 1: {4, 6, 5, 4, 3, 4, 9, 8, 1} Output: {6, 9, 9, 9, 4, 9, -1, -1, -1} Let us try to understand the problem statement. We are given an input array that has …

• ## PostOrder Traversal in a binary tree

We discussed about the basic tree traversals in this post – Binary Tree Traversals Lets take our own sample tree for understanding post-order traversal. In Post-Order traversal, the root is visited after both sub-trees are completed. Post-order traversal is defined as follows:- Traverse the left sub-tree in post-order. (Step 1) Traverse the right sub-tree in post-order. (Step 2) Visit the root The post-order traversal can then be defined in this way – The nodes of the tree will therefore be in order – 4, 5, 2, 6, 7, 3, 1 …

• ## InOrder Traversal in a binary tree

We discussed about the tree traversal techniques in this post- Binary Tree Traversals Please see pre-order traversal to understand the basics of visiting nodes. We have our same sample tree Now let us try to understand the In-order traversal. In in-order traversal, the root is traversed between the sub trees. In-order traversal is defined as follows. Traverse the left sub-tree Visit the node Traverse the right sub-tree So when we apply the in-order traversal on our example tree this will be done as:- We get the final in-order traversal as:- …

• ## PreOrder Traversal in a binary tree

We learned about the different type of traversals in this post Binary Tree Traversals In pre-order traversal, each node is processed before (pre) either of its sub-trees. This is the simplest traversal to understand. However, even though each node is processed before the sub-trees, it still requires that some information must be maintained while moving down the tree. Let us consider an example In the example tree shown above, the node “1” is processed first, then the left sub-tree, followed by the right sub-tree. Therefore, processing must return to the …

• Misc

## How will you reverse a queue?

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 …

• Arrays