栈和队列详解

栈

功能要求

编程实现栈的如下功能：
（1）建立一个顺序栈，并可以输出栈中各元素值。
（2）元素入栈，并可以输出栈中各元素值
（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。

具体实现与分析过程

在要求实现的栈的操作里主要有下面四个功能，这样就能实现所要求的几个功能：

1. 创建栈
2. 入栈
3. 出栈
4. 输出栈中各元素的值

既然要求是顺序栈，底层实现就要使用数组，加上一个栈顶指针，同时栈顶指针指向栈顶元素的后面的空位置，也就是说顺序栈大致是这样一个模型：

也就是说创建一个顺序栈，其实就是创建一个带有栈顶指针的数组。另外由于数组具有随机存取的特点，栈顶指针可以是对应位置的索引，而不必是一个指针，所以顺序栈其实就是一个数组加上一个记录栈顶索引的变量。
通过上面的分析，我已经知道顺序栈是什么样的，但是功能1要求的是输入栈中的元素个数n和各个元素值来创建一个顺序栈，也就是说只创建一个顺序栈是不够的，还需要将各个元素入栈，下面我们来分析一下入栈的操作：
因为我们的栈顶指针指向的是栈顶元素之后的空位置，所以在此空位置上放置要入栈的元素即可完成入栈操作，入栈完成之后，此时栈顶指针指向的是栈顶最后一个元素，所以需要将栈顶指针向后移一个位置，因为顺序栈中栈顶指针记录的是索引，所以栈顶指针加1即可。当然可能会在入栈时发生栈满这种情况，如何判断栈满呢？我们需要有一个记录栈最大容量的变量，如果说栈中的元素数目等于栈的最大容量，说明栈满了，需要进行栈的扩充操作。此时我们就需要对栈进行扩充，顺序栈进行扩充可以这样进行：
1.开辟更大的一片连续内存空间
2.将之前的数据复制到新开辟的内存空间（因为栈顶指针记录的是索引，所以栈顶指针的值不变）
这样就完成了栈满之后进行扩充的操作。
根据这样的思路我们可以写出如下的代码：

// 创建指定大小的栈
int * InitStack(int size, int * top){
    // 为栈分配内存空间
    int * p = (int *)malloc(sizeof(int)*size);
    // 栈顶指针初始化
    *top = 0;
    return p;
}

//向栈中输入元素
void Push(int num, int *top, int **stack, int MaxSize){
    (*stack)[*top] = num;
    (*top)++;
    // 检查是否栈满
    if(*top == MaxSize){
        MaxSize *= 2;
        int * p = (int *)malloc(sizeof(int)*MaxSize);
        for(int i = 0;i < *top; i++){
            p[i] = (*stack)[i];
        }
        free(*stack);
        *stack = p;
    } 
}

这两项功能搭配就能够实现完整的功能（1）.实现代码如下：

int main(){
    int top = 0;
    int * stack = NULL;
    int MaxSize = 10;
    stack = InitStack(MaxSize, &top);
    int n, num;
    printf("请输入要向栈中输入的元素个数：");
    scanf("%d", &n);
    printf("请依次输入每一各元素的值：\n");
    while(n--){
        scanf("%d", &num);
        Push(num, &top, &stack, MaxSize);
    }
    printf("从栈顶到栈底的元素依次为：\n");
    for(int i = top-1; i+1; i--){
        printf("%d\n", stack[i]);
    }
    return 0;
}

接下来进行功能（2）的实现：
经过实现功能（1），我们可以发现在实现功能（1）的过程中我们使用了功能（2），我们已经在实现功能（1）的过程中，顺便实现了功能（2），而且在上面我们已经分析过了在向栈中压入元素的时候可能发生栈满，并对这种情况采取了对策，所以我们直接按照上面的思路进行设计即可。
我想了想还是将遍历输出栈中所有元素改成函数，方便代码重复使用。
代码如下：

// 向栈中输入元素
void Push(int num, int *top, int **stack, int MaxSize){
    (*stack)[*top] = num;
    (*top)++;
    // 检查是否栈满
    if(*top == MaxSize){
        MaxSize *= 2;
        int * p = (int *)malloc(sizeof(int)*MaxSize);
        for(int i = 0;i < *top; i++){
            p[i] = (*stack)[i];
        }
        free(*stack);
        *stack = p;
    } 
}

// 遍历栈，查看栈有哪些元素
void iterate(int *stack, int top){
    if(top){
        printf("从栈顶到栈底的元素依次为：\n");
        for(int i = top-1; i+1; i--){
            printf("%d\n", stack[i]);
        }
    }else{
        printf("这是一个空栈，没有元素。\n");
    }
}

接下来就只剩最后一个功能了，将栈顶元素出栈，并输出出栈元素值和出栈后顺序栈中各元素值。
这一个操作主要在于将栈顶元素出栈，如果栈顶元素出栈，那么需要将栈顶指针向下移动，也即是执行栈顶指针减1操作，此时栈顶元素就被出栈了，但是不光要执行出栈操作，还要输出栈顶元素的值，由于我们规定的是栈顶指针指向栈顶元素之后的空位置，所以栈顶元素出栈之后栈顶指针就指向了之前的栈顶元素所在的位置，但是因为并没有其他元素入栈，所以此时栈顶指针指向的位置存储着之前栈顶元素的值，所以可以根据栈顶指针输出之前栈顶元素的值，可以这样做是因为，栈顶元素并没有被其他元素值覆盖，所以才可以这样写，如果被覆盖那么就不可以 这样写了。遍历栈输出栈中的元素值，这与之前一样。需要注意的是空栈这种特殊情况，空栈代表栈中没有元素，这种情况下是不能进行栈顶元素的出栈操作的。
根据上述思路，所写代码如下：

// 栈顶元素出栈操作
void Pop(int * stack, int * top){
    if(!*top){
        printf("空栈，无法执行栈顶元素出栈操作。\n");
    }else{
        (*top)--;
        printf("出栈的栈顶元素的值为：%d\n", stack[*top]);
    }
}

总结

这样关于栈的三个功能就都完成了，对于顺序栈来说，栈满的扩充是比较耗时的，因为他需要将原来栈中的元素都进行复制，这是比较耗时的。

队列

功能要求

编程实现队列的如下功能：
（1）建立循环队列，并可以输出队列中各元素的值
（2）元素入队，并可以输出队列中各元素的值
（3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。

具体实现与分析过程

对于队列，就像人类排队一样，队列中的元素是从队头出去，从队尾进入的，对于一个队列它的图示可以画成下面的样子：

我们知道出队列是从队头开始出，但是从队头开始出队列的话可以有两种方式：
1.队头不同，元素动
2.队头动，元素不动
我们来看一下第一种方式，可以大致画成下面的图像

显然队头后面的所有元素都要动一下，如果队列种元素特别多这在时间上开销就会非常大，而采用第二种方式，则如图所示：

这样的话只移动了队头一次，使得出队操作变成了O(1)时间复杂度，但是这又引入了新的问题，那就是队头向后移动之后，队头前面仍有存储空间，这部分存储空间就无法使用了，为了避免空间的浪费，我们必须采取一定的措施，如何能将那部分空间利用上呢？时钟，看一下时钟的构造是这样的有分针秒针时针，当时针转过12个小时之后又会回到起点，分针则是转过60分钟之后回到起点，秒针则是转过60秒种之后回到起点，假设有这样一个转盘上面有两个针，S与E针每次圆盘被等分成x份，每一次指针只顺时针转动一个格子，因为这是一个循环的圆盘所以S与E就算只是顺时针转动也能一次又一次的遍历圆盘，如果要是队列的存储空间也是这样是不是就能够摆脱因为队头指针后移造成队头指针前面的空间无法访问的情况？答案是肯定的。
所以我们就将队列设计称为这样的循环队列，但是设计成这样的话具体应该怎么操作呢？
假设我们现在存在一个循环队列，那么现在我们就要探讨一下循环队列中，各中情况的判定条件，以及如何计算各项数据。

如果这是一个空队列，那么这个空队列的队头指针应该与队尾指针重合，也即是下面这种情况

我们可以明显看出队列为空的条件应为：
$$队头==队尾$$
这样一来队满的条件就不能是这一个条件了，我们将队满的图示画出来看看：

也就是说队尾指针向后移动一个单位如果能够与队首指针重合，那么说明队满了。但是队尾指针向后移动一个单位时可能会回到内存的首位所以（队尾+1）%num这一个值如果等于队首则说明队满了。可以看到循环队列判断队满时有一个元素空间并没有储存任何元素，也就是浪费了一个存储空间。
队满判定条件：
$$(队尾+1)\%num==队首(num为内存空间的个数)$$
有了这些分析之后，我们就可以着手实现队列要求的三个功能了。
第一个根据输入的队列长度n和各元素值建立值建立一个循环顺序表表示的队列，并输出队列中的各元素值，创建一个循环顺序表，也就是说这一个功能需要首先创建一个顺序表，然后向顺序表中输入元素（元素入队）,等所有元素入队之后遍历队列，输出所有元素的值。
入队操作很容易实现我们只需要进行队尾指针的改变，即可
有了上述思路，开始实现：

// 创建队列
int * InitQueue(int MaxSize){
    int * p = (int *)malloc(sizeof(int)*MaxSize);
    return p;
}

void enqueue(int **queue, int *front, int *rear, int *MaxSize, int num){
    if((*rear+1)%(*MaxSize) == *front){
        // 队满，进行队列扩容
        //需要注意扩容之后指针指向的位置
        int i;
        int *p = (int *)malloc(sizeof(int)*(*MaxSize)*2);
        for(i = 0; *rear!=*front;i++){
            p[i] = (*queue)[*front];
            *front = (*front + 1)%(*MaxSize);
        }
        *rear = i;
        *front = 0;
        *MaxSize = (*MaxSize)*2;
        free(*queue);
        *queue = p;
    }else{
        (*queue)[*rear] = num;
        *rear = (*rear+1)%(*MaxSize);
    }
}

//遍历队列
void iterate(int *queue, int front, int rear, int MaxSize){
    if(front!=rear){
        printf("从队首到队尾的元素依次为：\n");
        while(front!=rear){
            printf("%d\n", queue[front]);
            front = (front+1)%MaxSize;
        }
    }else{
        printf("队列为空队列");
    }
}

实现功能（2），因为我们在实现功能（1）的时候已经实现了功能（2），所以我们不需要再重新写代码，直接按照功能（1）中的思路实现即可。

// 元素入队
void enqueue(int **queue, int *front, int *rear, int *MaxSize, int num){
    if((*rear+1)%(*MaxSize) == *front){
        // 队满，进行队列扩容
        int i;
        int *p = (int *)malloc(sizeof(int)*(*MaxSize)*2);
        for(i = 0; *rear!=*front;i++){
            p[i] = (*queue)[*front];
            *front = (*front + 1)%(*MaxSize);
        }
        *rear = i;
        *front = 0;
        *MaxSize = (*MaxSize)*2;
        free(*queue);
        *queue = p;
    }else{
        (*queue)[*rear] = num;
        *rear = (*rear+1)%(*MaxSize);
    }
}

接下来我们要实现的功能是队首元素出队：队首元素出队，并且输出队首元素，和出队之后队列中各元素的值。
队首元素出队只需要将队首指针进行后移即可，但是队首指针进行后移之后可能转了一圈，此时再进行输出队首元素就比较麻烦，所以我直接进行队首元素的输出然后再将队首指针进行后移，这样就能够实现队首元素出列及输出队首元素的值。
代码实现如下：

void dequeue(int *queue, int *front, int rear, int MaxSize){
    if(*front!=rear){
        printf("出列的队首元素的值为：%d\n", queue[*front]);
        *front = (*front+1)%MaxSize;
    }else{
        printf("队列为空队列");
    }
}

如果有什么地方讲的不好或者讲错的地方欢迎大家指出来，如果我所讲的对你们有帮助不要忘了点赞、收藏、关注哦! 我是你们的好伙伴apprentice_eye 一个致力于让知识变的易懂的博主。