If you have a stack that contains 3000 integers, and you need to see if it contains the number 5678, what is the worst case scenario in terms of the number of operations you would have to do? You can use a second stack. Count every peek, push, pop and comparison, and assume you need to ensure that the integers in the collection maintain their order in the original stack.

If you have a stack that contains 3000 integers, and you need to see if it contains the number 5678, what is the worst case scenario in terms of the number of operations you would have to do? You can use a second stack. Count every peek, push, pop and comparison, and assume you need to ensure that the integers in the collection maintain their order in the original stack.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter18: Stacks And Queues

Section: Chapter Questions

Problem 16PE: The implementation of a queue in an array, as given in this chapter, uses the variable count to...

See similar textbooks

Similar questions

The insertion sort was discussed and the implementation was demonstrated in the sorting lecture. In this assignment, you are asked to re-implement the insertion sort (InsertionSort.java),with additional requirements. Particularly, you need to show:1. For each iteration, how a number from a unsorted region is placed in the correctionposion in the sorted region;2. How to make the whole array be sorted based on the previous step, and count the totalnumber of shifts during the whole insertion sort process.2 Details of the ProgramTo complete the whole implementation, you should write at least the following importantmethods:2.1 Part1: insertLast/**A method to make an almost sorted array into fully sorted.@param arr: an array of integers, with all the numbers are sortedexcepted the last one@param size: the number of elements in an array*/public static void insertLast(int[] arr, int size){// your work}To make it concrete, let’s use the example shown in Figure 1. In this example, the…
It's a very nice application of stacks. Consider that a freight train has n railroad cars. Each to be left at different station. They're numbered 1 through n & freight train visits these stations in order n through 1. Obviously, the railroad cars are labeled by their destination. To facilitate removal of the cars from the train, we must rearrange them in ascending order of their number (i.e. 1 through n). When cars are in this order, they can be detached at each station. We rearrange cars at a shunting yard that has input track, output track & k holding tracks between input & output tracks (i.e. holding track). The figure shows a shunting yard with three holding tracks H1, H2 & H3, also n = 9. The n cars of freight train begin in the input track & are to end up in the output track in order 1 through n from right to left. The cars initially are in the order 5,8,1,7,4,2,9,6,3 from back to front. Later cars are rearranged in desired order. To rearrange cars, we…
Given a set of n types of rectangular 3-D boxes, where the ith box has height hi, width wi and depth di (all real numbers). Create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. It is possible to rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box. Precisely define the subproblem.Provide the recurrence equation.Describe the algorithm in pseudocode to compute the optimal value.Describe the algorithm in pseudocode to print out an optimal solution.
You are the sysadmin for a big tech company, and you have to estimate the amount of servers you need to handle some long-running jobs. One server can handle only one job at once. One job can only be executed by one server at once. Once a server has finished executing its current job, it can be reassigned to a new job. Given an array of time intervals intervals where intervals[i] = [starti, endi], representing the start and end time for a particular job that needs to be executed, return the minimum number of servers required to run all jobs. Constraints: 1 <= intervals.length <= 104 0 <= starti < endi <= 106 Function definition for Java: public int minMeetingRooms(int[][] intervals) { // Your code here } Function definition for Python: def minMeetingRooms(self, intervals: List[List[int]]) -> int: #Your code here Announced Test Cases: Input: intervals = [[0,30],[5,10],[15,20]] Output: 2Explanation: We need one server for the job that starts at 0. For the job…
Solve using JAVA only Given a square chess board of size N, solve the N queens problem. Print out the number of solutions for a given N. You do not need to print out or produce the actual solutions, only the number of correct solutions. Solve for N between 2 and 8. Try your program with 9 and 10, produce those results if it returns in a reasonable amount of time. The N queens problem is to find every configuration of N queens distributed on an NxN square chess board such that all queens are safe from attack by each other.
g. If you have 1024 Bytes of memory, what is the maximum length of the linked list of integers that you can create. You can assume that full memory can be used for creating the linked list. Answer:
Consider a list L = {387, 690, 234, 435, 567, 123, 441}. Here, the number ofelements n = 7, the number of digits l = 3 and radix r = 10. This means that radixsort would require 10 bins and would complete the sorting in 3 passes. illustrates the passes of radix sort over the list. It is assumed that each key is thrown into the bin face down. At the end of each pass, when the keys are collected from each bin in order, the list of keys in each bin is turned upside down to be appended to the output list
The following are the operations that you can do using a single linked list. Choose only one operation then create the algorithm and simulate. The attached Rubric will be used in evaluating the activity. 1. Delete a particular node in a single linked list 2. Delete the first node of a single linked list 3. Insertion after a given node of a single linked list 4. Insertion at a given position in a single linked list 5. Insertion before a given node in a single linked list 6. Reverse a single linked list EX: Delete the last node of a single linked list Problem" Deletion of the last node in a single linked list Algorithm" Step 1: if HEAD = NULL Write UNDERFLOW Go to Step 8 Step 2: SET PTR = HEAD Step 3: Repeat Steps 4 and while PTR à NEXT = NULL Step 4: SET PREPPTR = PTR Step 5: SET PTR =PTR à NEXT [End of loop] Step 6: SET PREPTR à NEXT = NULL Step 7: FREE PTR Step 8: EXIT…
Question.
Solve using JAVA only Given a square chess board of size N, solve the N queens problem. ONLY Print out the NUMBER of solutions for a given N. DO NOT print out or produce the actual solutions, the code shold ONLY PROVIDE the number of correct solutions. Solve for N between 2 and 8. Try your program with 9 and 10, produce those results if it returns in a reasonable amount of time. The N queens problem is to find every configuration of N queens distributed on an NxN square chess board such that all queens are safe from attack by each other.
Given the list of integers 2,-10, 12, 25, -32, 22, 56, 5, you are required to find the element whose rank is 4. This is the element whose index is 4, when the list is sorted in increasing order and indexed from 1 to 8. You are not allowed to sort the entire list; instead, you must use the PARTITION procedure discussed in class for QuickSort to partition the above list, determine which list contains the element you are looking for and recursively continue with this abbreviated list. Make a table with two columns: the first column enumerates the list in which the element lies and the second column states its rank in this list. Thus the first (and trivial) row entry would have the above list in the first column and 4 in the second column.
In C++, Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 20 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in the blank, etc ( Like prior program done with LISTS ) Create a class called Node: Have a Name and Priority. Data set - 1 is the highest priority, 10 is lowest priority. Enqueue and dequeue in the following order. Function Name, Priority Enqueue Joe, 3 Enqueue Fred, 1 Enqueue Tuyet, 9 Enqueue Jose, 6 Dequeue Enqueue Jing, 2 Enqueue Xi, 5 Enqueue Moe, 3 Dequeue Enqueue Miko, 7 Enqueue Vlady, 8 Enqueue Frank, 9 Enqueue Anny, 3 Dequeue Enqueue Xi, 2 Enqueue Wali, 2 Enqueue Laschec, 6 Enqueue Xerrax, 8 Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue…