猿创征文|栈和队列OJ刷题

简介: 猿创征文|栈和队列OJ刷题

前言

作者小蜗牛向前冲

名言我可以接收失败,但我不能接收放弃

如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

为了提高自己编写代码的能力,特意开设刷题专题,记录自己刷题的思路和理解。欢迎❀大家的指正。

在下面的解题中我们都用C语言实现。

1用队列实现栈

在这里我们就是要将队列模拟实现成栈,我们知道队列是先进先出,栈是先进后出;那我们又如何实现呢?其实我们可以借助二个队列实现。下面我们借助图像来理解一下:

 

首先我们建立二个队列p1,p2,我们可能理解为入栈我们就将入数据到p1处。

其次,我们可以认为p2队列是用来中间存放数据的

这样我们就成功将5出栈了,如果要将4出栈,那么我们又得需要将p2中的数据倒入到p1中:

这样我们就完成了4出栈。

下面我们简单总结一下思路:

1我们要建立二个队列经行模拟。

2始终保持一个队列为空,在出栈时,将将n-1个数据都倒入到空队列中,那么留在另个队列的数据就可以直接出栈了。

下面是完成的解题代码:

typedef  int QDataType;
//定义队列
typedef struct QueueNode
{
  QDataType data;//数据类型
  struct QueueNode* next;
}QNode;
 
//定义指向头和尾的二个指针
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}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);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//返回队列的大小
int QueueSize(Queue* pq);
 
//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
 
//销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* del = cur;
    cur = cur->next;//指向下个节点
    free(del);
  }
  pq->head = pq->tail = NULL;//防止出现野指针
  pq->size = 0;
}
 
//入队
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //申请节点
  QNode* newNode = (QNode*)malloc(sizeof(QNode));
  if (newNode==NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  else
  {
    newNode->data = x;
    newNode->next = NULL;
  }
  //队列为空
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newNode;
  }
  //不为空
  else
  {
    pq->tail->next = newNode;
    pq->tail = newNode;//tail指针指向newNode
  }
  pq->size++;
}
 
//出队
void QueuePop(Queue* pq)
{
  assert(pq);
  //断言队列是否为空
  assert(!QueueEmpty(pq));
  //当队列中就一个数据时
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* del = pq->head;
    pq->head = pq->head->next;//头变为下个节点
    free(del);
    del = NULL;
  }
  pq->size--;
}
 
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->tail == NULL;
}
 
//返回指向队头的数据的指针
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  //断言队列是否为空
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
 
//返回指向队尾的数据的指针
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  //断言队列是否为空
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
 
//返回队列的大小
int QueueSize(Queue* pq)
{
  return pq->size;
}
 
typedef struct {
    Queue p1;//入栈
    Queue p2;//出栈
 
} MyStack;
 
 
MyStack* myStackCreate() {
      MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
        //对栈初始化
        QueueInit(&obj->p1);
        QueueInit(&obj->p2);
        return obj;
}
 
void myStackPush(MyStack* obj, int x) {
    //当p1为空时就将数据倒入
    if(!QueueEmpty(&obj->p1))
    {
        QueuePush(&obj->p1,x);
    }
    else
    {
        QueuePush(&obj->p2,x);
    }
 
}
 
int myStackPop(MyStack* obj) {
    Queue* empty = &obj->p1;//假设p1为空
    Queue* noEmpty = &obj->p2;
    //如果p1队列为非空
    if(!QueueEmpty(&obj->p1))
    {
        empty = &obj->p2;
        noEmpty = &obj->p1;
    }
    //将非空队列中的N-1的数据都倒入到空队列中,那么原队列还剩的1个数据就是要返回的栈顶数据
    while(QueueSize(noEmpty)>1)
    {
        QueuePush(empty,QueueFront(noEmpty));//入栈
        QueuePop(noEmpty);//出栈
    }
    int top =  QueueFront(noEmpty);
     QueuePop(noEmpty);//出栈
    return top;
}
 
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->p1))
    {
        return QueueBack(&obj->p1);
    }
    else
    {
        return QueueBack(&obj->p2);
    }
}
 
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2);
}
 
void myStackFree(MyStack* obj) {
     QueueDestroy(&obj->p1);
     QueueDestroy(&obj->p2);
     free(obj);
}

2 栈实现队列

要用二个栈实现队列,这是很好实现的。

为什么这么说呢?我们可以用栈PushST来模拟入队列栈PopST模拟出队列

下面我们顺着这个思路来,来图解一下 1,2,3,4的入队列和出队列的过程。

1数据入队列

2 要出队列时,当PopST为空的时候,就将PushST的数据倒入到PopST中,然后直接出就行。

完整代码:

typedef  int STDataType;
//定义栈
typedef struct Stack
{
  STDataType* arr;//数据类型
  int pos;//数组下标
  int capacity;//栈的容量
}ST;
 
//初始化
void StackInit(ST* ps);
//销毁
void StackDestroy(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
显示返回栈顶数据
STDataType StackTop(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
//返回栈的长度//初始化
void StackInit(ST* ps)
{
  assert(ps);
  ps->arr = NULL;//初始数组为空
  ps->pos = ps->capacity = 0;//初始为0
}
 
//销毁
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->arr);//arr是整个栈的地址
  ps->arr = NULL;
  ps->capacity = ps->pos = 0;
}
 
//入栈
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  //判断栈的空间是否满
  if (ps->pos == ps->capacity)
  {
    //扩容
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//扩2倍
    STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("reamlloc fail");
      exit(-1);
    }
    //跟新容量
    ps->arr = tmp;
    ps->capacity = newCapacity;
  }
  //入栈
  ps->arr[ps->pos] = x;
  ps->pos++;//下标++
}
 
//出栈
void StackPop(ST* ps)
{
  assert(ps);
  //断言栈是否为空
  assert(!StackEmpty(ps));
  --ps->pos;
}
 
//判断栈是否为空
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->pos == 0;
}
 
//显示返回栈顶数据
STDataType StackTop(ST* ps)
{
  assert(ps);
  //断言栈是否为空
  assert(!StackEmpty(ps));
  return  ps->arr[ps->pos - 1];//下标已经前移
}
 
//返回栈的长度
int StackSize(ST* ps)
{
  assert(ps);
  return ps->pos;
}
int StackSize(ST* ps);
 
typedef struct {
  ST PushST;//入队列
  ST PopST;//出队列
} MyQueue;
 
 
MyQueue* myQueueCreate() {
  //为模拟的队列开辟空间
  MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
  //初始化
  StackInit(&obj->PushST);
  StackInit(&obj->PopST);
  return obj;
}
 
void myQueuePush(MyQueue* obj, int x) {
  StackPush(&obj->PushST, x);
}
void PushSTTOPopST(MyQueue* obj)
{
  //判断PopST是否为空
  if (StackEmpty(&obj->PopST))
  {
    while (!(StackEmpty(&obj->PushST)))
    {
      StackPush(&obj->PopST, StackTop(&obj->PushST));
      StackPop(&obj->PushST);
    }
  }
}
 
int myQueuePop(MyQueue* obj) {
  //将PuahST中的元素都倒入PopST中
  PushSTTOPopST(obj);
  int fornt = StackTop(&obj->PopST);
  StackPop(&obj->PopST);
  return fornt;
}
 
int myQueuePeek(MyQueue* obj) {
  //将PuahST中的元素都倒入PopST中
  PushSTTOPopST(obj);
  return StackTop(&obj->PopST);
 
}
 
bool myQueueEmpty(MyQueue* obj) {
  return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}
 
void myQueueFree(MyQueue* obj) {
  //销毁空间
  StackDestroy(&obj->PushST);
  StackDestroy(&obj->PushST);
  free(obj);
}

3 设计循环队列

对于设计循环队列来说有二种思路:

1 用数组实现

2 用链表实现

 

对于这二种思路,我会首选思路1,为什么会这么说呢?

因为用链表实现循环队列,首先你要malloc多份空间,而且这样你还不好判断循环队列是否已满!

所以:我会选择用思路1来为大家解题。

此题有个重点:那就是如何判断队列是否以满。

因为在对于空和满来说,队列中指针fornt和back都是指向同一个位置。

那么我们这么去解决呢?

我们有二个思路:

1多开辟一块空间

2用size标记队列的长度,当size==k时就满

下面我们用思路1来解决:

代码转换:

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

完整代码:

typedef struct {
    int* arr;
    int fornt;
    int back;
    int n;
 
} MyCircularQueue;
 
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr = (int*)malloc(sizeof(int) * (k + 1));
    obj->fornt = obj->back=0;
    obj->n = k + 1;
    return obj;
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->fornt == obj->back;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back + 1) % obj->n == obj->fornt;
 
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->arr[obj->back] = value;
    obj->back++;
    //如果back指针已经指向尾,需要重新指向头
    obj->back %= obj->n;
    return true;
 
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->fornt++;
    //如果fornt指针已经指向尾,需要重新指向头
    obj->fornt %= obj->n;
    return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arr[obj->fornt];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else if(obj->back==0)
    return obj->arr[obj->n-1];
    else
    return obj->arr[obj->back-1];
    // return obj->arr[(obj->back -1 + obj->n) % obj->n];
}
 
 
 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
 
}


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

热门文章

最新文章