Meng Yan (孟岩) @ SUN Personal Opinions Only

How to implement queue with stack?

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).