欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

用队列实现栈

程序员文章站 2024-01-28 21:44:10
...

使用队列实现栈的下列操作:

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空
解题思路:
栈是一种 后进先出的数据结构,栈内元素从顶端压入,从顶端弹出。队列是一种与栈相反的 先进先出的数据结构,队列中元素只能从后端入队,然后从前端端出队。为了满足栈的特性,我们需要维护两个队列 q1 和 q2。同时,我们用一个额外的变量来保存栈顶元素。

出队操作:
例如q1非空q2空,让q1的元素除最后一个入到请q2中,再将q1的最后一个弹出就行。
入队操作:
只需要元素进入非空的队列就行用队列实现栈

#include <stdlib.h>
#define LEN 20
typedef struct queue{
    int* data;
    int head;
    int rear;
    int size;
}Queue;

typedef struct {
    Queue *q1,*q2;
} MyStack;

//初始化
Queue* InitQueue(int k)
{
    Queue* obj=(Queue*)malloc(sizeof(Queue));
    obj->data=(int*)malloc(sizeof(int)*k);
    obj->head=-1;
    obj->rear=-1;
    obj->size=k;
    return obj;
}
//插入数据
void enQueue(Queue* obj,int e)
{
    //不用考虑队列还是是否满了
    //对列为空
    if(obj->head==-1)
    {
        obj->head=0;
    }
    //队列一般情况
    obj->rear=(obj->rear+1)%obj->size;
    obj->data[obj->rear]=e;
}
//出队
int deQueue(Queue* obj)
{
    //出对不用考虑空
    int a=obj->data[obj->head];
    //只有一个元素
    if(obj->head==obj->rear)
    {
        obj->head=-1;
        obj->rear=-1;
        return a;
    }
    //队列一般情形
    obj->head=(obj->head+1)%obj->size;
    return a;
}
//判空
int isEmpty(Queue* obj)
{
    return obj->head==-1;
}
/** Initialize your data structure here. */

MyStack* myStackCreate() {
    MyStack *obj=(MyStack *)malloc(sizeof(MyStack));
    obj->q1=InitQueue(LEN);
    obj->q2=InitQueue(LEN);
    return obj;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    //只要我找到一个队列为非空,我就向里面添加元素,如果两个都是空的,那随便哪一个都可以
    if(isEmpty(obj->q1))
    {
        enQueue(obj->q2,x);
    }
    else
    {
        enQueue(obj->q1,x);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
  //栈弹出的时候,有且只有一个队列为非空
    if(isEmpty(obj->q1))
    {    //q2为非空的时候,q2出列直到q2中只有一个元素

        while(obj->q2->head!=obj->q2->rear)
        {            //q2出列的元素,入列q1

            enQueue(obj->q1,deQueue(obj->q2));
        }
        return deQueue(obj->q2);
    }
    else
    {
        while(obj->q1->head!=obj->q1->rear)
        {            //q1出列的元素,入列q2

            enQueue(obj->q2,deQueue(obj->q1));
        }
        return deQueue(obj->q1);
    }
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
  //取栈顶元素,有且只有一个队列为非空,我直接取非空队列的尾部即可
    if(isEmpty(obj->q1)){
        return obj->q2->data[obj->q2->rear];
    }
    return obj->q1->data[obj->q1->rear];
}


/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
  if(obj->q1->head==-1 && obj->q2->head==-1){
      return true;
  }
  return false;
}

void myStackFree(MyStack* obj) {
    free(obj->q1->data);
    obj->q1->data=NULL;
    free(obj->q1);
    obj->q1=NULL;
    free(obj->q2->data);
    obj->q2->data=NULL;
    free(obj->q2);
    obj->q2=NULL;
    free(obj);
    obj=NULL;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/