栈与队列练习题

简介: 栈与队列练习题

有效的括号

有效的括号


思路: 我们可以使用一个栈来解决这个问题, 我们用栈来存储左括号,当遇见右括号就取出栈顶元素出来比较,如果符合就继续匹配,否则就返回false, 或者最后栈还要数据,或者栈没有数据但还要右括号都是不匹配成功的

typedef char TackDataType;
typedef struct Stack
{
    TackDataType * a;
    int top; //栈顶元素
    int capacity;
}Stack;
//初始化
void TackInit(Stack *pst)
{
    assert(pst);
    pst->a = NULL;
    pst->top = -1;
    pst->capacity = 0;
}
// 入栈
void TackPush(Stack *pst, TackDataType elemest)
{
    assert(pst);
    //判断是否满了
    if ((pst->top) +1 == pst->capacity)
    {
        pst->capacity = (pst->capacity == 0? 4 : pst->capacity * 2);
        TackDataType* tmp = (TackDataType*)realloc(pst->a,sizeof(Stack) * pst->capacity);
        if (tmp == NULL)
        {
            perror("realloc");
            return;
        }
        pst->a = tmp;

    }
    pst->a[++(pst->top)] = elemest;

}
//出栈
void TackPop(Stack *pst)
{
    assert(pst);
    if(pst->top != -1)
        pst->top--;
}
//长度
int TackSize(Stack *pst)
{
    assert(pst);
    return (pst->top) + 1;
}
//是否为空
bool TackEmpty(Stack *pst)
{
    assert(pst);
    return pst->top == -1; 
}
//栈顶元素
TackDataType TackTop(Stack *pst)
{
    assert(pst);
    return pst->a[pst->top];
}
//释放
void TackDestroy(Stack *pst)
{
    free(pst->a);
    pst->a = NULL;
    pst->top = -1;
    pst ->capacity = 0;
}

bool isValid(char* s) 
{
    Stack pst;
    //初始化
    TackInit(&pst);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            //入栈
            TackPush(&pst, *s);

        }
        else
        {
            //是否为空
            if (TackEmpty(&pst))
            {
                TackDestroy(&pst);
                return false;
            }

                
            //栈顶元素
            if ((*s == '}' &&  TackTop(&pst) == '{')
            || (*s == ']' &&  TackTop(&pst) == '[')
            ||(*s == ')' &&  TackTop(&pst) == '('))
            {
                //出栈
                TackPop(&pst);
            }
            else
            {
                return false;
            }
            

        }
        s++;
    }
    //是否为空
    if (!TackEmpty(&pst))
    {
        TackDestroy(&pst);
        return false;
    }
    TackDestroy(&pst);    
    return true;

    
}



用队列实现栈

用队列实现栈


这道题主要的就是在删除和插入数据中要下点功夫,

插入: 我们只需往不为空的队列插入,因为这样必定有一个队列为空,如果刚开始两个队列都为空,我们只需随意插入一个队列就行

删除: 我们删除栈的栈顶元素,是直接删除最新插入的元素,而队列的特点就是先进先出,我们可以借助空队列把非空队列的最后一个元素保留下来,然后把多余的元素插入到空队列中,需要注意的是,插入的最后一个元素的下一个next一定要修改为NULL,不然在释放会有野指针,然后保留的最后一个元素再free掉,

剩下的就是释放空间:

我们要先释放掉链表的空间,然后再释放两个队列的空间,

删除:

typedef int QDataType;
//链表节点
typedef struct QNode
{
    QDataType val;
    struct QNode *next;
}QNode;
//队列结构
typedef struct Queue
{
    QNode* head;
    QNode* tail; //队尾
    int size;
}Queue;


//创建两个队列
typedef struct
{
    Queue stack1;
     Queue stack2;

} MyStack;


MyStack* myStackCreate() 
{
    //创建两个队列
    MyStack * Queuetack = (MyStack*)malloc(sizeof(MyStack));
    //创建哨兵位
    Queuetack->stack1.head = (QNode*)malloc(sizeof(QNode));
    Queuetack->stack1.head->next = NULL;
    Queuetack->stack1.size = 0;
     Queuetack->stack1.tail = Queuetack->stack1.head;
      //创建哨兵位
     Queuetack->stack2.head = (QNode*)malloc(sizeof(QNode));
    Queuetack->stack2.head->next = NULL;
    Queuetack->stack2.size = 0;
     Queuetack->stack2.tail = Queuetack->stack2.head;
     return Queuetack;

    
}

void myStackPush(MyStack* obj, int x) 
{
   assert(obj);
    if (obj->stack2.size)
    {
        //创建节点
        QNode* newnode = (QNode*)malloc(sizeof(QNode));
        newnode->val = x;
        newnode->next = NULL;
        //插入
        obj->stack2.tail->next = newnode;
        obj->stack2.tail = newnode;
        obj->stack2.size++;
    }
    else
    {
        //创建节点
        QNode* newnode = (QNode*)malloc(sizeof(QNode));
        assert(newnode);
        newnode->val = x;
        newnode->next = NULL;
        //插入
        obj->stack1.tail->next = newnode;
        obj->stack1.tail = newnode;
        obj->stack1.size++;
    }
}

int myStackPop(MyStack* obj) 
{
    if (!obj->stack2.size && !obj->stack1.size)
        return 0;
    if (obj->stack2.size)
    {
        while (obj->stack2.head->next != obj->stack2.tail)
        {
            QNode* node = obj->stack2.head->next;
            obj->stack2.head->next = node->next;
            obj->stack1.tail->next = node;
            obj->stack1.tail = node;
            
            obj->stack1.size++;

        }
        obj->stack1.tail->next = NULL;
        int a = obj->stack2.tail->val;
        free(obj->stack2.tail);
        obj->stack2.tail = obj->stack2.head;
        obj->stack2.head->next = NULL;
        obj->stack2.size = 0;
        return a;
    }
    else
    {

        while (obj->stack1.head->next != obj->stack1.tail)
        {
            QNode* node = obj->stack1.head->next;
            obj->stack1.head->next = node->next;
            obj->stack2.tail->next = node;
            obj->stack2.tail = node;
            
            obj->stack2.size++;

        }
        obj->stack2.tail->next = NULL;
        int a = obj->stack1.tail->val;
        free(obj->stack1.tail);
        obj->stack1.tail = obj->stack1.head;
        obj->stack1.head->next = NULL;
        obj->stack1.size = 0;
        return a;
    }
    
}

int myStackTop(MyStack* obj) 
{

    
    if (!obj->stack2.size && !obj->stack1.size)
        return 0;
    if (!obj->stack2.size)
    {
        return obj->stack1.tail->val;
    }
    else
    {
        return obj->stack2.tail->val;
    }
}

bool myStackEmpty(MyStack* obj) 
{
    return obj->stack2.size== 0 && obj->stack1.size ==0;
}

void myStackFree(MyStack* obj) 
{
    QNode *cur = obj->stack1.head->next;
    while(cur)
    {
        QNode *cur1 = cur->next;
        free(cur);
        cur = cur1;
    }
    free(obj->stack1.head);
    obj->stack1.head = NULL;
    obj->stack1.size = 0;
    obj->stack1.tail = NULL;

    cur = obj->stack2.head->next;
     while(cur)
    {
        QNode *cur1 = cur->next;
        free(cur);
        cur = cur1;
    }
     free(obj->stack2.head);
    obj->stack2.head = NULL;
    obj->stack2.size = 0;
    obj->stack2.tail = NULL;
    free(obj);
}


用栈实现队列

用栈实现队列

结构:

这道题的思路和上面的题目思路是相同的,我们借助两个栈来实现队列,

有点差别就是

插入:


我们插入要插入到stack1那里去,

删除:

如果stack2为空,我们就要把stack1的数据插入stack2,如果stack2有数据可以先删除stack2的数据,直到为空,然后再把stack1的数据插入到stack2里面去


查找头:

如果stack2为空,我们就要把stack1的数据插入stack2,如果stack2有数据可以先查找stack2的数据


删除我们不能从top那边开始拉数据,而是要从left开始,

我们还要注意的就是队列插入的时候一定判断 栈是否要扩大空间,

typedef int StackDAtaType;
typedef struct Stack
{
    StackDAtaType *data;
    int top;//栈顶元素下一个
    int capacity;

}Stack;

typedef struct 
{
    Stack stack1;
    Stack stack2;
} MyQueue;


MyQueue* myQueueCreate() 
{
    //初始化
    MyQueue *queue = (MyQueue*)malloc(sizeof(MyQueue));
    //第一个栈
    queue->stack1.data = NULL;
    queue->stack1.top = 0;//栈顶元素的下一个
    queue->stack1.capacity = 0;
    //第二个栈
    queue->stack2.data = NULL;
    queue->stack2.top = 0;
    queue->stack2.capacity = 0;
    return queue;
}

void myQueuePush(MyQueue* obj, int x) 
{
        //第一个栈插入
        //判断是否满栈
        if(obj->stack1.top == obj->stack1.capacity)
        {
            obj->stack1.capacity = (obj->stack1.capacity == 0 ? 4 : obj->stack1.capacity * 2);
             StackDAtaType *tmp =  (StackDAtaType*)realloc(obj->stack1.data, sizeof(StackDAtaType) * obj->stack1.capacity);
             if (tmp == NULL)
             {
                 perror("realloc");
                 return ;
             }
              obj->stack1.data = tmp;
        }
        obj->stack1.data[obj->stack1.top++] = x;
    
}

int myQueuePeek(MyQueue* obj) 
{
    if(!obj->stack2.top && !obj->stack1.top)
        return 0;
    if(obj->stack2.top)
    {
        return obj->stack2.data[obj->stack2.top -1];
    }
    else
    {
        //取出第一栈的元素 插入到第二栈
        while (obj->stack1.top)
        {
             //判断是否满栈
            if (obj->stack2.top == obj->stack2.capacity)
            {
                obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);
                StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);
                if (tmp == NULL)
                {
                    perror("realloc");
                    return   0;
                }
                obj->stack2.data = tmp;
            }
  
                obj->stack2.data[obj->stack2.top++] = obj->stack1.data[--obj->stack1.top];
        }

        return obj->stack2.data[obj->stack2.top - 1];

    }
    
}

int myQueuePeek(MyQueue* obj) 
{
    if(!obj->stack2.top && !obj->stack1.top)
        return 0;
    if(obj->stack2.top)
    {
        return obj->stack2.data[obj->stack2.top -1];
    }
    else
    {
        //取出第一栈的元素 插入到第二栈
        while (obj->stack1.top)
        {
             //判断是否满栈
    if (obj->stack2.top == obj->stack2.capacity)
    {
        obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);
        StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);
        if (tmp == NULL)
        {
            perror("realloc");
            return 0;
        }
        obj->stack2.data = tmp;
    }
  
            obj->stack2.data[obj->stack2.top++] = obj->stack1.data[--obj->stack1.top];
        }

        return obj->stack2.data[obj->stack2.top - 1];

    }
    
}

bool myQueueEmpty(MyQueue* obj) 
{
    return obj->stack1.top == 0 && obj->stack2.top == 0;
}

void myQueueFree(MyQueue* obj) 
{
    free(obj->stack1.data);
    obj->stack1.data = NULL;
    obj->stack1.top = 0;
    obj->stack1.capacity = 0;

    free(obj->stack2.data);
    obj->stack2.data = NULL;
    obj->stack2.top = 0;
    obj->stack2.capacity = 0;
    free(obj);

}


循环队列

循环队列


这道题主要就是判断空和满的情况

主要有顺序表和链表,

顺序表:

这里我们使用front指向队头,back指向队尾的下一个,当front和back相等就为空,但是如果顺序表只有一个元素,就会无法判断,那我们可以多创建一个空间,

当back+1等于front就是满的情况,由于是循环队列,back的值要使用(back+1 +k+1)%(k+1)

typedef struct 
{
    int *list;
    int front;
    int back;
    int k;
    
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue * obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    obj->list = (int*)malloc(sizeof(int) * (k + 1)); //多开创一个空间
    obj->front = 0;
    obj->back = 0; //指向尾的下一个
    obj->k = k + 1;
    return obj;
    
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if ((obj->back + 1) % (obj->k) != obj->front)
    {
        obj->list[obj->back] = value;
        obj->back = (obj->back + 1 + obj->k) % (obj->k);
        return true;
    }
    return false;
    
    
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (obj->back == obj->front)
        return false;
    obj->front = (obj->front + 1 + obj->k) % (obj->k);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(obj->back == obj->front)
        return -1;
    return obj->list[obj->front];
    
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(obj->back == obj->front)
        return -1;
    return obj->list[(obj->back-1 + obj->k) %(obj->k)];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->back == obj->front;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->back + 1) % (obj->k) == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->list);
    free(obj);
}


链表:我们也可以通过类似的方法来,但是我们如果要找到队尾节点,就要标记好,如果是使用双向链表就可以不用标记

typedef int DataType;
typedef struct ListNode1
{
    DataType val;
    struct ListNode1 *next;
} ListNode;
typedef struct 
{
    ListNode * head;
    ListNode* back;
    ListNode* tail;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) 
{
    //创建一个循环队列
    MyCircularQueue *obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->head = NULL;
    obj->back = NULL;
    obj->tail =NULL;
    int i= 0;
    for (i = 0; i < k+1; i++)
    {
        //创建节点
        ListNode *newnode = (ListNode*)malloc(sizeof(ListNode));
        newnode->next = NULL;
        if(obj->tail == NULL)
        {
            obj->head = newnode;
            obj->back = newnode;
            obj->tail = newnode;
        }
        else
        {
            obj->tail->next = newnode;
            obj->tail = obj->tail->next;
        }
    }
    obj->tail->next = obj->head;
    obj->tail = obj->back;
    return obj;
    
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{

    if(obj->head != obj->back->next)
    {
        obj->back->val = value;
        obj->tail = obj->back;
        obj->back = obj->back->next;
        return true;

    }
    return false;
    
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    //为空返回false
    if(obj->head == obj->back)
    {
        return false;
    }
    obj->head = obj->head->next;
    return true;
    
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(obj->head == obj->back)
    {
        return -1;
    }
    return obj->head->val;
    
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(obj->head == obj->back)
    {
        return -1;
    }
    return obj->tail->val;

    
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    if(myCircularQueueRear(obj) == -1)
        return true;
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
     if(obj->head != obj->back->next)
    {
        return false;
    }
    return true;
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    ListNode *p = obj->tail->next;
    while(obj->back != p)
    {
        ListNode *pnode = obj->back->next;
        free(obj->back);
        obj->back = pnode;
        free(obj);
    }
    
}


总结

这些题目主要还是考察我们对队列和栈的熟悉程度

相关文章
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
23 1
|
6天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
21天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
24天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
26天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
47 4
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
数据结构(栈与列队)
数据结构(栈与列队)
20 1
|
2月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
17 0
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
34 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器