概述
栈和队列比较简单，就简单的描述描述，上一节链表讲的有点多了，这次简单讲解一下栈和对列。
4.1 栈
4.1.1 栈的结构
栈的结构，在其他博客也说的很多了，这里就简单说一说，栈是一种线性结构，栈的元素只能先进后出（Frist In Last Out简称 FILO），最早进入的元素存储到栈底，最后进入的元素叫栈顶，栈的操作只能在栈顶操作。
栈的结构可以用数组或者链表来实现
下面只要用数组来实现的：
typedef struct Stack
{
int top; //栈顶指针
int size; //栈的大小
Elemtype *data; //栈的元素
}_Stack;
4.1.2 栈的操作
- 入栈
入栈操作（push）就是把一个新的元素添加到栈顶的位置，然后这个新元素就是栈顶了。
/**
* @brief 入栈,内部支持扩容
* @param
* @retval
*/
int stack_push(struct Stack *s, Elemtype data)
{
if(s == NULL)
return -1;
if(s->top >= s->size) //这个是要等于，因为有0
{
int new_len = (s->size>>1) + s->size;
//printf("len = %d %d %dn", s->size>>1, s->size, new_len);
s->data = realloc(s->data, new_len*sizeof(Elemtype)); //扩容1.5倍,realloc可以复制之前数据到新的内容区
if(s == NULL)
return -2;
s->size = new_len;
}
s->data[s->top] = data;
s->top++;
return 0;
}
- 出栈
出栈操作（pop）就是把元素从栈里取出，不过只能从栈顶的元素取出，出栈元素的前一个元素将会称为新的栈顶
/**
* @brief 出栈，
* @param
* @retval
*/
int stack_pop(struct Stack *s, Elemtype *data)
{
if(s == NULL || data == NULL)
return -1;
//可以做减少容量的操作
if(s->top == 0)
return -2;
*data = s->data[--s->top]; //这个是指向栈顶的，需要先减
return 0;
}
4.1.3 附加：栈的面试题
1.有效括号
leetcode 20题：
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
这道题是在leetcode做的第一道题，不过感觉c语言刷leetcode有点累，啥都需要封装，但是目前涉及到这些基本的数据结构，还是用c写，在leetcode可以用c++，直接调用c++封装好的栈。之前我们也封装好了一个栈，可以现在用来试试。
这道题目就是利用了栈的功能，先进后出，我们把每进来的属于左括号的都进栈，当来了右括号的，就把获取栈顶元素，判断一下是否和刚进来的右括号匹配，如果不匹配，就返回失败，如果匹配的话，出栈，然后继续下一轮。
代码：
/**
* @brief 有效括号
* @param s: 字符串
* @retval
*/
int stack_ValidParentheses(char *s)
{
//1.创建一个栈
struct Stack st;
stack_creat(&st, 10);
//2.分解字符串，c语言只能用指针遍历
char *c = s;
while(*c != ' ')
{
//3.判断是否是左括号，是的话就入栈,否则取出栈顶元素做判断
if(*c == '(' || *c == '[' || *c == '{')
{
stack_push(&st, *c);
}
else
{
int cc;
//先做检测，如果栈为空，返回失败
if(stack_len(&st) == 0)
return -1;
stack_pop(&st, &cc);
//判断是否跟输入的一致
if(*c == ')' && cc != '(' ||
*c == ']' && cc != '[' ||
*c == '}' && cc != '{' )
{
return -1;
}
}
c++;
}
//4.如果栈为空，就说明匹配成功，反则失败
if(stack_len(&st) == 0)
return 0;
return -1;
}
不同语言的实现，只是语法有区别，具体思想都差不多的。
2.最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。
当初第一次听这道题还是在面试的时候，当初很懵逼，想不出来，结果很明显面试被刷了，再次遇到是在程序员小灰的公众号上看到答案，感觉设计的真好，算法还是要好好刷刷。
不好理解就画图，画了图就好理解了：
- 首先申请两个栈，一个是存储正常存储元素的栈，另一个是备胎栈，存储最小值的
- 入栈
这个最小栈的入栈设计和我们之前的入栈有点区别，首先第一个元素4入栈，它会入两个栈，因为最小栈现在为空，所以第一个值就是最小值。
仅接着第二个元素9入栈，在入栈之前要判断一下栈B的栈顶元素，如果9比栈顶元素小，入栈B，现在结果9>4，所以不入栈B。
第三个元素是3，再进行比较，这时候3<4所以入栈B。
- 出栈
竟然入栈都要考虑栈B了，出栈的时候也需要考虑到了。在出栈的时候会判断一下栈B的栈顶元素，如果值相等，栈B也出栈，这样栈B的栈顶元素就是目前栈的最小值，符合获取栈的最小值的复杂度为O(1)
- 获取最小值
直接获取栈B的栈顶元素即可。
思想已经描述清楚了，那代码就不难写了：
/**
* @brief 最小栈创建
* @param
* @retval
*/
static struct Stack gs_stA;
static struct Stack gs_stB;
int stackMin_init(void)
{
//1.创建一个栈A
stack_creat(&gs_stA, 10);
stack_creat(&gs_stB, 10);
return 0;
}
int stackMin_push(Elemtype data)
{
//1.入栈
Elemtype temp;
//判断栈B是否为空，为空直接进栈
if(stack_len(&gs_stB) == 0)
{
stack_push(&gs_stB, data);
}
else
{
//跟栈顶元素判断，如果小于栈顶元素进栈
stack_top(&gs_stB, &temp);
if(data <= temp)
{
stack_push(&gs_stB, data);
}
}
//栈A都需要进栈
stack_push(&gs_stA, data);
return 0;
}
Elemtype stackMin_pop(void)
{
//1.出栈
Elemtype tempA, tempB;
//栈A先出栈
stack_pop(&gs_stA, &tempA);
//看看栈B的栈顶元素
if(stack_len(&gs_stB) != 0)
{
stack_top(&gs_stB, &tempB);
if(tempA == tempB)
stack_pop(&gs_stB, &tempB);
}
return 0;
}
Elemtype stackMin_top(void)
{
//1.出栈
Elemtype tempA;
//栈A先出栈
stack_top(&gs_stA, &tempA);
return tempA;
}
Elemtype stackMin_getMin(void)
{
//最小值
Elemtype temp;
//判断栈B是否为空，不为空就获取最小值
if(stack_len(&gs_stB) != 0)
{
stack_top(&gs_stB, &temp);
return temp;
}
return -1;
}
4.2 队列
4.2.1 队列的结构
队列（queue）是一种线性数据结构，不同于栈先入后出，队列中的元素只能先入先出（first IN First Out，简称FIFO)。队列的出口端叫做队头，队列的入口端叫队尾。入队只能从队尾入，出队只能从队头出。
队列的实现可以用数组也可以用链表。我这里使用数组来实现
typedef struct Queue
{
int front; //对头指针
int rear; //队尾指针
int size; //队列的大小
Elemtype *data; //队列的元素
}_Queue;
4.2.2 循环队列
为什么直接说循环队列，是我们用的基本都是循环队列，基本的队列没什么用，所以直接使用循环队列。
循环队列就是利用已经出队元素留下的空间，让队尾的指针指回到数组的首位，这样这个对列就循环起来了。
判断队列满的条件：（队尾下标+1）%数组长度 = 队头下标。
4.2.3 循环队列的操作
1.入队
入队（enqueue）就是把新元素放入到队列中，只允许在队尾位置放入元素，新元素的下一个位置会成为新的队尾。新添加了扩容操作。
/**
* @brief 入队
* @param
* @retval
*/
//旧代码，保留做对比
int queue_enter(struct Queue *q, Elemtype data)
{
assert(q);
//判断队列是否满
if((q->rear+1)%q->size == q->front)
return -1;
q->data[q->rear] = data;
q->rear = (q->rear+1)%q->size;
return 0;
}
//新添加了扩容操作
int queue_enter(struct Queue *q, Elemtype data)
{
assert(q);
//判断队列是否满
if((q->rear+1)%q->size == q->front)
{
//申请新的内存扩容
int new_len = (q->size>>1)+q->size;
q->data = realloc(q->data, sizeof(Elemtype)*new_len);
assert(q->data);
//如果front<rear就没有问题，扩容后的数据也是直接添加到后面
//如果front>rear，在旧的数组空间，就被分为两截，所以要把0到rear的一截复制到q->size后面，来完成扩容，最后修改rear指针
if(q->rear < q->front)
{
int i;
int old_len = q->size;
for(i=0; i<q->rear; i++)
{
q->data[old_len++] = q->data[i];
}
q->rear = old_len;
}
q->size = new_len;
}
q->data[q->rear] = data;
q->rear = (q->rear+1)%q->size;
return 0;
}
2.出队
出队操作（dequeue）就是把元素移出队列，只允许从队头移除，出队元素下一个元素是新的队头。
/**
* @brief 出队
* @param
* @retval
*/
int queue_delete(struct Queue *q, Elemtype *data)
{
assert(q);
assert(data);
//判断队列是否为空
if(q->rear == q->front)
return -1;
*data = q->data[q->front];
q->front = (q->front+1)%q->size;
return 0;
}
3.遍历
循环队列遍历还是有点意思的，所以这里实现了一个
/**
* @brief 遍历栈
* @param
* @retval
*/
int queue_traversal(struct Queue *q)
{
if(q == NULL)
return -1;
int i = 0;
int head = (q->front)%q->size;
int tail = (q->rear)%q->size;
printf("traversal %d %dn", head, tail);
for(i=head; i != tail; i=(i+1)%q->size) //这样遍历
{
printf("%d ", q->data[i]);
}
printf("n");
return 0;
}
4.2.4 附加：对列的面试题
暂时没有，以后可以添加
4.3 哈希表
暂时没有，以后添加
队列暂时没有面试题，不过leetcode上面队列的题也不少，可以去刷刷，我这里先不刷了，之后会去刷的，现在连哈希表都没实现，不过哈希表实现重点还是哈希函数，以后仔细研究过再做笔记把。
最后
以上就是典雅小天鹅为你收集整理的后台开发学习笔记（四、栈、队列）的全部内容，希望文章能够帮你解决后台开发学习笔记（四、栈、队列）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复