假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
c#中的解决方案
public class Queue<T> where T : class
{
private Stack<T> input = new Stack<T>();
private Stack<T> output = new Stack<T>();
public void Enqueue(T t)
{
input.Push(t);
}
public T Dequeue()
{
if (output.Count == 0)
{
while (input.Count != 0)
{
output.Push(input.Pop());
}
}
return output.Pop();
}
}
其他回答
队列中的两个堆栈定义为stack1和stack2。
排队: euqueued的元素总是被推入stack1
出列: stack2的顶部可以被弹出,因为它是在stack2不为空时插入队列的第一个元素。当stack2为空时,我们从stack1中弹出所有元素,并将它们逐个推入stack2。队列中的第一个元素被压入stack1的底部。由于它位于stack2的顶部,所以在弹出和推入操作后可以直接弹出。
下面是相同的c++示例代码:
template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T> void CQueue<T>::appendTail(const T& element) {
stack1.push(element);
}
template<typename T> T CQueue<T>::deleteHead() {
if(stack2.size()<= 0) {
while(stack1.size()>0) {
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size() == 0)
throw new exception("queue is empty");
T head = stack2.top();
stack2.pop();
return head;
}
这个解决方案是从我的博客中借来的。我的博客网页上有详细的操作模拟分析。
在Swift中使用两个堆栈的队列实现:
struct Stack<Element> {
var items = [Element]()
var count : Int {
return items.count
}
mutating func push(_ item: Element) {
items.append(item)
}
mutating func pop() -> Element? {
return items.removeLast()
}
func peek() -> Element? {
return items.last
}
}
struct Queue<Element> {
var inStack = Stack<Element>()
var outStack = Stack<Element>()
mutating func enqueue(_ item: Element) {
inStack.push(item)
}
mutating func dequeue() -> Element? {
fillOutStack()
return outStack.pop()
}
mutating func peek() -> Element? {
fillOutStack()
return outStack.peek()
}
private mutating func fillOutStack() {
if outStack.count == 0 {
while inStack.count != 0 {
outStack.push(inStack.pop()!)
}
}
}
}
使用两个java.util.Stack对象实现队列:
public final class QueueUsingStacks<E> {
private final Stack<E> iStack = new Stack<>();
private final Stack<E> oStack = new Stack<>();
public void enqueue(E e) {
iStack.push(e);
}
public E dequeue() {
if (oStack.isEmpty()) {
if (iStack.isEmpty()) {
throw new NoSuchElementException("No elements present in Queue");
}
while (!iStack.isEmpty()) {
oStack.push(iStack.pop());
}
}
return oStack.pop();
}
public boolean isEmpty() {
if (oStack.isEmpty() && iStack.isEmpty()) {
return true;
}
return false;
}
public int size() {
return iStack.size() + oStack.size();
}
}
对于c#开发人员,这里是完整的程序:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QueueImplimentationUsingStack
{
class Program
{
public class Stack<T>
{
public int size;
public Node<T> head;
public void Push(T data)
{
Node<T> node = new Node<T>();
node.data = data;
if (head == null)
head = node;
else
{
node.link = head;
head = node;
}
size++;
Display();
}
public Node<T> Pop()
{
if (head == null)
return null;
else
{
Node<T> temp = head;
//temp.link = null;
head = head.link;
size--;
Display();
return temp;
}
}
public void Display()
{
if (size == 0)
Console.WriteLine("Empty");
else
{
Console.Clear();
Node<T> temp = head;
while (temp!= null)
{
Console.WriteLine(temp.data);
temp = temp.link;
}
}
}
}
public class Queue<T>
{
public int size;
public Stack<T> inbox;
public Stack<T> outbox;
public Queue()
{
inbox = new Stack<T>();
outbox = new Stack<T>();
}
public void EnQueue(T data)
{
inbox.Push(data);
size++;
}
public Node<T> DeQueue()
{
if (outbox.size == 0)
{
while (inbox.size != 0)
{
outbox.Push(inbox.Pop().data);
}
}
Node<T> temp = new Node<T>();
if (outbox.size != 0)
{
temp = outbox.Pop();
size--;
}
return temp;
}
}
public class Node<T>
{
public T data;
public Node<T> link;
}
static void Main(string[] args)
{
Queue<int> q = new Queue<int>();
for (int i = 1; i <= 3; i++)
q.EnQueue(i);
// q.Display();
for (int i = 1; i < 3; i++)
q.DeQueue();
//q.Display();
Console.ReadKey();
}
}
}
使用堆栈实现队列的以下操作。
push(x)——将元素x推到队列的后面。
pop()——从队列前面移除元素。
peek()——获取前端元素。
empty()——返回队列是否为空。
class MyQueue {
Stack<Integer> input;
Stack<Integer> output;
/** Initialize your data structure here. */
public MyQueue() {
input = new Stack<Integer>();
output = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
}
/** Get the front element. */
public int peek() {
if(output.isEmpty()) {
while(!input.isEmpty()) {
output.push(input.pop());
}
}
return output.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return input.isEmpty() && output.isEmpty();
}
}