链式栈和链式队列--简单易懂

#include<iostream>

#include<cstdlib>

using namespace std;

typedef int datatype;

typedef struct link_node{

    datatype info;

    struct link_node*next;

}node;  

node *init()

{

    return NULL;

}

int empty(node *top)

{

    return top?0:1;

}

datatype read(node *top)

{

    if(!top)

    {

        cout << "栈空" << endl;

        exit(1);

    }

    return top->info;

}

void display(node *top)

{

    node *p;

    p = top;

    if(!p)  cout << "链式栈为空" << endl;

    while(p)

    {

        cout << p->info;

        p = p->next;

    }

}

node* push(node *top,datatype x)

{

    node *p;

    p = new struct link_node();

    p->info = x;

    p->next = top;

    top = p;

    return top;

}

node *pop(node *top)

{

    node* p;

    if(!p)

    {

        cout << "链式栈为空" << endl;

        return NULL;

    }

    p = top;

    top = top->next;

    delete p;

    return top;

}

void recycle(node *top)  //用来删除动态申请内存

{

    node *p = top;

    if(!p)

       exit(1);

    while(top)

    {

        p = top;

        top = top->next;

        delete p;

    }    

}

int main()

{

    node *top ;

    top = init();

    top = push(top,1);

    top = push(top,2);

    top = push(top,3);

    top = push(top,4);

    display(top);

    cout << "栈顶为:" << read(top) << endl;

    recycle(top);

    return 0;

}

#include<iostream>

#include<cstdlib>

using namespace std;

typedef int datatype;

typedef struct link_node{

    datatype info;

    struct link_node*next;

}node;

typedef struct

{

    node*front,*rear;  //队列的队首和队尾指针,指向第一个和最后一个队列成员

}queue;

queue*init()

{

   queue *qu;

   qu = new queue();

   qu->front = qu->rear = NULL;

   return qu;    

}

int empty(queue qu)

{

   return qu.front?0:1;    

}

void display(queue *qu)

{

   node *p = qu->front;

   if(!p)  cout << "队空" << endl;

   while(p)

   {

           cout << p->info << endl;

           p = p->next;

   }

}

queue*insert(queue*qu,datatype x)

{

    node*p;

    p = new node();

    p->info = x;

    p->next = NULL;

    if(!qu->front)

       qu->front = qu->rear = p;

    else

    {

        qu->rear->next = p;

        qu->rear = p;

    }

    return qu;

}

datatype read(queue *qu)

{

    if(!qu->front){ cout << "队空" << endl;exit(1); }  

    return qu->front->info;

}

queue *del(queue *qu)

{

    node *p;

    if(!qu->front) { cout<<"无法删除"<<endl;return qu;}

    p = qu->front;  //指向队首

    qu->front = p->next;   //队首指针指向下一个结点

    delete p;//用free来没报错,奇怪

    if(!qu->front) qu->rear = NULL;   //队列中唯一元素被删除后,队列为空

    return qu;

}

void recycle(queue *qu)  //用来删除动态申请内存

{

    node *p,*q;

    q = p = qu->front;    

    delete qu; //qu结点一定存在,故先删除

    if(!p)

      exit(1);

    while(q)

    {

        p = q;  //保存一个临时结点,以便用来删除

        q = q->next;

        delete(p);

    }

}

int main()

{

    queue *qu;

    qu = init();

    insert(qu,1);

    insert(qu,2);

    insert(qu,3);

    insert(qu,4);

    display(qu);

    cout << "队首为:" << read(qu) << endl;

    recycle(qu);

    return 0;

}