队列实现栈VS栈实现队列

简介: 队列实现栈VS栈实现队列



昨天导游考试考完啦!!希望明年是导游小唐!!🙂当然,代码我们不能忘敲代码!!

【1】用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

思路分析

 

  • 压栈:把元素放到不为空的队列里面。(两者若都为空随便放一个)
  • 出栈:把不为空的队列里面元素>1,全部导入另外一个为空队列里面,Pop最后元素。

易错总结

  • 创建的临时变量出了作用域就销毁了,所以需要malloc才可。
  • 类型匹配的问题
  • 假设法的使用
  • 销毁的时候要先销毁队列开辟的空间,不然会造成野指针。
  • 匿名结构体
  • 耦合性
  • -> 优先级高于&

Queue.c&Queue.h手撕队列

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
//创建队列节点
typedef struct QueueNode
{
  QDataType val;
  struct QueueNode* next;
}QNode;
//两个指针维护链表队列
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  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);//判断队列是否是否为NULL
int QueueSize(Queue* pq);//队列里面的元素个数
//不需要头节点,初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}
QNode* Createnode(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  newnode->val = x;
  newnode->next = NULL;
  return newnode;
}
//Push元素
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //创建节点
  QNode* newnode = Createnode(pq,x);
  if (pq->phead == NULL)
  {
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}
//Pop元素
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->phead);//为NULL的判断
  QNode* cur = pq->phead;
  pq->phead = pq->phead->next;
  free(cur);
  cur = NULL;
  //为一个节点的判断
  if (pq->phead == NULL)
  {
    pq->ptail = NULL;
  }
  pq->size--;
}
//队头元素
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
  return pq->phead->val;
}
//队尾元素
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->ptail);
  return pq->ptail->val;
}
//判断是否为NULL
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->phead == NULL;//return pq->size == 0
}
//队员元素个数
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
//空间释放
void QueueDestroy(Queue* pq)
{
  assert(pq);
  while (pq->phead)
  {
    QNode* cur = pq->phead;
    pq->phead = pq->phead->next;
    free(cur);
    cur = NULL;
  }
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}

在之前的博文里面,我们详细的阐述了单链表实现【队列】的实现。这里就不在过多解释了。这里我们来用【两个队列】实现一个【栈】🆗!

声明栈MyStack

//匿名结构体
typedef struct {
    Queue Q1;
    Queue Q2;
} MyStack;//结构体类型
//一级指针修改结构体变量
struct {
    Queue Q1;
    Queue Q2;
} MyStack;//结构体变量

创建&初始化栈myStackCreate

//初始化
MyStack* myStackCreate() {
    //MyStack mystack;出了作用域就销毁了
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->Q1);
    QueueInit(&obj->Q2);
    return obj;
}

压栈myStackPush

//放元素
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //找不为NULL的队列依次插入
    if(!QueueEmpty(&obj->Q1))//!=0
    {
        QueuePush(&obj->Q1, x);//尾插
    }
    else//== 0
    {
        QueuePush(&obj->Q2, x);
    }
    //两个==0 随便进一个
}

出栈&返回栈顶元素myStackPop

//出元素
int myStackPop(MyStack* obj) {
    assert(obj);
    //判断为空/非空------假设法
    Queue*nonempty=&obj->Q1;
    Queue*empty=&obj->Q2;
    if(QueueEmpty(&obj->Q1))//==0true与上面逻辑相反//出了作用域就销毁了姐姐❌
    {
        nonempty=&obj->Q2;
        empty=&obj->Q1;//创建
    }
    while(QueueSize(nonempty)>1)//队列里面的元素个数 > 1
    {
        int x = QueueFront(nonempty);//队列头的元素
        QueuePush(empty, x);//放元素到队列尾
        QueuePop(nonempty);//出元素到队头
    }
    int Back=QueueFront(nonempty);//队列尾的元素
    QueuePop(nonempty);
    return Back;
}

返回栈顶元素myStackTop

//栈顶元素
int myStackTop(MyStack* obj) {
  if(!QueueEmpty(&obj->Q1)) 
  {
    return QueueBack(&obj->Q1);
  }
  else
  {
    return QueueBack(&obj->Q2);
  }
}

判断栈空否myStackEmpty

//判空
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->Q1) && QueueEmpty(&obj->Q2);//&&
}

释放空间myStackFree

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->Q1);
    QueueDestroy(&obj->Q2);
    free(obj);
    obj=NULL;
}

MyStack总代码

typedef struct {
    Queue Q1;
    Queue Q2;
} MyStack;
//一级指针修改结构体变量
//初始化
MyStack* myStackCreate() {
    //MyStack mystack;出了作用域就销毁了
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->Q1);
    QueueInit(&obj->Q2);
    return obj;
}
//放元素
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //找不为NULL的队列依次插入
    if(!QueueEmpty(&obj->Q1))//!=0
    {
        QueuePush(&obj->Q1, x);//尾插
    }
    else//== 0
    {
        QueuePush(&obj->Q2, x);
    }
    //两个==0 随便进一个
}
//出元素
int myStackPop(MyStack* obj) {
    assert(obj);
    //判断为空/非空------假设法
    Queue*nonempty=&obj->Q1;
    Queue*empty=&obj->Q2;
    if(QueueEmpty(&obj->Q1)
    {
        nonempty=&obj->Q2;
        empty=&obj->Q1;//创建
    }
    while(QueueSize(nonempty)>1)//队列里面的元素个数 > 1
    {
        int x = QueueFront(nonempty);//队列头的元素
        QueuePush(empty, x);//放元素到队列尾
        QueuePop(nonempty);//出元素到队头
    }
    int Back=QueueFront(nonempty);//队列尾的元素
    QueuePop(nonempty);
    return Back;
}
//栈顶元素
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) {
    QueueDestroy(&obj->Q1);
    QueueDestroy(&obj->Q2);
    free(obj);
    obj=NULL;
}

【2】用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

思路分析

  • 一个栈S1用来专门入数据Push
  • 另外一个栈S2用来专门出数据Pop(S2为空的时候才能把S1的数据导入S2 直到S1为空)
  • S2不为空的时候直接出数据即可
  • 队列出数据的顺序性质 == 栈导入另外一个栈出数据的顺序

易错总结

  • 创建的临时变量出了作用域就销毁了,所以需要malloc才可。
  • 类型匹配的问题
  • 销毁的时候要先销毁队列开辟的空间,不然会造成野指针。
  • 匿名结构体
  • 耦合性
  • -> 优先级高于&
  • !STempty(&obj->stackpush))//!=0 flase---true开始导 直到==0 true
  • 结构体和结构体指针

Stack.h&Stack.c手撕栈

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int top;
  int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);
void STInit(ST* pst)
{
  assert(pst);
  pst->a = 0;
  pst->top = 0;
  pst->capacity = 0;
}
void Createcapacity(ST* pst)
{
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
    STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(ST) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
}
void STPush(ST* pst, STDatatype x)
{
  assert(pst);
  Createcapacity(pst);
  pst->a[pst->top] = x;
  pst->top++;
}
void STPop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  pst->top--;
}
STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  return pst->a[pst->top-1];
}
bool STempty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}

同样我们之前用数组实现了【栈】,这里我们在来用两个栈实现【队列】 。

声明队列MyQueue

typedef struct {
    ST stackpush;
    ST stackpop;
} MyQueue;

创建&初始化队列myQueueCreate

MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->stackpush);
    STInit(&obj->stackpop);
    return obj;
}

入队列myQueuePush

//入队列
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->stackpush, x);
}

返回队头元素myQueuePeek

//取出队列的数据 --所以可以先实现这个
int myQueuePeek(MyQueue* obj) {
  if(STempty(&obj->stackpop))//==0 true为空导数据
  {
    while(!STempty(&obj->stackpush))//!=0//!=0 flase---true开始导 直到==0 true ---false
    {
      int x=STTop(&obj->stackpush);
      STPush(&obj->stackpop,x);
      STPop(&obj->stackpush);
    }
  }
  return STTop(&obj->stackpop);
}

出队列&返回队头元素myQueuePop

//出队列 为NULL就导数据/出队列  不为NULL出队列
int myQueuePop(MyQueue* obj) {
    int back=myQueuePeek(obj);
    STPop(&obj->stackpop);
    return back;
}

判断队列空否myQueueEmpty

bool myQueueEmpty(MyQueue* obj) {
    return STempty(&obj->stackpush) && STempty(&obj->stackpop);
}

释放空间myQueueFree

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->stackpush);
    STDestroy(&obj->stackpop);
    free(obj);
    obj=NULL;
}

MyQueue总代码

typedef struct {
    ST stackpush;
    ST stackpop;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->stackpush);
    STInit(&obj->stackpop);
    return obj;
}
//入队列
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->stackpush, x);
}
//取出队列的数据 --所以可以先实现这个
int myQueuePeek(MyQueue* obj) {
  if(STempty(&obj->stackpop))//==0 true为空导数据
  {
    while(!STempty(&obj->stackpush))//!=0//!=0 flase---true开始导 直到==0 true ---false
    {
      int x=STTop(&obj->stackpush);
      STPush(&obj->stackpop,x);
      STPop(&obj->stackpush);
    }
  }
  return STTop(&obj->stackpop);
}
//出队列 为NULL就导数据/出队列  不为NULL出队列
int myQueuePop(MyQueue* obj) {
    int back=myQueuePeek(obj);
    STPop(&obj->stackpop);
    return back;
}
//
bool myQueueEmpty(MyQueue* obj) {
    return STempty(&obj->stackpush) && STempty(&obj->stackpop);
}
void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->stackpush);
    STDestroy(&obj->stackpop);
    free(obj);
    obj=NULL;
}
  • 不要对比代码!怎么想怎么写!
  • 调试很重要!调式:按照自己预期的去走读代码(最后上编译器)
  • 编译出错:运行的问题
  • 执行错误:逻辑的问题

✔✔✔✔✔最后,感谢大家的阅读,若有错误和不足,欢迎指正!

【数组栈】实现-CSDN博客

单链表实现【队列】-CSDN博客

目录
相关文章
|
12天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
29 0
|
13天前
|
存储 算法 索引
【算法与数据结构】队列的实现详解
【算法与数据结构】队列的实现详解
|
5天前
|
存储 算法 调度
数据结构期末复习(3)栈和队列
数据结构期末复习(3)栈和队列
13 0
|
17天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
|
17天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
|
17天前
|
存储 缓存 算法
【算法与数据结构】栈的实现详解
【算法与数据结构】栈的实现详解
|
17天前
|
存储 算法 编译器
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。
49 0

热门文章

最新文章