猿创征文|栈和队列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);
 
}


相关文章
|
8天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
24 8
【数据结构OJ题】合并两个有序链表
|
10天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
12 2
【数据结构OJ题】移除链表元素
|
10天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
12 1
【数据结构OJ题】链表中倒数第k个结点
|
11天前
|
存储
【数据结构OJ题】轮转数组
力扣题目——轮转数组
16 2
【数据结构OJ题】轮转数组
|
11天前
|
算法
【数据结构OJ题】移除元素
力扣题目——移除元素
14 1
【数据结构OJ题】移除元素
|
7天前
【数据结构OJ题】链表分割
牛客题目——链表分割
9 0
【数据结构OJ题】链表分割
|
10天前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
10 0
【数据结构OJ题】链表的中间结点
|
10天前
【数据结构OJ题】反转链表
力扣题目——反转链表
11 0
【数据结构OJ题】反转链表
|
10天前
【数据结构OJ题】合并两个有序数组
力扣题目——合并两个有序数组
11 0
【数据结构OJ题】合并两个有序数组