手写堆栈 队列 c++

一.堆栈

1.数组实现

#include <iostream>
using namespace std;
const int maxx=1e5;
template <class T>
class stack{
public:
    T stk[maxx];
    int top;
    stack(){
        top=0;
    }
    bool stackfull();
    bool stacknull();
    void push(T x);
    T pop();
};
template <class T>
bool stack<T>::stackfull(){
    if(top==maxx-1) return 1;
    return 0;
}
template <class T>
bool stack<T>::stacknull(){
    if(top==0)  return 1;
    return 0;
}
template <class T>
T stack<T>::pop(){
    if(stacknull())  return 1;
    return stk[--top];
}
template <class T>
void stack<T>::push(T x){
    if(stackfull())  return ;
    stk[top++]=x;
}
int main()
{
    stack<double> st;
    st.push(1.1);
    st.push(2.2);
    st.push(3.3);
    while(!st.stacknull()){
        cout<<st.pop()<<endl;
    }
    return 0;
}

2.单向链表实现

#include <iostream>
using namespace std;
class list{
public:
    list *head;
    list *tail;
    list *next;
    int num;
    list(){
        head=tail=next=NULL;
    }
    virtual void push(int x)=0;
    virtual int pop()=0;
};
class stack:public list{
public:
    void push(int x);
    int pop();
};
void stack::push(int x){
    list *noww;
    noww=new stack;
    if(!noww){
        cout<<"error"<<endl;
        return ;
    }
    noww->num=x;
    if(head)  noww->next=head;
    head=noww;
    if(!tail)  tail=head;
}
int stack::pop(){
    int x;
    list *p;
    if(!head){
        cout<<"empty"<<endl;
        return 0;
    }
    x=head->num;
    p=head;
    head=head->next;
    delete p;
    return x;
}
int main()
{
    list *p;
    stack aa;
    p=&aa;
    p->push(1);
    p->push(2);
    p->push(3);
    cout<<p->pop()<<endl;
    cout<<p->pop()<<endl;
    cout<<p->pop()<<endl;
    return 0;
}

二.队列

1.数组实现

#include <iostream>
using namespace std;
const int maxx=1e5;
template <class T>
class queue{
public:
    T quee[maxx];
    int head;
    int tail;
    queue(){
        head=tail=0;
    }
    bool queuefull();
    bool queuenull();
    void push(T x);
    T pop();
};
template <class T>
bool queue<T>::queuefull(){
    if(tail==maxx && head!=tail)  return 1;
    return 0;
}
template <class T>
bool queue<T>::queuenull(){
    if(head==tail && head==maxx) return 1;
    return 0;
}
template <class T>
void queue<T>::push(T x){
    if(queuefull()) return ;
    quee[tail++]=x;
}
template <class T>
T queue<T>::pop(){
    if(queuenull()) return 1;
    return quee[head++];
}
int main()
{
    queue<int> que;
    que.push(1);
    que.push(2);
    que.push(3);
    while(!que.queuenull()){
        cout<<que.pop()<<endl;
    }
    return 0;
}

2.单向链表实现

#include <iostream>
using namespace std;
class list{
public:
    list *head;
    list *tail;
    list *next;
    int num;
    list(){
        head=tail=next=NULL;
    }
    virtual void push(int x)=0;
    virtual int pop()=0;
};
class queue:public list{
public:
    void push(int x);
    int pop();
};
void queue::push(int x){
    list *noww;
    noww=new queue;
    if(!noww){
        cout<<"error"<<endl;
        return ;
    }
    noww->num=x;
    if(tail)  tail->next=noww;
    tail=noww;
    noww->next=NULL;
    if(!head)  head=tail;
}
int queue::pop(){
    int x;
    list *p;
    if(!head){
        cout<<"empty"<<endl;
        return 0;
    }
    x=head->num;
    p=head;
    head=head->next;
    delete p;
    return x;
}
int main()
{
    list *p;
    queue aa;
    p=&aa;
    p->push(1);
    p->push(2);
    p->push(3);
    cout<<p->pop()<<endl;
    cout<<p->pop()<<endl;
    cout<<p->pop()<<endl;
    return 0;
}

一个简单的小例子

题目描述

输入

输出

样例输入

10 2

样例输出

1010

代码：

#include <iostream>
using namespace std;
const int maxx=1e3+10;
template <class T>
class stack{
public:
    int stk[maxx];
    int top;
    stack(){
        top=0;
    }
    bool stackfull();
    bool stacknull();
    void push(int x);
    T pop();
};
template <class T>
bool stack<T>::stackfull(){
    if(top==maxx-1)  return 1;
    return 0;
}
template <class T>
bool stack<T>::stacknull(){
    if(top==0)  return 1;
    return 0;
}
template <class T>
void stack<T>::push(int x){
    if(stackfull())  return ;
    stk[top++]=x;
}
template <class T>
T stack<T>::pop(){
    if(stacknull())  return 1;
    return stk[--top];
}
int main()
{
    stack<int> st;
    int n,d;
    cin>>n>>d;
    if(n==0){
        cout<<"0"<<endl;
        return 0;
    }
    while(n!=0){
        st.push(n%d);
        n/=d;
    }
    int p;
    while(!st.stacknull()){
        p=st.pop();
        if(d>10 && p>9){
            char ch='A'+(p-10);
            cout<<ch;
        }
        else  cout<<p;
    }
    cout<<endl;
    return 0;
}