#栈和队列相关oj(上)

简介: #栈和队列相关oj

写在前面:很久没更新博客了,没有其他原因,主要是懒(狗头保命),言归正传,由于我使用的是纯c语言,库中没有队列和栈所以要在做题前首先要创建队列或栈,因此首先在正文开始前附上队列和栈的代码实现,后续题目代码将不再贴有关栈和队列的实现代码。

栈的实现:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
  //类似于顺序表,数组,top,容量
  STDataType* a;
  int top;
  int capacity;
}ST;
//接口函数:判断是否为空,插入,删除,顶部,size
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* Ps);
STDataType top(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
void StackInit(ST* ps)
{
  //初始化,top和容量都置空
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
  assert(ps);
  //销毁链表释放a的空间
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  //插入数据要检查容量,但是因为只有一个插入函数,所以容量检查不用单独封装
  if (ps->top == ps->capacity)//说明要扩容
  {
    int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, newcapcity * sizeof(STDataType));
    if (tmp == NULL)//检查realloc是否成功
    {
      perror("realloc fail\n");
    }
    //扩容成功
    ps->a = tmp;
    ps->capacity = newcapcity;
  }
  //开始插入数据
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
STDataType top(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top-1];
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}

队列的实现:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QNDataType;
typedef struct QueueNode
{
  //使用单链表
  struct QueueNode* next;
  QNDataType data;
}QNode;
//链表的缺陷就在于尾插太麻烦,不如直接定义一个尾节点
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
//队尾入,队头出,与单链表的实现唯一的区别在于这个有两个结构体,什么时候用什么样的结构体定义变量要分清楚
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QNDataType x);
void QueuePop(Queue* pq);
QNDataType QueueFront(Queue* pq);
QNDataType 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);
    del = NULL;
  }
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QNDataType x)
{
  assert(pq);
  //要开辟一个节点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode==NULL)
  {
    perror("malloc fail\n");
    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;
  }
  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->head == NULL&&pq->head==NULL;
}
QNDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QNDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

 

本文目录

一.用队列实现栈

二.用栈实现队列

三.循环队列 

##一.用队列实现栈

题目链接

225.用队列实现栈

题目描述

仅用两个队列实现一个先入后出的栈,并支持栈的四种基本操作.

解题思路

队列是先进先出而栈要后进先出,题目给了两个队列,将所有元素插入到其中一个队列,另外一个为空队列,每次要删除元素时,把要删除元素前的所有元素push到非空队列中即可。

代码实现

typedef struct 
{//定义两个队列
  Queue q1;
  Queue q2;
} MyStack;
MyStack* myStackCreate() 
{
    //队列的初始化,要malloc
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}
void myStackPush(MyStack* obj, int x) 
{
    //要判断是否为空,往非空队列插入元素
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj) 
{
    //删除元素,要导数据,参考链表相交,设计两个指针
    Queue*empty=&obj->q1;
    Queue*nonempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        //q1不为空则说明假设错误,交换位置
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    //把nonempty中n-1个数据插到empty中
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        //要让nonempty的front后移
        QueuePop(nonempty);
    }
    //题目要求该函数要返回栈顶元素
    int top=QueueFront(nonempty);
    QueuePop(nonempty);
    return top;
}
int myStackTop(MyStack* obj)
{
    //判断非空,返回非空队列的back
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) 
{
    //两个都为空才为空
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) 
{
    //分开free
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    //obj=NULL;
}


相关文章
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
14天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
18天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
54 1
|
15天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
12 0
|
19天前
探索数据结构:队列的的实现与应用
探索数据结构:队列的的实现与应用
|
19天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
27天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
84 64
|
20天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
20天前
初步认识栈和队列
初步认识栈和队列
47 10
|
2月前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用