数据结构——3道栈和队列OJ题(上)

简介: 笔记

习题1 用队列实现栈


225. 用队列实现栈 - 力扣(LeetCode)


1.把有数据队列的内容,传到没数据的队列中,传一个之后,再原队列中删一个


2.等q1中剩一个元素的时候,让这个元素出队


这样就可以达到栈的效果,1,2,3,4,5,让5先出栈,之后再按照同样的方法把q1看作空(压栈的时候要往有元素的队里压),开始倒数据即可  1.png2.png3.png

队列的实现

typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode *head;
  QNode* tail;
  size_t size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(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 QueueDestory(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, QDataType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
  pq->head = pq->tail = newnode;
  }
  else
  {
  pq->tail->next = newnode;
  pq->tail = pq->tail->next;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }//如果只剩一个节点,单独处理,防止tail变为野指针
  else
  {
  QNode* cur = pq->head;
  pq->head = pq->head->next;
  free(cur);
  cur = NULL;
  }
  pq->size--;
}
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;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head==NULL && pq->tail==NULL;
}
int QueueSize(Queue* pq)
{
  return pq->size;
}


通过队列实现栈

结构体的建立

typedef struct {
Queue q1; //建立俩个
Queue q2;
} MyStack;
//也可用Queue*,但是这样的话要用malloc给q1和q2开辟空间

初始化

MyStack* myStackCreate() {
    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);
    }//如果q1不是空,把元素压到q1
    else
    {
         QueuePush(&obj->q2,x);
    }
}

出栈

int myStackPop(MyStack* obj) {
   Queue *empty=&obj->q1;//假设q1为空
    Queue *noempty=&obj->q2;//假设q2不是空
    if(!QueueEmpty(&obj->q1))
    {
        noempty=&obj->q1;
        empty=&obj->q2;
 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->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) {
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}

这里不能直接free(obj),因为q1和q2是链表,链表的内存不连续,如果释放掉boj,则q1和q2没有释放,会造成内存泄漏


用队列实现栈

232. 用栈实现队列 - 力扣(LeetCode)


4.png

若队列中是1 2 3 4 5,则按照栈的规则,此时出栈顺序应该是 5 4 3 2 1,我们可以用俩个队列来实现栈

1.把PushST里面的数据倒到PopST

2.出栈的时候,我们只需要出PopST里面的元素就可以,当有元素要填充时,填充到PushST就行

5.png 栈的实现

typedef int STDdtaTtype;
typedef struct Stcak
{
  STDdtaTtype* data;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDdtaTtype x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDdtaTtype StackTop(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->data = NULL;
  ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
  assert(ps);
  free(ps->data);
  ps->capacity = ps->top = 0;
  ps->data = NULL;
}
void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1
{
  assert(ps);
  int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  if (ps->capacity == ps->top)//判断是否满了
  {
  STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity);
  if (tmp == NULL)
  {
    perror("realloc fail");
    exit(-1);
  }
  ps->data = tmp;
  ps->capacity = newcapacity;
  }
  ps->data[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}
STDdtaTtype StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->data[ps->top - 1];
}
bool StackEmpty(ST* ps)//判断是否为空栈
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}


结构体创建

typedef struct {
ST PushST;
ST PopST;
} MyQueue;

结构体的初始化

MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->PushST);
StackInit(&obj->PopST);
return obj;
}


相关文章
|
1天前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
14 2
|
23小时前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
16 7
|
23小时前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
16 0
|
1天前
|
C语言
数据结构------栈(Stack)和队列(Queue)
数据结构------栈(Stack)和队列(Queue)
10 0
|
1天前
|
编译器 Linux C语言
第五章 栈与队列
第五章 栈与队列
9 0
|
1天前
03(数据结构考研)队列相关操作代码
03(数据结构考研)队列相关操作代码
9 0
|
6天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
81 64
|
15天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
6天前
|
Go
数据结构之 - 深入了解栈数据结构
数据结构之 - 深入了解栈数据结构
16 5
【数据结构】--- 栈和队列
【数据结构】--- 栈和队列