自学内容网 自学内容网

栈和队列的算法题目(C语言)

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;

}


原文地址:https://blog.csdn.net/qq_64105689/article/details/142210849

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!