数据结构[栈与队列]的基本操作

首先大致说一下栈这个数据结构，他是一个先进后出的结构，就好比家中摆盘子一样，洗好的盘子放到最上面，当要用的时候从最上面拿走（当然只是一般情况，你要是每次都从下面抽走盘子我也没办法）。
这样的话我们可以直接用前面学过的线性表来实现，但是链的哪边是top呢？仔细分析一下就会发现如果我们用链的结尾作为top，我们删除它（因为这是一个单链表，指针只指向下一个元素），所以当我们用结尾作为top，删除元素后，找不到上一个元素的地址在哪。

struct Snode{
    int date;
    Snode *next;
};
typedef Snode* Stack;

栈的基本操作：
1.创建栈的头节点

Stack creat(){
    Stack s;
    s=new Snode;
    s->next=NULL;
    return s;
}

2.判断是否为空栈

bool isempty(Stack s){
    return s->next==NULL;
}

3.插入元素

void push(int val,Stack s){
    Stack node;
    node=new Snode;
    node->date=val;
    node->next=s->next;
    s->next=node;
}

4.删除元素并返回删除元素的值

int pop(Stack s){  
    Stack firstval;
    int val;
    if(isempty(s)){
        cout<<"堆栈空"<<endl;
        return NULL;
    }
    else{
        firstval=s->next;
        s->next=firstval->next;
        val=firstval->date;
        free(firstval);
        return val;
    }
}

以上就是堆栈的基本操作了。

队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
1.创建操作

struct node{
    int date;
    node *next;
};
struct Qnode{
    node *rear;
    node *front;
};
typedef Qnode *Queue;

Queue creat(){
    Queue q;
    q=new Qnode;
    q->front=q->rear=NULL;
    return q;
}

2.插入操作

void push(int val,Queue q){
    node *p;
    p=new node;
    p->date=val;
    p->next=NULL;
    if(q->rear==NULL){  //这里特别重要！！
        q->rear=p;
        q->front=p;
        return ;
    }
    else{
        q->rear->next=p;
        q->rear=p;
    }

    return ;
}

3.出队操作

void del(Queue q){  //出队
    node* frontcell;
    int frontdate;
    if(q->front==NULL) {
        cout<<"empty"<<endl;
        return ;
    }
    frontcell=q->front;
    if(q->front==q->rear){
        q->front=q->rear=NULL;
    }
    else{
        q->front=q->front->next;
    }
    frontdate=frontcell->date;
    free(frontcell);
    cout<<frontdate<<endl;
    return ;
}

4.查看其中元素

void show(Queue q){
    if(q->front==NULL){
        cout<<"empty"<<endl;
        return ;
    }
    node *p;
    p=q->front;
    while(p!=NULL){
        printf("%d ",p->date);
        p=p->next;
    }
    cout<<endl;
    return ;
}

5.返回队首元素

int readfront(Queue q){
    if(q->front==NULL){
        return 0;
    }
    cout<<q->front->date<<endl;
    return 1;
}