自学内容网 自学内容网

队列实现栈与栈实现队列


前言

1、用于巩固栈和队列。
2、本章是使用纯C语言实现的栈和队列,不懂的可以先看看这个喔:c语言实现栈和队列,当然这里直接用C++的栈和队列会更方便哦。
3、利于复习C语言的知识点。

一、使用队列实现栈

1·、题目链接:用队列实现栈
2、题目描述:

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

3、例子:
在这里插入图片描述
4、题目分析:

(1)队列的操作是先进先出并且队头出,队尾进,而栈相反是先进后出,栈顶出,栈顶入
(2)题目要求我们使用两个队列来实现这个栈的一些操作,如:push,pop等。 我们可以使用两个队列进行倒数据:
(3)进栈:将数据储存到有数据的队列里队尾(要是两个队列都为空的话随便进一个就行喔)
(4)出栈:将有数据的队列往没有数据的队列里倒,直到剩下一个数据之后停止倒数据,进行队列的出队操作即可将最后进的数据删除(也就是出栈)。
(5)取栈顶元素:查看有数据队列的队头即可。 (6)判断栈是否为空:即判断两个队列是否为空即可,两个队列为空栈就为空,不然就是不为空。

5、图解:
进栈:
在这里插入图片描述
出栈:
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/b9c9ef27c88b445ba0d12f329af7451f.png

6、参考代码:

typedef  int QDataType;
// 链式结构:表示队列 
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

// 初始化队列 
void QueueInit(Queue* q)
{
q->_front = NULL;
q->_rear = NULL;
q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
assert(q);
//生成节点
QNode* tmp = (QNode*)malloc(sizeof(QNode));
if (tmp == NULL)
{
perror("err");
return;
}
tmp->_data = data;
tmp->_next = NULL;
//没有节点
if (q->_front ==NULL)
{
q->_front = q->_rear = tmp;
}
//有节点
else
{
 q->_rear->_next=tmp;
 q->_rear = tmp;
}
q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
assert(q);
//队列为空
assert(q->_front);
//队列只有一个元素或多个元素
if (q->_front == q->_rear)
{
q->_front = q->_rear = NULL;
}
else
{
QNode* next = q->_front->_next;
free(q->_front);
q->_front = next;
}
q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->_front);
return q->_front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->_rear);
return q->_rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
assert(q);
QNode* tmp = q->_front;
while (tmp!=NULL)
{
QNode* next = tmp->_next;
free(tmp);
tmp = next;
}
q->_front=q->_rear= NULL;
q->size = 0;
}

//栈的结构体,因为通过两个队列来实现,所以成员为2个队列
typedef struct {
    Queue  q1;
    Queue  q2;
} MyStack;



/
//主要部分在下面,上面的是队列




//初始化栈
MyStack* myStackCreate() {
    //动态申请一个栈,如果直接创建 MyStack st 的话,这个栈会随着函数销毁而销毁,但是动态申请就不会
    MyStack *st=(MyStack*)malloc(sizeof(MyStack));
    //初始化两个队列
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

//进栈
void myStackPush(MyStack* obj, int x) {
    //往不为空的队列进
    if(!QueueEmpty(&obj->q1))
    {
      QueuePush(&obj->q1,x);
    }
    else
    {
      QueuePush(&obj->q2,x);
    }
}


//出栈
int myStackPop(MyStack* obj) {
     //将不为空的队列往空的队列倒,直到只剩下一个元素
     //假设p1是为空的队列 
     Queue *p1=&obj->q1;
     Queue *p2=&obj->q2;
     //假设不成立进行修正
     if(!QueueEmpty(p1))
     {
         p1=&obj->q2;
         p2=&obj->q1;
     }

     //倒数据
     while(QueueSize(p2)>1)
     {
          QueuePush(p1,QueueFront(p2));
          QueuePop(p2);
     }
     //先将最后一个保存再弹出
       int tmp=QueueBack(p2);
         QueuePop(p2);
         return tmp;
    
}

//取栈顶的元素
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;
}

二、使用栈实现队列

1、题目链接:栈实现队列
2、题目描述:

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

实现 MyQueue 类:

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

3、例子:
在这里插入图片描述
4、题目分析:

(1)通过两个栈来实现队列的push、pop等操作。
(2)我们可以固定一个栈(sta1)保存数据(进行入队操作),另一个栈(sta2)来进行展现队头数据和出队头的操作,当要展现队头数据和出队头的操作时,如果sta2为不空的话就展示栈顶的元素或者出栈,当sta2为空时就将sta1的数据倒到sat2里,再进行不为空的操作。
(3)取队头元素:直接取sta2的栈顶数据,(如果sta2为空的话就要将sta1的数据倒到sta2再取)
(4)判断队列是否为空:通过判断两个栈是否存在元素来判断是否为空,两个都为空即为空。

5、图解:
在这里插入图片描述
6、参考代码:

typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top;// 栈顶
int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

// 初始化栈 
void StackInit(Stack* ps)
{
    assert(ps);
    ps->_capacity = 0;
    ps->_a = NULL;
    ps->_top = 0;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
    //满了扩容
    if (ps->_capacity == ps->_top)
    {
        int size = 0;
        if (ps->_capacity == 0)
        {
                 size = 4;
        }
        else
        {
            size = ps->_capacity * 2;
        }
        STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * size);
        //判断
        if (tmp == NULL)
        {
            perror("err");
            return ;
        }
        ps->_a = tmp;
        ps->_capacity = size;
    }
    //入栈
    ps->_a[ps->_top] = data;
    ps->_top++;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->_top);
    return ps->_a[ps->_top - 1];
}

// 出栈 
void StackPop(Stack* ps)
{
    assert(ps);
    //栈为空 
    assert(ps->_top);
    ps->_a[ps->_top - 1] = 0;
    //栈不为空
    ps->_top--;
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->_top;
}

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->_top == 0;
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->_a);
    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}





//
//下面是主要部分,上面是栈





typedef struct {
    //存数据
     Stack sta1;
    //倒数据
     Stack sta2;
} MyQueue;

//初始化队列
MyQueue* myQueueCreate() {
    MyQueue* tmp=(MyQueue*)malloc(sizeof(MyQueue));
    //初始化两个栈
    StackInit(&tmp->sta1);
    StackInit(&tmp->sta2);
    //返回队列
      return tmp;
}
//进队
void myQueuePush(MyQueue* obj, int x) {
   //压进储存数据的sta1
    StackPush(&obj->sta1,x);
}

int myQueuePop(MyQueue* obj) {
    //sta2为空就倒数据
    int tmp=0;
    if(StackEmpty(&obj->sta2))
    {
     while(!StackEmpty(&obj->sta1))
    {
       StackPush(&obj->sta2,StackTop(&obj->sta1));
       StackPop(&obj->sta1);
    }  
    }
    //保存队头数据
    tmp=StackTop(&obj->sta2);
    //出队
     StackPop(&obj->sta2);
        return tmp;
}

int myQueuePeek(MyQueue* obj) {
    //sta2为空就倒数据
     if(StackEmpty(&obj->sta2))
     {
    while(!StackEmpty(&obj->sta1))
    {
       StackPush(&obj->sta2,StackTop(&obj->sta1));
       StackPop(&obj->sta1);
    }
     }
   //返回队头数据,不用出队
    int tmp=StackTop(&obj->sta2);
        return tmp;
}

//判断是否为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->sta1)&&StackEmpty(&obj->sta2);
}

//销毁队列
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->sta1);
    free(obj);
    obj=NULL;
}

以上就是分享的内容了,如有错误,评论区留言。

最后 ,谢谢大家的观看!


原文地址:https://blog.csdn.net/2302_79539362/article/details/136399907

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!