Introduction to Algorithms
3rd Edition
ISBN: 9780262033848
Author: Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein
Publisher: MIT Press
expand_more
expand_more
format_list_bulleted
Question
Chapter 17.1, Problem 1E
Program Plan Intro
To decide whether it is possible to push k items onto the stack would require
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents have asked these similar questions
Problem Statement: We can store k stacks in a single array if we use the data structure suggested
in Figure 1 shown below, for the case k = 3. We push and pop from each stack as suggested in
connection with Figure 2 below. However, if pushing onto stack i causes TOP(i) to equal
BOTTOM(i – 1), we first move all the stacks so that there is an appropriate size gap between each
adjacent pair of stacks. For example, we might make the gaps above all stacks equal, or we might
make the gap above stack i proportional to the current size of stack i (on the theory that larger
stacks are likely to grow sooner, and we want to postpone as long as possible the next
reorganization).
1
stack 1
3
stack 2
bottom
stack 3
3
top
stackspace
Figure 1
top
first element
second element
maxlength
last element
elements
The pseudocode of Figure 6.16 illustrates the basic push() and pop() operations of an array-based stack. Assuming that this algorithm could be used in a concurrent environment, answer the following questions:a. What data have a race condition?b. How could the race condition be fixed?
Two stacks S1 and S2 are to be stored in a single array A[1:n], with
PushS1 (x) and PushS2 (x) handling their respective push operations with
regard to element x and PopS1 (x) and PopS2 (x) handling their respective pop
operations, with the output variable x indicating the element popped out from the
stack. Let TopS1 and TopS2 be their respective top-of-stack variables. The stacks
share their storage space in such a way that their respective bottom of stacks are
positioned in the middle of the array, as shown in Figure P4.1, and the stacks grow
in the opposite directions.
Array A:
[1]
[2] [3]...
Stack S₁
. [[n/2]][[n/2]+1] [n-2] [n-1] [n]
Bottom of
Stack S₁
PopS1 (w)
PopS2 (y)
PushS1 (y)
PushS2 (w)
Stack S₂
Figure P4.1. Two stacks are stored in a single array A with
the bottom of stacks positioned in the middle of the array
PopS2 (y)
PopS2 (w)
Bottom of
Stack S₂
i) For n = 5, if S1 = {a, b} and S2 = {m, n}, how would array A look after all of
the elements of stacks S1 and S2 were…
Knowledge Booster
Similar questions
- A stack of integer elements is implemented as an array. The index of the topelement is kept in position 0 in the array, and the stack elements are stored in stack[1], …,stack[stack[0]].1. How does this implementation fare when assessed against the idea of an array as ahomogeneous collection of data elements?2. How would this implementation change the stack specification?3. How would it change the implementation of the functions?arrow_forward3. A stack can be implemented with an array A[0..N-1] and a variable pos. The push and pop operations are defined by the following code. push (x) A[pos] + x 1. pos + pos end push pop () pos + pos + 1 return A[pos] end pop Which of the following will initialize an empty stack with capacity N for this implementation?arrow_forwardConsider the following infix expression.( 5 + 8 ) * 9 – 7 * 10 + 9.Apply infix-to-postfix conversion algorithm to generate the correspondingpostfix expression from the given infix expression. You have to show thecontent of stack at each stage of conversion.arrow_forward
- S1 and S2 are two sorted stacks of n and m numbers, with the top elements of each stack pointing to the smallest number in their list. To ensure that all of the components in stacks S1 and S2 are available in MERGE in decreasing order, with the largest element at the top, create a stack MERGE that combines the items in stacks S1 and S2.Remember that there are (n + m) components in the stack MERGE.arrow_forward1. Describe how to implement a queue using two stacks and O(1) additional memory, so that the amortized time for any enqueue or dequeue operation is O(1). The only access you have to the stacks is through the standard subroutines Push and Pop.arrow_forwardIt is known that when an information system processes data, a Linked Stack is used, and the name of the indicator pointing to the top of the stack is Top. When the input data enters the system, it needs to be stored in the stack first, and then the information system will extract the data from the stack to perform operations as required. it is known that the sequence of a set of integer data entering the aforementioned information system is as follows; 27, 98, 24, 9, 83 In the initial stage of the aforementioned information system, the Stack is in an empty state, and in the process of entering the above-mentioned integer data string into the information system, the operation sequence of the Stack is as follows; Push, Push, Pop, Push, Push, Push, Pop Please diagrammatically depict the Linked Stack of the information system at each stage of operationarrow_forward
- Let S1, S2 and S3 be three stacks with |S1|=|S2|=|S3|= n (i.e) all of them will have same capacity. Assume that only two of the stacks are filled to the capacity with arbitrary non-negative integers and one of them is empty. Re-arrange the elements in the stack so that even integers are placed in one stack and odd integers in another stack. In case the number of even elements exceeds the number of odd elements, then the extra odd elements that do not fit onto one stack can be placed on the third. The case where odd elements are greater than even is analogous.arrow_forwardWhen a stack segment is initialized then SS and SP are initialized O only SS is initialized O only SP is initialized SS and SP need not be initialized )arrow_forwardStudy the scenario and complete the question(s) that follow: A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle while a queue is a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle. A typical example of a stack may include an internet web browsers store the addresses of recently visited sites on a stack. Each time a user visits a new site, that site's address is "pushed" onto the stack of addresses. The browser then allows the user to "pop" back to previously visited sites using the "back" button. 3.1 Develop an application that store characters A, B and C in a stack array and then displays both the size and the last-in element of the stack. The application should then remove the last element of the stack and then display again both the size and the last-in element of the stack. Appropriate stack methods should be used to add, delete and display characters.arrow_forward
- Write a code/algorithm, which takes two sorted integer stacks ‘intstack_1’ and ‘intstack_2’ (with minimum value on ‘top’ and the maximum value at the bottom) as input. The algorithm should output a single sorted stack ‘result_stack’ of all the values (with the minimum value on ‘top’ and the maximum value at the bottom). The algorithm should fulfill the following constraints: Only stack operations are allowed, and they are already implemented (pop, push, top, isEmpty, isFull etc.). No other data structure is allowed except stack. The algorithm must work correctly for input stacks of different sizes. [Hint: you will have to use an additional stack.]arrow_forward(i) Suppose an initially empty stack S has executed a total of 30 push operations,20 top operations, and 18 pop operations, 8 of which raised Empty errors that were caught and ignored. What is the maximum and current size of S? Clearly write how you calculated the current size of S based on the stack operations. How many overflow errors would have occurred during the push operations?arrow_forwardQuestion 3 Convert the following infix notation to its postfix notation. You must show the stack contents in your simulation. z* 5 == [9 *r != {(4 > c / 8) || (2 *r =,> ==, != && || (low)arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
- C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning