1

I implemented it as an array with two stacks adjacent to each other, but their tops on the either ends. That is, if top(stack1) is at the beginning of keys, top(stack2) is at the end of keys. Bottom(Stack1) and Bottom(Stack2) should be adjacent, but anywhere between top(Stack1) and top(Stack2). To delete, I am poping from Top(Stack1), and for inserting, I am pushing in Top(stack2). Could somebody pls tell me if it is correct to do it this way?

When I read CLRS, I solved the que this way, and had no way to know that it was ryt or not. But it was asked in today's exam, and everyone later on was discussing the way given officially (here and everywhere else on net), so it seems I am the only one to do it such a way. I really wanna know if this is wrong or right ? Please help

Improve this question

4 Answers 4

Reset to default
1

Queues and stacks are abstract data structures which have well defined behaviors and any implementation of these data structures should respect this contract.

Your idea of using a single array to implement two stacks is good. But, the inserts and deletes should happen on both stacks.

For eg. lets say you have this setup

2 3 4 5 6

top(stack1) is 2
bottom(stack1) is 4
top(stack2) is 6
bottom(stack2) is 5

after popping from stack1 3 times you would have reached the bottom of your stack i.e 4 and no longer able to pop anything even though there are two more elements in your QUEUE implementation. So, a few corrections to your implementation is required.

So, if I were to implement two stacks which emulate a QUEUE, this is how I would do it.

Stack1: 2 3 4 5 6 which is essentially an array
2 is the bottom of the stack and 6 is the top of the stack.

Stack2: empty

Insert an element to Queue:
This is very simple. Just add to the end of array i.e stack1
stack1:2 3 4 5 6 7
Now 7 is the top of the stack.

Delete an element from Queue:
1. Pop all elements in stack1 and insert them to stack2. So, your array will be reversed
stack1:empty
stack2: 7 6 5 4 3 2 . Now 2 is at the top of the stack.
2. Now your top(stack2) will be pointing to 2. Just pop it. 7 6 5 4 3
3. Now for the remaining elements in stack2, pop from stack2 and insert them to stack1.
stack2:empty
stack1:3 4 5 6 7

PS: The above algorithm assumes that you know how to manage memory for arrays as it shrinks or expands.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

thanx for d answer. although i hv not specified in my algorithm in the answersheet about bottom (Stack1) or Bottom(Stack2). I hv just put the condition if(Top1<=Top2) for deletion and if(Top2<N) for insertion, since we had have not been taught resizable arrays. well, as u said, it all depends on the evaluator now. thnx anyways
Raymond, please use the proper English language. This is an English forum, not a cryptoenglish one.
@AI Kepp: I dont get you. Which lines are talking of are cryptoenglish ?
@srikfreak : Yes sir, I know the way you mentioned is the one probably sir was looking for. But I didnt try to think of it, because it never came to my mind that the one I arrived at (it was so natural to me) could possibly be wrong. I ll do by this method next time ownwards though...
Raymond, you should write THE instead of D, HAVE instead of HV, RIGHT instead of RYT etc. Is it hard for you to imagine that many people around the world have problems to understand your fancy language?
|
0

I think you actually can implement a queue using two adjacent stacks as you described. The problem is that you cannot implement those two adjacent stacks with an array efficiently. I mean your queue seems OK, but when you try to use the underlying stacks, you encounter the problem how to insert a new item at the beginning of the array (i.e. push to stack1). You need to move (copy) all items in your array to push an item into stack1. And that's ill design.

Improve this answer

1 Comment

That is it. I have made up my mind to insert at end and delete at beginning of the array. Because that is how a queue works, right ? Insertion and deletion at different ends. I am using the pop property of Stack 1 and Push property of Stack 2, to make the array behave as queue.
0

For those who are looking for the solution, a sample one is this:

Let's say we have two stacks S1 and S2.
A queue has the given two behaviours:

  1. Enqueue: Insert an element into the queue. For this, simply push into S1.
  2. Dequeue: Pop all elements from from S1 one by one, simultaneously pushing them into S2. Now pop from S2. The popped element is the desired result of Dequeue.

Readers are encouraged to find more optimized solutions to this and post them here if possible :)

Improve this answer

Comments

0

Here is an example in python using the built in array/list for two stacks.

class Queue2Stacks(object):

    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, element):
        self.in_stack.append(element)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()
Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.