栈和队列（单链表简单实现）

一、栈
    栈的特性是先进后出，首先定义一个栈顶指针head或者Top都是可以的。入栈的时候总是在栈顶指针指向的位置插入元素，这样首先插入的元素就跑到后边去了。出栈的时候也是首先从栈顶指向的节点处先出栈，以此来实现先入后出。。
代码如下：其实还就是单链表，只不过单链表初始化的时候不是从后面，而是从前面插入元素。

#include <stdlib.h>
#include <stdio.h>

#define TRUE 1
#define FALSE 0

typedef struct node
{
    int data;
    struct node *next;
}Stack;

void StackInit(Stack *head)
{    //栈的初始化
    head->next = NULL;
}

int StackInput(Stack *head, int num)
{    //入栈
    Stack *p = (Stack *)malloc(sizeof(Stack));
    p->data = num;

    p->next = head->next;
    head->next = p;

    return 0;
}

int StackOutput(Stack *head)
{    //出栈
    int x;
    Stack *p = (Stack *)malloc(sizeof(Stack));
    p = head->next;
    x = p->data;
    head->next = p->next;
    free(p);
    return x;
}

int main()
{
    Stack *top;
    int num[4], i;

    top = (Stack *)malloc(sizeof(Stack));
    StackInit(top);


    for(i = 0; i < 4; i++)
    {
        printf("Please Input %d num:", i+1);
        scanf("%d", &num[i]);
        StackInput(top, num[i]);
    }

    printf("Output num is:\n");
    for(i = 0; i < 4; i++) //出栈，顺序相反
    {
        printf("%d", StackOutput(top));
    }
    return 0;
}

二、队列
    队列和栈正好是相反的，先入先出的结构，构造队列时必须有一个队首指着和一个队尾指针，当队首指针和队尾指针指向同一个地址时，代表这个队列是一个空队列。这两个指针同时也就是队列的精华所在，这两个指针也是有next的，队首指针的next指向的是队列的数据节点，而队尾指针的next指向的是NULL，这一点初始化的时候要注意一下。整个队列中也就只有这两个指针是符号结构体类型的变量，其他的还是和单链表一样的单一结构类型。
代码如下：

/* 队列   先入先出*/
/*使用指针是可以的，但是一定要注意，指针是不是有空间的，也就是指针变量是否是赋值的
没有赋值的指针是不能够使用的，使用的话会出错的*/
#include <stdlib.h>
#include <stdio.h>

#define TRUE 1
#define FALSE 0

typedef struct node
{ /* 节点类型 */
  int data;
  struct node *next;
} qnode;


typedef struct pointer
{    //这仅仅是两个指针，指向队首和队尾，中间节点仍然是单链表的节点
    qnode *front; /* 队首指针 */
    qnode *rear; /* 队尾指针 */
} qpointer;


int QueneInit(qpointer *qp)
{    //队列的初始化
    qnode *q;
    q = (qnode *)malloc(sizeof(qnode));

    qp->front = q;        /*队首和队尾共同指向同一个节点*/
    qp->front->next = NULL;
    qp->rear = qp->front;

}


int QuenePush(qpointer *qp, int x)
{    //入队列
    qnode *p;
    p = (qnode *)malloc(sizeof(qnode));
    p->data = x;
    p->next = NULL;

    qp->rear->next = p;
    qp->rear = p;
}

int IsEmpty(qpointer *qp)
{    //判断队列是否为空
    if (qp->front == qp->rear)
        return TRUE;
    return FALSE; /*这句不能少，少了会出错的*/
}


int QuenePop(qpointer *qp)
{    //出队列
    qnode *q;
    int x;
    if(IsEmpty(qp)) //判断
        return FALSE;

    q = (qnode *)malloc(sizeof(qnode));
    q = qp->front->next;
    x = q->data;
    qp->front->next = q->next;

    if (qp->rear == q) //判断是不是已经到了队列的最后
    {
        qp->rear = qp->front;
    }
    free(q);
    return x;
}



int main()
{    // 为什么使用qpointer *qp 不行呢？
    int num[4], i;
    qpointer qp;
    QueneInit(&qp);

    for(i = 0; i < 4; i++)
    {
        printf("Please Input Num:");
        scanf("%d", &num[i]);
        QuenePush(&qp, num[i]);
    }

    for(i = 0; i < 4; i++)
    {
        printf("%3d", QuenePop(&qp));
    }
    printf("\n");
    return 0;
}

/以上其实都是对链表的进一步运用而已/