如何使用两个堆栈（LIFO），以便它可以像一个队列（FIFO）？ [英] How can i use two stacks(LIFO) so that it can work like a queue(FIFO)?

问题描述

我有两个堆栈（它遵循LIFO）。我想知道如果我可以写一个C程序使用这两个协议栈的工作就像一个队列（FIFO）。

I have two stacks(which follows LIFO). I would like to know if i can write a C program to use these two stacks work like a queue(FIFO).

推荐答案

一层堆栈，用于插入新的元素到队列中。其他堆栈用来删除元素。当输出堆栈为空，则输入堆栈反转，成为新的输出叠层

One stack is used to insert new elements into the queue. The other stack is used to remove elements. When the output stack is empty, the input stack is reversed and becomes the new output stack.

在伪C：

typedef struct { stack in, stack out } queue.

void insert(queue *q, void *data) {
  push(q->in, data);
}

void* remove(queue *q) {
  if (empty(q->out)) {
    while (!empty(q->in)) { // q->out = reversed q->in
      push(q->out, pop(q->in)); 
    }
  }
  return pop(q->out);  // assumes that it returns NULL if q->out is empty
}

这是渐近相同的复杂作为常规队列，但是每个元件被触摸数次。既然你用C的工作，为什么不使用常规的环形缓冲区？

This is asymptotically the same complexity as a regular queue, but each element is touched several times. Since you're working in C, why not use a regular ring-buffer?

的修改的：这确实是Okasaki的功能队列的工作，@ bdonlan的回答中提到的方法

Edit: This is indeed the way Okasaki's functional queues work that @bdonlan's answer mentioned.

这篇关于如何使用两个堆栈（LIFO），以便它可以像一个队列（FIFO）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！