【栈和队列】算法题 ---- 力扣(二)

简介: 【栈和队列】算法题 ---- 力扣

【栈和队列】算法题 ---- 力扣(一)https://developer.aliyun.com/article/1621386

三、用栈实现队列

       上一个题让我们用队列来实现栈,这个用两个栈来实现队列。

定义两个栈

思路:

       往PushST中插入数据,再将数据导入到PopST中,出栈即可;

       入队列:往PushST中插入数据

       出队列:判断栈PopST是否为空?如果PopST栈为空,就将栈PushST中数据导入到栈PopST中去,再让栈PopST出栈操作;如果不为空,直接让栈PopST出栈操作即可。

       取队头数据:和出队列操作一样,只是不需要出栈操作,只取数据

分析:

       假设依次插入了1,2,3三个数据,现在出栈一次,再插入一个数据4,最后取队头数据,依次出栈。

       出栈一次,PopST为空,就将PushST中数据导入到PopST中去。

依次导入

       出栈;

再插入数据4

取队头数据:

最后依次出队列

现在,PopST栈为空,就要先将PushST中数据先导入到PopST中。

再出队列

力扣题代码如下:

typedef int SType;
typedef struct Stack
{
  SType* arr;
  int size;  //栈顶
  int num;   //空间大小
}Stack;
//初始化
void STInit(Stack* ps)
{
  assert(ps);
  ps->arr = NULL;
  ps->size = ps->num = 0;
}
//判断栈是否为空
bool STEmpty(Stack* ps)
{
  assert(ps);
  return ps->size == 0;
}
//入栈
void STPush(Stack* ps, SType x)
{
  assert(ps);
  //判断空间大小是否足够
  if (ps->num <= ps->size)
  {
    int newnum = (ps->num == 0) ? 4 : ps->num * 2;
    SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack));
    if (tmp == NULL)
    {
      perror("realloc filed");
      exit(1);
    }
    ps->arr = tmp;
    ps->num = newnum;
  }
  ps->arr[ps->size++] = x;
}
//出栈
void STPop(Stack* ps)
{
  assert(ps); //不能传NULL
  assert(!STEmpty(ps));  //栈不能为空
  ps->size--;
}
//取栈顶数据
SType STtop(Stack* ps)
{
  return ps->arr[ps->size - 1];
}
//获取栈中数据个数
int STSize(Stack* ps)
{
  assert(ps);
  return ps->size;
}
//栈的销毁
void STDesTroy(Stack* ps)
{
  assert(ps);
  if (ps->arr)
    free(ps->arr);
  ps->arr = NULL;
  ps->size = ps->num = 0;
}
 
 
typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;
 
//初始化
MyQueue* myQueueCreate() {
    MyQueue* Queue=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&Queue->s1);
    STInit(&Queue->s2);
    return Queue;
}
//插入数据
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    STPush(&obj->s1, x);
}
 
int myQueuePop(MyQueue* obj) {
    assert(obj);
    if(STEmpty(&obj->s2))
    {
        //把s1中数据导入到s2
        while(!STEmpty(&obj->s1))
        {
            STPush(&obj->s2,STtop(&obj->s1));
            STPop(&obj->s1);
        }
    }
    int ret=STtop(&obj->s2);
    STPop(&obj->s2);
    return ret;
}
 
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->s2))
    {
        //把s1中数据导入到s2
        while(!STEmpty(&obj->s1))
        {
            STPush(&obj->s2,STtop(&obj->s1));
            STPop(&obj->s1);
        }
    }
    return STtop(&obj->s2);
}
 
bool myQueueEmpty(MyQueue* obj) {
    return (STEmpty(&obj->s1)) && (STEmpty(&obj->s2));
}
 
void myQueueFree(MyQueue* obj) {
    if(obj)
        free(obj);
    obj=NULL;
}

四、设计循环队列

       设计循环队列,这里使用数组来设计

这里会设计到的一些问题:

       插入数据,如何判断空间是否满了?      

这里多申请一个空间,便于判断空间是否满了

       删除数据,如何去删?

这里,删除front指向的数据,就是队头数据

详细代码如下:

 
typedef struct {
    int* arr;
    int front;
    int rear;
    int num;
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->arr = malloc((k + 1) * sizeof(int));
    pq->front = pq->rear = 0;
    pq->num = k;
    return pq;
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
 
    return (obj->rear == obj->front);
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->num + 1) == obj->front;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
 
    if (myCircularQueueIsFull(obj)) // 队列满了
    {
        return false;
    }
    // 插入数据
    obj->arr[obj->rear++] = value;
    obj->rear %= (obj->num + 1);
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
    obj->front++;
    obj->front %= (obj->num + 1);
    return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    int ret=obj->rear-1;
    if(obj->rear==0)
    {
        ret=obj->num;
    }
    return obj->arr[ret];
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
    obj = NULL;
}

感谢各位大佬支持并指出问题,

                      如果本篇内容对你有帮助,可以一键三连支持以下,感谢支持!!!

相关文章
|
2月前
|
存储 算法
【栈和队列】算法题 ---- 力扣(一)
【栈和队列】算法题 ---- 力扣
|
2月前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
2月前
|
算法
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
2月前
|
算法
【顺序表】算法题 --- 力扣
【顺序表】算法题 --- 力扣
|
5月前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
39 3
|
7月前
题目----力扣--链表的中间结点
题目----力扣--链表的中间结点
31 0
|
7月前
题目----力扣--反转链表
题目----力扣--反转链表
33 0
|
7月前
|
存储 算法 索引
LeetCode刷题---链表经典问题(双指针)
LeetCode刷题---链表经典问题(双指针)
|
图计算 索引 容器
leetcode100----双指针
leetcode100----双指针