报

数据布局之栈和队列算法题

美丽的神话 Lv.8

2025-12-4 16:04:49 关注

一：有效括号数

学了栈之后这一题就比力简单了。
思绪：1、左括号进栈 2、右括号出栈匹配。
完备代码：

由于使用C语言写的，以是内里包罗了栈的实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* st);
void StackPush(ST* st, STDataType x);
void StackPop(ST* st);
STDataType StackTop(ST* st);
bool StackEmpty(ST* st);
void StackDestroy(ST* st);
int StackSize(ST* st);
void StackInit(ST* st)
{
st->a = NULL;
//top 表示栈顶元素的下一个
st->capacity = st->top = 0;
}
void StackPush(ST* st, STDataType x)
{
assert(st);
if (st->top == st->capacity)
{
int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
STDataType* tmp = (STDataType*)realloc(st->a, newcapacity*sizeof(STDataType));
if (tmp == NULL)
{
perror("malloc fail!!");
exit(1);
}
st->a = tmp;
st->capacity = newcapacity;
}
st->a[st->top++] = x;
}
void StackPop(ST* st)
{
assert(st);
assert(!StackEmpty(st));
st->top--;
}
STDataType StackTop(ST* st)
{
assert(st);
assert(!StackEmpty(st));
return st->a[st->top - 1];
}
bool StackEmpty(ST* st)
{
assert(st);
return st->top == 0;
}
void StackDestroy(ST* st)
{
assert(st);
free(st->a);
st->a == NULL;
st->capacity = st->top = 0;
}
int StackSize(ST* st)
{
assert(st);
return st->top;
}
bool isValid(char* s) {
ST st;
StackInit(&st);
while(*s)
{
if(*s=='{'
|| *s=='('
|| *s=='[')
{
StackPush(&st,*s);
}
else
{
if(StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
char c = StackTop(&st);
StackPop(&st);
if((c == '{' && *s != '}')
|| (c == '(' && *s != ')')
|| (c == '[' && *s != ']'))
{
StackDestroy(&st);
return false;
}
}
s++;
}
bool ret = StackEmpty(&st);
StackDestroy(&st);
return ret;
}

二：用队列实现栈

起首阐明一点，这只是对栈和队列熟练度的观察，并不是栈的更好地实现方式。
思绪：两个队列，包管有一个队列为空，然后别的操纵基于空队列实现。
画图分析：

完备代码：

typedef int QDatatype;
typedef struct QueueNode {
QDatatype data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
struct QueueNode* head;
struct QueueNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype Queueback(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDatatype x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!!");
exit(1);
}
else
{
newnode->next = NULL;
newnode->data = x;
}
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
QueueNode* del = pq->head;
pq->head = del->next;
free(del);
del = NULL;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
return pq->head->data;
}
QDatatype Queueback(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
int cnt = 0;
QueueNode* cur = pq->head;
while (cur)
{
cnt++;
cur = cur->next;
}
return cnt;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate()
{
//不能直接创建结构体，出函数栈帧销毁
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
//判空
Queue *Empty = &obj->q1;
Queue *NonoEmpty = &obj->q2;
if (!QueueEmpty(Empty))
{
Empty = &obj->q2;
NonoEmpty = &obj->q1;
}
//出队列，入另外一个队列
while (QueueSize(NonoEmpty) > 1)
{
QDatatype data = QueueFront(NonoEmpty);
QueuePush(Empty, data);
QueuePop(NonoEmpty);
}
//剩余一个元素
QDatatype data = QueueFront(NonoEmpty);
QueuePop(NonoEmpty);
return data;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{
return Queueback(&obj->q1);
}
else
{
return Queueback(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2));
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);
* int param_2 = myStackPop(obj);
* int param_3 = myStackTop(obj);
* bool param_4 = myStackEmpty(obj);
* myStackFree(obj);
*/

三：用栈实现队列

这一题就是反过来用栈实现队列，要实现后进先出。
思绪：两个栈pushst popst 然后往pushst内里push ，每当要出队列大概要去队头数据时，就返回popst的栈顶数据，如果popst为空，就一口气把pushst内里的数据全塞进去。
就不画图了

完备代码：

栈的实如今上面有，不重复拷贝了。