232.用栈实现队列
题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
思路
这是一道模拟题，不涉及到具体算法，使用栈来模拟队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈。
#define MAX_SIZE 1000
typedef struct {
int top;
int data[MAX_SIZE];
} Stack;
void initStack(Stack *stack) {
stack->top = -1;
}
bool isEmpty(Stack *stack) {
return stack->top == -1;
}
void push(Stack *stack, int value) {
if (stack->top < MAX_SIZE - 1) {
stack->data[++stack->top] = value;
} else {
printf("Stack overflow\n");
}
}
int pop(Stack *stack) {
if (!isEmpty(stack)) {
return stack->data[stack->top--];
} else {
printf("Stack underflow\n");
return -1;
}
}
int peek(Stack *stack) {
if (!isEmpty(stack)) {
return stack->data[stack->top];
} else {
printf("Stack is empty\n");
return -1;
}
}
typedef struct {
Stack inputStack;
Stack outputStack;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue *obj = (MyQueue*)malloc(sizeof(MyQueue));
initStack(&obj->inputStack);
initStack(&obj->outputStack);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
push(&obj->inputStack, x);
}
void moveElements(Stack *inputStack, Stack *outputStack) {
while (!isEmpty(inputStack)) {
push(outputStack, pop(inputStack));
}
}
int myQueuePop(MyQueue* obj) {
if (isEmpty(&obj->outputStack)) {
moveElements(&obj->inputStack, &obj->outputStack);
}
return pop(&obj->outputStack);
}
int myQueuePeek(MyQueue* obj) {
if (isEmpty(&obj->outputStack)) {
moveElements(&obj->inputStack, &obj->outputStack);
}
return peek(&obj->outputStack);
}
bool myQueueEmpty(MyQueue* obj) {
return isEmpty(&obj->inputStack) && isEmpty(&obj->outputStack);
}
void myQueueFree(MyQueue* obj) {
free(obj);
}
学习反思
栈和队列的原理：队列是先进先出，栈是先进后出。
225. 用队列实现栈
题目链接/文章讲解/视频讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
思路
typedef struct {
int* data;
int front;
int back;
int size;
int capacity;
} Queue;
Queue* createQueue(int capacity) {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->data = (int*)malloc(sizeof(int) * capacity);
queue->front = 0;
queue->back = 0;
queue->size = 0;
queue->capacity = capacity;
return queue;
}
void enqueue(Queue* queue, int value) {
queue->data[queue->back] = value;
queue->back = (queue->back + 1) % queue->capacity;
queue->size++;
}
int dequeue(Queue* queue) {
int value = queue->data[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size--;
return value;
}
int peek(Queue* queue) {
return queue->data[queue->front];
}
bool isEmpty(Queue* queue) {
return queue->size == 0;
}
void freeQueue(Queue* queue) {
free(queue->data);
free(queue);
}
typedef struct {
Queue* queue1;
Queue* queue2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
obj->queue1 = createQueue(100); // 初始化队列，容量设定为 100
obj->queue2 = createQueue(100);
return obj;
}
void myStackPush(MyStack* obj, int x) {
enqueue(obj->queue2, x);
while (!isEmpty(obj->queue1)) {
enqueue(obj->queue2, dequeue(obj->queue1));
}
Queue* temp = obj->queue1;
obj->queue1 = obj->queue2;
obj->queue2 = temp;
}
int myStackPop(MyStack* obj) {
return dequeue(obj->queue1);
}
int myStackTop(MyStack* obj) {
return peek(obj->queue1);
}
bool myStackEmpty(MyStack* obj) {
return isEmpty(obj->queue1);
}
void myStackFree(MyStack* obj) {
freeQueue(obj->queue1);
freeQueue(obj->queue2);
free(obj);
}
学习反思
队列模拟栈，其实一个队列就够了，那么我们先说一说两个队列来实现栈的思路。队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
20. 有效的括号
题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
思路
int notMatch(char par, char* stack, int stackTop) {
switch(par) {
case ']':
return stack[stackTop - 1] != '[';
case ')':
return stack[stackTop - 1] != '(';
case '}':
return stack[stackTop - 1] != '{';
}
return 0;
}
bool isValid(char * s){
int strLen = strlen(s);
char stack[5000];
int stackTop = 0;
int i;
for(i = 0; i < strLen; i++) {
char tempChar = s[i];
if(tempChar == '(' || tempChar == '[' || tempChar == '{')
stack[stackTop++] = tempChar;
else if(stackTop == 0 || notMatch(tempChar, stack, stackTop))
return 0;
else
stackTop--;
}
return !stackTop;
}学习反思
由于栈结构的特殊性，非常适合做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种情况。
一些同学，在面试中看到这种题目上来就开始写代码，然后就越写越乱。
建议在写代码之前要分析好有哪几种不匹配的情况，如果不在动手之前分析好，写出的代码也会有很多问题。
先来分析一下 这里有三种不匹配的情况，
-
第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
-
第二种情况，括号没有多余，但是 括号的类型没有匹配上。
-
第三种情况，字符串里右方向的括号多余了，所以不匹配
我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
1047. 删除字符串中的所有相邻重复项
思路
char* removeDuplicates(char* s) {
int len = strlen(s);
char* stack = (char*)malloc((len + 1) * sizeof(char));
int stackSize = 0;
for (int i = 0; i < len; i++) {
if (stackSize > 0 && stack[stackSize - 1] == s[i]) {
stackSize--;
} else {
stack[stackSize] = s[i];
stackSize++;
}
}
stack[stackSize] = '\0';
char* result = (char*)malloc((stackSize + 1) * sizeof(char));
strcpy(result, stack);
free(stack);
return result;
}
学习反思
这个函数通过动态内存分配来创建一个临时的栈，并在处理完字符串后，将其内容复制到一个新的字符串中，然后返回这个新字符串。
总结
了解了队列和栈，加油！！！