stack

顺序栈

利用数组，进行栈的操作

（待补充

链式栈

利用链表，进行栈的操作，基本不用担心栈溢出。但是需要手动释放结点内存。

这里用进栈用头插法。

（待补充

queue

顺序队列

使用数组实现，有假溢出的情况，空间利用率低。

循环队列

解决了假溢出，空出一个空间判断队列是否已满。

#include <iostream>

using namespace std;
class queue{

public:
    int *q,qSize;
    //尾指针，头指针
    int top{0},end{0};
    
    //初始化队列长度
    queue(int qSize){
        this->qSize = qSize;
        q = new int[qSize];
    }
    int front(){
        return q[top];
    }

    int pop(){
        if(isEmpty()){
            cerr << "Empty queue" << endl;
            return -1;
        }
        int ans = q[top];
        top= (top+1)%qSize;
        return ans;
    }

    void push(int i){
        if(isOversize()){
            cerr << "Oh! my size is max."<<endl;
            return ;
        }
        q[end] = i;
        end = (end+1)%qSize;
    }

    bool isEmpty(){
        return top==end;
    }
    //end+1是否等于top
    bool isOversize(){
        if((end+1)%qSize==top)return true;
        return false;
    }

};

int main()
{
    queue myQueue(5);
    
    //5个存储空间最多只能放4个数，所以会overSize提醒
    for(int i=0;i<5;i++){
        myQueue.push(i+10);
    }

    cout<<myQueue.front()<<endl;
    myQueue.pop();
    cout<<myQueue.front()<<endl;
    myQueue.pop();
    cout<<myQueue.front()<<endl;
    myQueue.push(521);
    myQueue.push(1314);
    cout<<myQueue.front()<<endl;
    myQueue.pop();
    cout<<myQueue.front()<<endl;
    myQueue.pop();
    cout<<myQueue.front()<<endl;
    myQueue.pop();
    cout<<myQueue.front()<<endl;

    return 0;
}

链队

用链表实现队列，不用担心队列长度是否已满。

#include <iostream>


using namespace std;

class node {
public:
    int val{0};
    node* next = nullptr;

    node() = default;
    node(int val) : val(val){
    }

    node(int val,node* next) : val(val), next(next){}

};

class queue{
public:
    node * head = new node;
    node* front = head;
    node* end = head;

    queue() = default;
    void push(int x){
        node * temp = new node(x);
        end->next = temp;
        end = end->next;
    }

	//	只需front的next只需下一个的下一个
    void pop(){
        if(isEmpty()){
            clog<<"Empty queue"<<endl;
            return ;
        }
        node* t = front->next;
        front->next = t->next;
        //如果只有一个结点，要把end=front
        if(t==end){
            end = front;
        }
        delete t;
    }
    int top(){
        if(isEmpty()){
            clog<<"Empty queue"<<endl;
            return -1;
        }
        return front->next->val;
    }

    bool isEmpty(){
        return front==end;
    }
    void destroy(){
        node* t ;
        while(front->next!=nullptr){
            t = front->next;
            front->next = t->next;
            delete t;
        }
        end = front;
    }
};



int main()
{
    queue me;
    
    me.pop();
    me.push(1213);
    me.push(429);
    cout<<me.top()<<endl;
    me.pop();
    cout<<me.top()<<endl;
    me.push(1213);
    me.push(429);
    me.push(1213);
    me.push(429);
    me.destroy();
    me.pop();
    cout<<me.top()<<endl;
    return 0;
}