两个栈实现队列 (C++)

概述

栈先进后出，一般用数组实现
队列先进先出，一般用链表实现
考虑到最终目的是实现队列，自定义栈，使用链表结构

原理

参照How to implement a queue using two stacks?

代码：

void push_back(E it)
{
	inbox.push(it);
	size++;
}

E pop_front()
{
	if (outbox.empty())
	{
		while (!inbox.empty())
		{
			outbox.push(inbox.pop());
		}
	}
	size--;
	return outbox.pop();
}

Code

stl stack

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

template <typename E>
class Queue
{
private:
    stack<E> inbox;
    stack<E> outbox;

public:
    int size = 0;

    void push_back(E it)
    {
        inbox.push(it);
        size++;
    }

    E pop_front()
    {
        if (outbox.empty())
        {
            while (!inbox.empty())
            {
                E tmp = inbox.top();
                outbox.push(tmp);
                inbox.pop();
            }
        }
        size--;
        E tmp = outbox.top();
        outbox.pop();
        return tmp;
    }
};

int main()
{
    Queue<int> que;
    //push 01234
    for (int i = 0; i < 5; i++)
    {
        que.push_back(i);
    }
    //pop 012
    for (int i = 0; i < 3; i++)
    {
        cout << que.pop_front() << endl;
    }
    //push 78
    for (int i = 7; i < 9; i++)
    {
        que.push_back(i);
    }
    //pop all left elements (3478)
    int len = que.size;
    for (int i = 0; i < len; i++)
    {
        cout << que.pop_front() << endl;
    }

    return 0;
}

自实现Stack版本

#include <iostream>
using namespace std;

//Linked Node
template <typename E>
class Node
{
public:
	E data;
	struct Node<E> *next;
	Node<E>()
	{
		next = NULL;
	}

	Node(E it, Node<E> *_next)
	{
		data = it;
		next = _next;
	}
};
//Linked Based Stack
template <typename E>
class Stack
{
private:
	Node<E> *head;
	int size;
	void init()
	{
		head = new Node<E>;
		size = 0;
	}
public:
	Stack()
	{
		init();
	}
	bool empty()
	{
		return size == 0;
	}
	E top()
	{
		return head->data;
	}
	void push(E it)
	{
		head = new Node<E>(it, head);
		size++;
	}
	E pop()
	{
		E tmp = top();
		size--;
		Node<E> *temphead = head;
		head = head->next;
		delete temphead;
		return tmp;
	}
};
//Queue implement
template <typename E>
class Queue
{
private:
	Stack<E> inbox;
	Stack<E> outbox;

public:
	int size = 0;

	void push_back(E it)
	{
		inbox.push(it);
		size++;
	}

	E pop_front()
	{
		if (outbox.empty())
		{
			while (!inbox.empty())
			{
				outbox.push(inbox.pop());
			}
		}
		size--;
		return outbox.pop();
	}
};

int main()
{
	Queue<int> que;
	//push 01234
	for (int i = 0; i < 5; i++)
	{
		que.push_back(i);
	}
	//pop 012
	for (int i = 0; i < 3; i++)
	{
		cout << que.pop_front() << endl;
	}
	//push 78
	for (int i = 7; i < 9; i++)
	{
		que.push_back(i);
	}
	//pop all left elements (3478)
	int len = que.size;
	for (int i = 0; i < len; i++)
	{
		cout << que.pop_front() << endl;
	}

	return 0;
}