How to implement queue with stack?
Interesting topic, right? One of my friends encounter this problem when he’s applying software engineer position in a company.
Suppose we have only stack available
Stack* stack_init();
void push(Stack*, int);
int pop(Stack*);
void stack_free();Please implement the following interface of queue
Queue* queue_init();
void inq(Queue*, int);
int outq(Queue*);
void queue_free();
Any idea, buddy? Here come 3 solutions:
1) By Winters Mi
- Stack* stack_init();
- void push(Stack*, int);
- int pop(Stack*);
- void stack_free(Stack*);
- struct Queue {
- struct Stack* stack_;
- }
- Queue* queue_init()
- {
- Queue* queue = new Queue;
- queue->stack_ = stack_init();
- }
- void inque(Queue* que, int newvalue)
- {
- Stack* temp = stack_init();
- int value;
- while((value = pop(que->stack_) != EOF){
- push(temp, value);
- }
- push(que->stack_, newvalue);
- while((value = pop(temp)) != EOF){
- push(que->stack_, value);
- }
- }
- int outque(Queue* que)
- {
- pop(que->stack_);
- }
- void queue_free(Queue* que)
- {
- stack_free(que->stack_);
- delete que;
- }
So, it’s a O(N) solution.
2) By Green Wang
- struct Queue
- {
- struct Stack *stack_forward;
- struct Stack *stack_backward;
- int iStack;
- }
- Queue* queue_init()
- {
- Queue* que = new Queue;
- que->stack_forward = stack_init();
- que->stack_backward = stack_init();
- que->iStack = 1;
- return que;
- }
- void stack_reverse(Stack *dest, Stack *src)
- {
- int value;
- while((value = pop(src) != EOF)
- {
- push(dest, value);
- }
- }
- void inque(Queue *que, int newvalue)
- {
- if (que->iStack != 1)
- {
- stack_reverse(que->stack_forward, que->stack_backward);
- que->iStack = 1;
- }
- push(que->stack_forward, newvalue);
- }
- int outque(Queue *que)
- {
- if (que->iStack != -1)
- {
- stack_reverse(que->stack_backward, que->stack_forward);
- que->iStack = -1;
- }
- return pop(que->stack_backward)
- }
- void queue_free(Queue* que)
- {
- stack_free(que->stack_forward);
- stack_free(que->stack_backward);
- delete que;
- }
If the operation of the queue is consecutive "in" or "out", it’s O(1); Or else O(n). This algorithm overcomes the shortcoming of the first one. Because if the operation is consecutive, we don’t need to reverse the stack back.
3) By Changzheng Liu
- /* create the type Queue by Stack */
- typedef struct {
- Stack* stack_out;
- Stack* stack_in;
- } Queue;
- /* Init Queue */
- Queue* queue_init()
- {
- Queue* que = (Queue*)malloc(sizeof(Queue));
- que->stack_out = stack_init();
- que->stack_in = stack_init();
- return que;
- }
- /* reverse the elements from src to dest */
- void stack_reverse(Stack *dest, Stack *src)
- {
- int value;
- while((value = pop(src) != EOF)
- {
- push(dest, value);
- }
- }
- /* put element into queue */
- void inque(Queue* que, int elem)
- {
- /* always push elements into stack_in */
- push(que->stack_in, elem);
- }
- /* get the element from queue */
- int outque(Queue* que)
- {
- int ret;
- /* always get element from stack_out,
- * if stack_out is empty, reverse stack_in to stack_out and try to pop from stack_out again
- */
- if ((ret = pop(que->stack_out)) == EOF)
- {
- stack_reverse(que->stack_out, que->stack_in);
- ret = pop(que->stack_out);
- }
- return ret;
- }
- /* free the queue */
- void queue_free(Queue* que)
- {
- stack_free(que->stack_out);
- stack_free(que->stack_in);
- free(que);
- }
Changzheng got these code from Google. :P. It’s really good. The idea is very simple, 2 stacks, one for in and one for out. For the "in" operation, just push all into the stack_in. For the "out" operation, if stack_out is empty, reverse the stack_in to stack_out, or else just pop the value.
So for "in" operation O(1); for "out" operation, if stack_out is empty, it’s O(n), else O(1).
Popularity: 28%
Related entries:
- No Related Posts
November 18th, 2007 at 3:01 am
How To Start A Blog…
I couldn’t understand some parts of this article, but it sounds interesting…