栈和队列的图文讲解，小白易懂_栈的基本图形

• 简述：

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

一.栈

1栈的基本概念

1.1栈的定义

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底（botton）,不含任何的数据元素的栈称为空栈。栈又称为后进后出（Last In First Out）的线性表，简称LIFO结构。

栈的插入操作，叫进栈，也称为压栈、入栈。类似子弹入弹夹，如下图所示。

栈的删除操作，叫作出栈，也有的叫作弹栈。如同子弹出来，如下图所示。

1.2栈的实现

栈的实现一般可以使用 数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

栈的基本操作

ADT栈(stack)
Data
同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
InitStack(*S)：初始化操作，建立一个空栈S。
DestroyStack(*S)：若栈存在，则销毁它。ClearStack(*s)：将栈清空。
StackEmpty(S)：若栈为空，返回true，否则返回fa1se。
GetTop(S，*e)：若栈存在且非空，用e返回S的栈顶元素。
Push(*S，e)：若栈S存在，插入新元素e到栈s中并成为栈顶元素。
Pop(*S，*e)：删除栈S中栈顶元素，并用e返回其值。
StackIength(S)：返回栈S的元素个数。
endADT

2静态栈的实现

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们简单概括
typedef int STDataType;//定义数据类型
#define N 10
typedef struct Stack
{
    STDataType a[N];
    int top; // 栈顶
}Stack;

2.1初始化栈

void StackInit(Stack *ST)
{
    ST->top = -1;    //初始化栈顶指针，注意top=-1
}

2,2判断栈是否为空

bool StackEmpty(Stack *ST)
{
    return ST->top == -1;
}

2.3进栈

void StackPush(Stack *ST,STDataType x)
{
    assert(ST->top!=N);
    ST->top++;
    ST->a[ST->top]=x;
}

2.4出栈

STDataType StackPop(Stack *ST)
{
    assert(ST->top>=0);
    STDataType x=ST->a[ST->top];
    ST->top--;
    return x;
}

2.5返回栈顶元素

STDataType StackTop(Stack *ST)
{
    assert(!StackEmpty(ST));
    return ST->a[ST->top];
}

3.动态栈的实现

// 支持动态增长的栈
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
//#define N 10
//struct Stack
//{
//    int a[N];
//    int top;
//};
 
typedef char STDataType;//定义数据类型
 
typedef struct Stack
{
    STDataType* a;
    int top;//栈顶数
    int capacity;//容量
}ST;
 
//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//压栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//返回栈的个数
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);
//返回栈顶元素
STDataType STTop(ST* ps);
//判断是否回文
bool STMatch(ST* ps);

3.1动态代码的实现

#include"Stack.h"
 
void STInit(ST* ps)
{
    assert(ps);
 
    ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
    if (ps->a == NULL)
    {
        perror("malloc fail");
        return;
    }
    ps->top = 0;
    ps->capacity = 4;
}
 
void STDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    
    ps->top = 0;//注意起点为0，压入时先赋值，再移动下标。
    ps->capacity = 0;
}
 
void STPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*ps->capacity*2);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        ps->capacity *= 2;
        ps->a = tmp;
    }
    ps->a[ps->top] = x;
    ps->top++;
}
 
void STPop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));
    ps->top--;
}
int STSize(ST* ps)
{
    assert(ps);
 
    return ps->top;
}
bool STEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}
STDataType STTop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));
    return ps->a[ps->top - 1];//注意栈顶元素是ps->top的前一个
}
bool STMatch(ST* ps)
{
    assert(ps);
    ST tmp;
    STInit(&tmp);
    while (STTop(ps) != '&')
    {
        STPush(&tmp, STTop(ps));
        STPop(ps);
    }
    STPop(ps);
    while (!STEmpty(ps))
    {
        if (STTop(&tmp) != STTop(ps))
            return false;
        STPop(ps);
        STPop(&tmp);
    }
    return true;
}

二、队列

4.队列的基本概念

4.1队列的定义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

队列是一种先进先出FIFO(First In First Out)的线性表。

允许进行插入操作的一端称为队尾。

允许进行删除操作的一端称为队头。

4.2队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

队列的基本操作

//定义类型
typedef char QDataType;
//定义队列结点结构
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;
//定义队列的头指针和尾指针
typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq,QDataType x);
//出队
void QueuePop(Queue* pq);
//返回队列的个数
int QueueSize(Queue* pq);
//检查队列是否为空
bool QueueEmpty(Queue* pq);
//返回头结点的数据
QDataType QueueFront(Queue* pq);
//返回尾结点的数据
QDataType QueueBack(Queue* pq);
//打印队列的全部元素
void QueuePrint(Queue* pq);

5队列的链表实现

#include"Queue.h"
void QueueInit(Queue* pq)
{
    assert(pq);
 
    pq->head = pq->tail = NULL;
    pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)//当前指针为空，则结束循环
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL )
    {
        assert(pq->tail == NULL);
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;//重点
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head != NULL);
    /*
    QNode* next = ps->head->next;
    free(pq->head);
    pq->head = next;
    if(pq->head == NULL)
        pq->tail = NULL;
        //可读性差
    */
    if (pq->head->next == NULL)
    {
        free(pq->head); 
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
    
}
int QueueSize(Queue* pq)
{
    assert(pq);
 
    return pq->size;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
 
    return pq->size == 0;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
    assert(pq);
 
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}
void QueuePrint(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)//当前指针为空，则结束循环
    {
        printf("%c -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

三.栈和队列面试题

括号匹配问题。 OJ链接
用队列实现栈。 OJ链接
用栈实现队列。 OJ链接
设计循环队列。 OJ链接

有兴趣的话可以试一下