数据结构栈和列表（数据结构系列4栈和队列）
数据结构栈和列表（数据结构系列4栈和队列）8：打印入栈时有一个放元素和移动指针的顺序问题，这一点要看你初始化时top的值是多少，如果初始化top=-1，那么就要先移动指针，再放元素。如果top=0，那么就要先放元素然后移动指针。实现栈建议使用数组和顺序表一样，栈也有静态和动态的，但是静态的不使用，所以使用动态栈（注意修改一下ps->_top=-1）
如果需要获取工程文件，优秀算法书籍，算法刷题攻略及算法刷题视频，请关注公众号【0与1】，并在后台回复【数据结构】
一：栈（1）栈的概念栈：栈是一种特殊的线性表，元素只能在一端插入和删除。进行插入和删除的一端称作栈顶，另一端称为栈底。栈中的元素遵循先进后出的原则。
（2）压栈与出栈压栈：栈的插入操作称为压栈，栈顶入数据
出栈：栈的删除操作称为出栈，栈顶也出数据
如下：栈顶固定，栈顶随元素插入和删除动态变化
上面的栈使用数组实现的，栈也可以用链表保存，如果是双向链表，哪一边作头或作尾都是可以的，但如果是单链表，为了操作的便利性，要注意方向
实现栈建议使用数组
和顺序表一样，栈也有静态和动态的，但是静态的不使用，所以使用动态栈
（注意修改一下ps->_top=-1）
入栈时有一个放元素和移动指针的顺序问题，这一点要看你初始化时top的值是多少，如果初始化top=-1，那么就要先移动指针，再放元素。如果top=0，那么就要先放元素然后移动指针。
8：打印
- 栈的先进后出规则是相对于栈中的元素而言的，并不是绝对的
- 栈经常用于有先进后出的需求场景中，如迷宫问题，括号匹配问题，表达式转换问题，还有递归转非递归等问题
Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDatatype;
//typedef struct Stack//静态栈，实际中不使用
//{
// int top;
// SLDatatype* _arr;
//}Stack;
typedef struct Stack
{
SLDatatype* _arr;
int _top;//栈顶
int _capacity;//容量
}Stack;
void StackInit(Stack* ps);//栈的初始化
void StackDestory(Stack* ps);//销毁栈
void StackAddCapacity(Stack* ps);//打印栈
void StackPrint(Stack* ps);//打印栈
void StackPush(Stack* ps SLDatatype x);//进栈
void StackPop(Stack* ps);//出栈
int StackEmpty(Stack* ps);//清空栈（1表示成功）
SLDatatype StackTop(Stack* ps);//获取栈顶元素
123456789101112131415161718192021222324252627282930
//Stack.c
#include "stack.h"
void StackInit(Stack* ps)
{
assert(ps);
ps->_arr = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
ps->_top = -1;
ps->_capacity = 4;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->_arr);
ps->_arr = NULL;
ps->_top = -1;
ps->_capacity = 0;
}
void StackPrint(Stack* ps)
{
assert(ps);
int k = ps->_top 1;
while (k--)
{
printf("%d " ps->_arr[k]);
}
}
void StackAddCapacity(Stack* ps)
{
assert(ps);
ps->_capacity *= 2;
SLDatatype* temp = (SLDatatype)realloc(ps->_arr sizeof(SLDatatype)*ps->_capacity);
ps->_arr = temp;
}
void StackPush(Stack* ps SLDatatype x)
{
assert(ps);
if (ps->_top == ps->_capacity-1)
StackAddCapacity(ps);
ps->_top ;
ps->_arr[ps->_top] = x;
}
void StackPop(Stack* ps)
{
assert(ps);
if (ps->_top == -1)
{
printf("栈为空\n");
exit(-1);
}
ps->_top--;
}
int StackEmpty(Stack* ps)
{
assert(ps);
if (ps->_top == -1)
{
printf("栈已经清空\n");
return 1;
}
return 0;
}
SLDatatype StackTop(Stack* ps)
{
assert(ps);
if (StackEmpty)
{
printf("栈空\n");
exit(-1);
}
return ps->_arr[ps->_top];
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
test.c
#include "stack.h"
void test()
{
Stack stack;
StackInit(&stack);
StackPush(&stack 1);
StackPush(&stack 2);
StackPush(&stack 3);
StackPush(&stack 4);
StackPush(&stack 5);
StackPush(&stack 5);
StackPush(&stack 5);
StackPush(&stack 5);
StackPush(&stack 5);
StackPrint(&stack);
//StackDestory(&stack);
}
int main()
{
test();
}
123456789101112131415161718192021222324二：队列（1）队列的概念
队列：是一种特殊的线性表，只允许在一端插入数据，在另一端删除数据。链表的特性是先进先出。进行插入操作的一端称之为队尾，进行删除操作的一端称之为队头。
（2）入队与出队入队：队列的插入操作，在队尾插入元素
出队：队列的删除操作，在队尾删除元素
和栈一样，队列同样可以用数组和链表实现，但是如果使用数组实现队列，插入操作可以很好的实现，但是删除操作势必会移动元素，效率不高。所以使用单链表来实现链表，而且单链表的结构很好的满足了链表。
插入操作就是对链表的尾插，删除操作就是链表的头删
队列使用单链表存储的，单链表的每个结点定义为QNode，然后使用两个指针front，rear指向QNode的头结点和尾节点
正常情况出栈很简单，但是要注意一个非常特殊的情况那就是队列中只有一个结点，也即pq->front==pq->rear，此时要特殊处理，将front和rear都置为空（同时注意打印函数也要相应做处理），否则将发生NULL错误
- 队列常用于有先进先出的需求场景中，比如要保持序列公平（排队抽号机 ），生产消费者模， 广度优先遍历
头条号有字数限制，只能用图片代替，如需要代码，可移步 https://blog.csdn.net/qq_39183034/article/details/113179959
