链表和队列

文章目录

关于模板类的详细说明，参考

#include <iostream>
#include<stack>
#include<stdlib.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
template<typename T> class CQueue{
	public:
		CQueue(void){};
		~CQueue(void){};
		void appendTail(const  T& node);
		 T deleteHead();
		void output();
	private:
		stack<T> stack1;
		stack<T> stack2;
};

//插入元素
template <typename T> void CQueue<T>::appendTail(const T& node)
{
    stack1.push(node);
}
//删除元素并返回
template <typename T> T CQueue<T>::deleteHead()
{
    if(stack2.size()<=0)
    {
        while(stack1.size()>0)
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
    }
    if(stack2.size()==0)
        return 0;//throw  exception();
    T head=stack2.top();
    stack2.pop();
    return head;

}
template<typename T>void CQueue<T>::output(){
	while(stack1.size()>0){
		T temp=stack1.top();
		cout<<temp<<" ";
		stack1.pop();
	}
	cout<<endl;

}

int main(int argc, char** argv) {
    CQueue<int> queu;
    queu.appendTail(1);
    queu.appendTail(2);
    queu.appendTail(3);
    queu.appendTail(4);
    //queu.output();
    int len=4;
    while(len>0)
    {
        cout<<queu.deleteHead()<<endl;
        --len;
    }
	return 0;
}

接下来，实现两个队列完成栈的作用

#include<iostream>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;

template <typename T>class CStack
{
public:
    CStack(void){};
    ~CStack(void){};
    void addhead(const T& node);
    T delethead();
private:
    queue<T> queue1;
    queue<T> queue2;

};
template <typename T> void CStack<T>::addhead(const T& element){
    if(queue1.size()>0)
        queue1.push(element);
    else if(queue2.size()>0)
        queue2.push(element);
    else
        queue1.push(element);
}
//删除的实现更好理解一点
//画个图，会很直观
template <typename T> T CStack<T>::delethead(){
    if(queue2.size()==0){
        while(queue1.size()>1){
            queue2.push(queue1.front());
            queue1.pop();
        }
        T& head=queue1.front();
        queue1.pop();
        return head;
    }
    else{
        while(queue2.size()>1){
            queue1.push(queue2.front());
            queue2.pop();
        }
        T& head=queue2.front();
        queue2.pop();
        return head;
    }
}
int main(){
    CStack<char> s;
    s.addhead('a');
    s.addhead('b');
    s.addhead('c');
    cout<<s.delethead()<<endl;
    s.addhead('f');
    cout<<s.delethead()<<endl;

    return 0;
}