栈和队列

1、栈

栈是一种先进先出的数据结构。栈顶进栈，栈顶出栈。

• 数据结构

typedef struct Data{
    int value;
    int min; //用来记录栈的最小值
}*DataType;
typedef struct Stack
{
    DataType link;//动态数组，或者可以直接用静态数组
    int top;
}Stack;

• 栈的初始化

void InitStack(Stack *s)
{
    s->top=0;
    s->link=(DataType)malloc(Max*sizeof(struct Data));
}

• 进栈

void Push(Stack *s, int d)
{
    if(s->top==Max)
    {
        printf("栈已满,无法进栈\n");
        return;
    }
    DataType element=(DataType)malloc(sizeof(struct Data));
    element->value=d;
    if(s->top==0)
        element->min=d;
    else
    {
        element->min=s->link[(s->top)-1].min;
         if(s->link[(s->top)-1].min>d)
                element->min=d;
    }
    s->link[s->top]=*element;
    s->top++;
}

• 出栈

void Pop(Stack *s)
{
    if(s->top==0)
    {
        printf("栈为空\n");
         return;
    }
    s->top--;
}

• 栈的最小值

int MinStack(Stack *s)
{
    return s->link[s->top-1].min;
}

2、队列

队列是FIFO（First In Fisrst Out），即先进先出。有队头和队尾两个指针，分别指向队列的头结点和尾结点。队头出队，队尾入队。

Paste_Image.png

• 数据结构

typedef struct QNode{
    TreeNode Node;      //[TreeNode数据结构]（http://www.jianshu.com/p/1343b3e27869）
    struct QNode * next;
}QNode,*QueueNode;
typedef struct LinkQueue{
    QueueNode front;
    QueueNode rear;
}LinkQueue;

• 队列初始化

void Init(LinkQueue *q)
{
    q->front=q->rear=(QueueNode)malloc(sizeof(QNode));//队列的头结点（空队列中只有一个头结点）
    if(!q->front)//申请内存空间失败
        exit(0);
    q->front->next=NULL;
}

• 入队

void EnQueue(LinkQueue *q,TreeNode treenode)
{
    QueueNode qnode;
    qnode=(QueueNode)malloc(sizeof(QNode));
    qnode->Node=treenode;
    /****插入队列****/
    qnode->next=q->rear->next;
    q->rear->next=qnode;
    /****改队尾指针****/
    q->rear=qnode;
}

• 出队

void DeQueue(LinkQueue *q,TreeNode *node)
{
    QueueNode p;
    p=q->front->next;//头结点后一个结点
    *node=p->Node;
    q->front->next=p->next;
    if(q->rear==p)       //删除的是否是最后一个节点
        q->rear=q->front;
    free(p);
}

• 队列是否为空

int QueueEmpty(LinkQueue *q)
{
    if(q->rear==q->front)//此时队列中只剩一个头结点，则队列为空
        return 1;
    else
        return 0;
}

Paste_Image.png