数据结构学习笔记|栈和队列
原创
1. 栈的定义
栈是一种先进后出的数据结构，其操作更是被限制在了pop和push里，而且仅仅是针对栈顶操作，所以时间复杂度是O(1)。想象栈其实和现实中叠放的盘子一样。
在做leetcode练习的时候，会有一些题目要求进行括号的匹配，就可以用到栈。
栈的实现可以用数组也可以用链表，用数组实现的叫做顺序栈，用链表实现的叫做链栈。我个人喜欢链栈多一些：
- 链表的扩容不需要移动内存；
- 栈的pop和push都是O(1)的操作，规避了链表查找的时间复杂度不如数组的问题。
2. 代码实现
如果仔细观察一下网上能搜到的栈的示意图，都可以看出来，栈很像一个竖放的链表：
这么一看，连pop和push操作都知道如何实现了，push就是头插法，pop就是从链表里取头结点的next即可。
struct stack {
int data;
linkedStack next;
int size;
int capacity;
};和之前实现的链表别无二致，除了名字不同我说不上任何不同来。可以说栈只是从链表的方法里挑了几个来实现一些受限的逻辑功能而已。
void push(linkedStack stack, int data) {
// 栈满，则返回什么也不做
if (stack->size == stack->capacity) {
printf("stack is full!");
return ;
}
// 在头结点之后插入结点
auto node = (linkedStack) malloc(sizeof (Stack));
node->data = data;
linkedStack L = stack; //指针指向头结点
node->next = L->next;
L->next = node;
// size自增1
stack->size += 1;
}
int pop(linkedStack stack) {
// 只有一个头结点，没有操作的必要
if (stack->size == 1) {
printf("stack is empty!");
exit(1);
}
linkedStack L = stack;
linkedStack r = L->next; //要取出的结点
L->next = r->next; //链表重新连上
int data = r->data;
free(r);
stack->size -= 1;
return data;
}3. 用链栈实现括号匹配
leetcode里有一道题大概是给了一个括号的字符串，要求判断这是不是一个合法的括号串。如“(([]))”、“(){}()”、“
(())()”就是合法的，而“(()))”、“()()(}”就是非法的。
这种就很好用栈来实现：
- 遍历字符串，如果是左括号就入栈；
- 如果是左括号，就对栈进行pop操作并将栈顶元素和左括号比对，如果成对就继续，不成对或者栈空就直接报错
知道了这个逻辑之后代码就好写了。
//判断左右括号的配对情况
bool isPair(char c1, char c2) {
return ((c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}')) ;
}
bool check(const char *str, int len) {
linkedStack stack = initStack(len + 1);
for (int i = 0; i < len; i++) {
char item = str[i];
if (item == '(' || item == '[' || item == '{') { // 左括号，压栈
push(stack, item);
} else { //右括号
if (stack->size == 1) { //栈里没有元素了，直接报错
return false;
}
char left = pop(stack);
if (!isPair(left, item)) { //不成对则报错，成对则继续
return false;
} else {
continue;
}
}
}
return true;
}4. 队列的定义和实现
队列这个名字起的很好，就和我们平时排队是一样的，先来的先得，对于队列来说有个说法叫做FIFO，先进先出，和日常排队是一样的。
在用Java的时候有一个叫线程池的东西很好用，其中就有一个等待队列，这就是队列的一个常见的应用场景。
队列和栈不同，栈只对栈顶进行push和pop操作，而队列明显是插入时从队尾插进来，逐出时从队头逐出。有个专用的词汇：
- enqueue：入队，从队尾插入数据；
- dequeue：出队，从队头取走数据。
如果用链表来实现，那应该是这样的：
还是一个链表，出队简单，和栈的pop操作一样。入队稍显麻烦，需要首先遍历到队尾。这样的时间复杂度是O(n)。
struct queue {
int data;
linkedQueue next;
int size;
int capacity;
};实现起来就是一个简单的尾插法和头取法：
void enqueue(linkedQueue queue, int data) {
if (queue->size == queue->capacity) {
printf("queue is full!");
return;
}
auto node = (linkedQueue) malloc(sizeof (Queue));
node->data = data;
linkedQueue L = queue;
if (L->next == nullptr) {
L->next = node;
return;
}
while (L->next != nullptr) {
L = L->next;
}
L->next = node;
queue->size += 1;
}
int dequeue(linkedQueue queue) {
int data;
if (queue->size == 1) {
printf("queue is empty!");
exit(1);
}
linkedQueue L = queue;
linkedQueue r;
r = L->next;
L->next = r->next;
data = r->data;
free(r);
queue->size -= 1;
return data;
}这里还是链表的老毛病，取尾部结点就必须要遍历，时间复杂度太高。当然，这一点可以通过维护一个尾指针解决，毕竟队列只会对头尾进行操作，这样做的效果是很显著的。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
