当前位置：首页 > news >正文

栈和队列的算法题目（C语言）

news 来源：原创 2024/9/19 16:07:27

1. 括号匹配问题

20. 有效的括号 - 力扣（LeetCode）

利用栈后入先出的特性解题

1.判断字符串是否为空为空返回

2.创建栈，遍历字符串

第一个字符是左括号的情况：入栈->继续遍历下一个字符

第一个字符是右括号的情况：从栈顶取元素，判断当前右括号是否匹配栈顶的左括号

3.遍历结束，判断栈是否为空，为空说明所有括号都已匹配，不为空说明有左括号没有匹配上

bool isValid(char* s) {Stack st;StackInit(&st);int count = 0;while(s[count]){if(s[count] == '(' || s[count] == '['|| s[count] == '{'){StackPush(&st,s[count]);}else{if(StackEmpty(&st)){StackDestory(&st);return false;}char top = StcakTop(&st);if(top == '(' && s[count] != ')'||top == '{' && s[count] != '}'||top == '[' && s[count] != ']'){StackDestory(&st);return false;}StackPop(&st);}count++;}int  result = StackEmpty(&st);StackDestory(&st);return result;
}

2. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

队列的特性是先入先出栈的特性是后入先出

创建两个队列

为空的情况：两个队列都为空

1.push插入：直接插入队列中

2.需要pop的时候，将队列的元素导到另一个队列，最后一个元素就是栈顶元素

3.当有元素需要插入，判断哪个队列不为空，就直接插入

typedef struct {Queue* q1;Queue* q2;
} MyStack;MyStack* myStackCreate() {MyStack* newQueue = (MyStack*)malloc(sizeof(MyStack));newQueue->q1 =(Queue*)malloc(sizeof(Queue));newQueue->q2 =(Queue*)malloc(sizeof(Queue));QueueInit(newQueue->q1);QueueInit(newQueue->q2);return newQueue;
}void myStackPush(MyStack* obj, int x) {Queue* empty = obj->q1;Queue* noempty = obj->q2;if(QueueEmpty(noempty)){empty = obj->q1;noempty = obj->q2;}QueuePush(noempty,x);
}int myStackPop(MyStack* obj) {Queue* empty = obj->q1;Queue* noempty = obj->q2;int val = 0;if(QueueEmpty(noempty)){empty = obj->q2;noempty = obj->q1;}while(noempty->_size > 1){int val = QueueFront(noempty);QueuePush(empty,val);QueuePop(noempty);}if(noempty->_size == 1){val = QueueFront(noempty);QueuePop(noempty);}return val;
}int myStackTop(MyStack* obj) {Queue* empty = obj->q1;Queue* noempty = obj->q2;int val = 0;if(QueueEmpty(noempty)){empty = obj->q2;noempty = obj->q1;}val = noempty->_rear->_data;return val;
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj->q1) && QueueEmpty(obj->q2);
}void myStackFree(MyStack* obj) {Queue* empty = obj->q1;Queue* noempty = obj->q2;if(QueueEmpty(noempty)){empty = obj->q2;noempty = obj->q1;}QueueDestory(noempty);free(obj->q1);free(obj->q2);free(obj);
}

3. 用栈实现队列

stack1存放要进栈的元素

stack2存放要出栈的元素

当stack2为空时将stack1的所有元素都导到stack2中

插入：

1.直接使用StackPush插入到stack1中

删除：

1.判断stack2是否为空，为空将stack1的数据导到stack2内

2.直接使用StackPop()取到栈顶元素返回

232. 用栈实现队列 - 力扣（LeetCode）

typedef struct {Stack* s1;Stack* s2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue));newQueue->s1 = (Stack*)malloc(sizeof(Stack));newQueue->s2 = (Stack*)malloc(sizeof(Stack));StackInit(newQueue->s1);StackInit(newQueue->s2);return newQueue;
}void myQueuePush(MyQueue* obj, int x) {StackPush(obj->s1,x);
}int myQueuePop(MyQueue* obj) {if(StackEmpty(obj->s2)){while(!StackEmpty(obj->s1)){StackPush(obj->s2,StackPop(obj->s1));}}return StackPop(obj->s2);
}int myQueuePeek(MyQueue* obj) {if(StackEmpty(obj->s2)){while(!StackEmpty(obj->s1)){StackPush(obj->s2,StackPop(obj->s1));}}return StcakTop(obj->s2);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj->s1) && StackEmpty(obj->s2);
}void myQueueFree(MyQueue* obj) {StackDestory(obj->s1);StackDestory(obj->s2);free(obj->s1);free(obj->s2);free(obj);
}

4. 设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

使用数组来设计循环队列，当head走到最后一个元素就使用%来使数组循环

head就是队头，tail就是队尾

从队头出数据，队尾入数据

题目要求队列长度为k，我们申请k+1个空间用来区分队列满和不满的情况

当head==tail就是队列为空
当tail的下一个位置的元素==head就表示队列为满

typedef struct {int *Queue;int k;int head;int tail;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* newQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));newQueue->tail = newQueue->head = 0;newQueue->k = k + 1; newQueue->Queue = (int*)malloc(sizeof(int)*(k+1));return newQueue;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->k) == obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->Queue[obj->tail] = value;obj->tail = (obj->tail+1)%(obj->k);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->head = (obj->head+1)%(obj->k);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->Queue[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->Queue[(obj->tail-1+obj->k) % obj->k];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->Queue);free(obj);
}

栈的C语言代码：

typedef char StackDataType;typedef struct StackNode
{StackDataType* _stack;int _capacity;int _top;
}Stack;void StackInit(Stack* st);
void StackPush(Stack* st, StackDataType data);
void StackPop(Stack* st);
StackDataType StcakTop(Stack* st);
int StackSize(Stack* st);
int StackEmpty(Stack* st);
void StackDestory(Stack* st);
void StackInit(Stack* st)
{st->_stack = NULL;st->_capacity = 0;st->_top = 0;
}
void StackPush(Stack* st, StackDataType data)
{assert(st);if (st->_capacity == st->_top){int newCapacity = st->_capacity == 0?4:st->_capacity*2;st->_stack = (StackDataType*)realloc(st->_stack, newCapacity * sizeof(StackDataType));st->_capacity = newCapacity;}st->_stack[st->_top] = data;st->_top++;
}
void StackPop(Stack* st)
{assert(st);assert(st->_top);st->_top--;
}
StackDataType StcakTop(Stack* st)
{assert(st);return st->_stack[st->_top-1];
}
int StackSize(Stack* st)
{assert(st);return st->_top;
}
int StackEmpty(Stack* st)
{assert(st);if (st->_top == 0){return true;}else{return false;}
}
void StackDestory(Stack* st)
{assert(st);free(st->_stack);st->_stack = NULL;st->_capacity = st->_top = 0;}

队列的C语言代码：

typedef int QueueNodeDataType;
typedef struct QListNode
{struct QListNode* _pNext;QueueNodeDataType _data;
}QNode;typedef struct Queue
{QNode* _front;QNode* _rear;int _size;
}Queue;void QueueInit(Queue* q);
void QueuePush(Queue* q, QueueNodeDataType val);
void QueuePop(Queue* q);
bool QueueEmpty(Queue* q);
int QueueSize(Queue* q);
QueueNodeDataType QueueFront(Queue* q);
QueueNodeDataType Queuerear(Queue* q);
void QueueDestory(Queue* q);
void QueueInit(Queue* q)
{assert(q);q->_front = NULL;q->_rear = NULL;q->_size = 0;
}
void QueuePush(Queue* q, QueueNodeDataType val)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));assert(newNode);newNode->_data = val;newNode->_pNext = NULL;if (q->_front == NULL)//队列没有结点{q->_front = q->_rear = newNode;}else{q->_rear->_pNext = newNode;q->_rear = newNode;}q->_size++;
}
void QueuePop(Queue* q)
{assert(q);if (q->_front == NULL){return;}else{if (q->_front == q->_rear)//说明只有一个结点{free(q->_front);q->_front = q->_rear = NULL;}else{QNode* cur = q->_front->_pNext;free(q->_front);q->_front = cur;}}q->_size--;
}
bool QueueEmpty(Queue* q)
{assert(q);return q->_front == NULL;
}
int QueueSize(Queue* q)
{assert(q);return q->_size;
}
QueueNodeDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}
QueueNodeDataType Queuerear(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}
void QueueDestory(Queue* q)
{assert(q);QNode* cur = q->_front;while (cur){QNode* tmp = cur;cur = cur->_pNext;free(tmp);}q->_front = q->_rear = NULL;}