假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
对于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();
}
}
}
其他回答
您必须从第一个堆栈中取出所有元素来获取底部元素。然后在每次“出队列”操作时将它们都放回第二个堆栈。
使用两个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();
}
}
使用O(1) dequeue(),这与pythonquick的答案相同:
// time: O(n), space: O(n)
enqueue(x):
if stack.isEmpty():
stack.push(x)
return
temp = stack.pop()
enqueue(x)
stack.push(temp)
// time: O(1)
x dequeue():
return stack.pop()
使用O(1) enqueue()(这在本文中没有提到,所以这个答案),它也使用回溯来冒泡并返回最底部的项。
// O(1)
enqueue(x):
stack.push(x)
// time: O(n), space: O(n)
x dequeue():
temp = stack.pop()
if stack.isEmpty():
x = temp
else:
x = dequeue()
stack.push(temp)
return x
显然,这是一个很好的编码练习,因为它效率很低,但仍然很优雅。
我的PHP解决方案
<?php
$_fp = fopen("php://stdin", "r");
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
$queue = array();
$count = 0;
while($line = fgets($_fp)) {
if($count == 0) {
$noOfElement = $line;
$count++;
continue;
}
$action = explode(" ",$line);
$case = $action[0];
switch($case) {
case 1:
$enqueueValue = $action[1];
array_push($queue, $enqueueValue);
break;
case 2:
array_shift($queue);
break;
case 3:
$show = reset($queue);
print_r($show);
break;
default:
break;
}
}
?>
在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()!)
}
}
}
}