16
$\begingroup$

I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and exercises given in the book by myself.

I am trying to solve Excercise 10.1-2 from Chapter 10 Elementary Data Structures from CLRS Second Edition. Here is what its states:

Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The solution that I have come up with so far is:

Let array A[1..n] implement two stacks: S1[1..i] and S2[i..n].

For the PUSH-S1 and PUSH-S2 operations, if the stack is 'full' then start pushing elements into the other stack (eg. if stack S1 is full when a new element is trying to be pushed in, then push that element into stack S2 and vice versa).

The problem with this approach is I will not be able to POP-S1 or POP-S2 reliably as there is no way of 'remembering' which element belongs to which stack. If the elements of the stack are (key,value) pairs, the key being the stack number, then to pop an element I would have to search, in the worst case, i or (n-i) times - which will be O(n) (feel free to correct me if I am wrong here), which would not be O(1).

I have been banging my head on the question for quite a while now. Am I on the right track? Can someone give my possible pointers for solving this problem?

In general, how should I 'think' about these problems? Or can only really intelligent people solve these types of problems? Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?

I await enlightenment.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ "Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?" In my experience, this is definitely the case. If nothing else, you will have thought in multiple ways about the problem, and by that alone develop more insight. As I was recently told: the best way to have good ideas is to have many ideas. $\endgroup$
    – G. Bach
    Jul 28, 2013 at 15:15

7 Answers 7

Reset to default
7
$\begingroup$

Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays and fix their direction of growth accordingly. They don't have to grow in the same direction.

Improve this answer
$\endgroup$
5
$\begingroup$

Here are some hints:

  1. One of the stacks should grow "up" and the other "down".
  2. There is no way of 'remembering' which element belongs to which stack - you are allowed to use additional variables to help you with stuff like that. (This makes more sense with the solution proposed by the first hint.)
Improve this answer
$\endgroup$
1
$\begingroup$

The first stack starts at 1 and grows up towards n, while the second starts form n and grows down towards 1. Stack overflow happens when an element is pushed when the two stack pointers are adjacent.

Improve this answer
$\endgroup$
1
$\begingroup$

This method efficiently utilizes the available space. It doesn’t cause an overflow if there is space available in arr[]. The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.

Improve this answer
$\endgroup$
-1
$\begingroup$

I thought of another solution. If we split the array into half (or as close as possible if the array has odd length) and make the first element go into the first stack and the second element go into the second stack. While popping we could retrace these steps. However, by implementing in this way would it violate any stack principle?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science! Unfortunately, your proposal doesn't work. In an array of length $N$, you're supposed to be able to store two stacks that won't overflow unless their total size exceeds N (so it should be able to cope with an empty stack and a stack of length $N$). Your solution overflows if either one of the stacks exceeds $N/2$. $\endgroup$
    – David Richerby
    Jan 10, 2015 at 15:08
-1
$\begingroup$

I guess there are many solutions to this problem. For the particular case of 2 stacks in one array, I like the solution of starting one stack at the first index and the second one at the last index. As the stacks grow, you know the array is full when the heads of each stack are adjacent.

However, you could implement this the same way as implementing K stacks in 1 array. If you store a queue with the free slots available, you have everything you need. For instance, you would know in which slot you would add your next value (independently from the stack you are pushing to). Everytime you push or pop a value, you pop or push a free slot, respectively. Storing such a queue might be considered overhead, still, the space complexity would remain the same.

The only thing you would have to do is to properly set the pointers (or indexes, after all, we are using an array).

Here is a short description, space complexity O(N) where N is the size of the array. Pop/push complexities O(1).

1) initialize a queue holding the free slots from 0 to N - 1.
2) initialize the heads of all the stacks to -1 (the stacks are empty)
3) POP: given a stack, set the head of that stack to the next element
   pointed to by the current head, and then remove the current head.
   Enqueue the index of the slot which just came free to the queue of free slots.
4) ADD: get the next available index from the queue of free slots.
   Create your new node in the new slot, and make it point to the current 
   head of that stack. Then set the current head of that stack to the newly added node.
Improve this answer
$\endgroup$
8
  • $\begingroup$ This looks answer looking for a problem, and coding algorithms isn't on topic with CS.SE. $\endgroup$
    – greybeard
    Sep 29, 2020 at 7:18
  • $\begingroup$ @greybeard Didn't know about the coding part, I'll adjust. About the other part I think it's irrelevant and incorrect. I've been reading a lot of solutions to this problem and thought it might be useful to share my point of view. $\endgroup$
    – mfnx
    Sep 29, 2020 at 7:40
  • $\begingroup$ This solution doesn't meet the requirements listed in the question, since it increases the amount of space needed by a constant factor, e.g., by 2x, which isn't allowed per the requirements in the question. The question asks "in such a way that neither stack overflows unless the total number of elements in both stacks together is n". Not $\Theta(n)$, not $n/2$, but $n$. $\endgroup$
    – D.W. ♦
    Sep 29, 2020 at 19:24
  • $\begingroup$ @D.W. no it does not increase the space needed. There will be only overflow if the array is full, and the array will be full if and only if the sum of the sizes of the stack is n. I guess you didn't understand well how the queue of available slots works. $\endgroup$
    – mfnx
    Sep 29, 2020 at 19:31
  • $\begingroup$ It appears you need extra space for the queue. Each "node" has a value and an index, which takes double the space; thus given n words, we can store only about n/2 values. If that isn't correct, please edit your answer to give an analysis of the space usage. You say in your own answer that space complexity is O(n), but O(n) isn't good enough; the question requires space complexity n, not O(n). $\endgroup$
    – D.W. ♦
    Sep 29, 2020 at 19:36
-2
$\begingroup$

Some hints

Make an array

Array elements with odd index are for stack1

Array elements with even index are for stack2

Now You can grow both stacks from left to right direction

Just keep variables that maintain top position of both stacks. You won't have to search the array.

and if stack1 becomes full while stack2 is empty you can keep track for additional stack1 elements in the stack2 by maintaining some variables

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is very convoluted. The existing answers already give much simpler ways of solving the problem $\endgroup$
    – David Richerby
    Jan 10, 2015 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.