数据结构刷题训练:队列实现栈

简介: 数据结构刷题训练:队列实现栈

前言

       我们已经学习了栈和队列,也都实现了它们各自的底层接口,那么接下我们就要开始栈和队列的专项刷题训练。


1. 题目:使用队列实现栈

题目描述:

题目链接:

2. 思路

       队列的结构是先进先出,题目的要求是,让我们利用队列的底层接口来实现栈,不可以改变队列的底层逻辑,所以如果你的思路是逆置队列这个链表,那这个思路就被pass掉了。

        那我们要如何利用队列尾进头出的特性来实现栈的尾进尾出呢?题目中给了我们两个队列,我们要使用这两个队列实现栈。

       入栈操作好说,问题在于出栈问题,思路是这样的:我们有两个队列,一个队列用于存储数据,另外一个队列(空队列)用于拷贝数据,将原队列的前n-1个数据拷贝到空队列中,然后再将原队列剩余的最后一个元素出队列,这样就模拟实现了栈的尾出


 

3. 分析

        根据上述的思路分析,队列实现栈,入栈不需要什么特殊操作例如我们入栈:1、2、3、4、5,出栈呢就是:5、4、3、2、1。

       上述的思路已经介绍了解决办法,也是非常简单的,但有人可能会问:那这样算法的效率岂不是很低?这种方法的效率确实低,但是这道题目考察的并不是效率的问题,而实性质问题,这也是一道经典的面试题目。这道题目并不难,但它考察对数据结构的理解,各各接口的实现中有很多需要注意的细节。

       首先这道题目是并没有给现成的队列,使用C语言解决需要我们现成造轮子,这也是C语言刷题的弊端,有很多题目都需要造轮子。那么这里我们就可以直接复制前边我们实现的队列。

接下来就是我们开始注意实现接口:

        首先题目中给了我们两个队列,为了便于传参和使用,我们可以定义一个结构体:

typedef struct {
Que q1;    //注意这里定于的队列类型一定要与自己定义的队列结构体类型对应
Que q2;
} MyStack;

这里我们在前边介绍结构体时提到过,匿名结构体。

3.1 创建栈

MyStack* myStackCreate() {
}

题目给出的接口如上,那这里我们要怎么创建我们的栈呢?是这样吗?

MyStack* myStackCreate() {
    MyStack st;
    //…
    return &st;
}

        对函数和指针比较熟悉的同学可能就已经发现不行,为什么不行?这里就牵扯到了函数相关的知识,函数内创建的变量都是存储在栈区,出了函数就会被销毁,内存已经被销毁,返回指针还有什么意义呢?所以这里需要使用malloc函数,动态内存分配开辟的空间在堆区,程序结束前不主动释放就一直存在。所以上述的创建变量的方法不可取。

正确的方法:

MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

        这里的pst->q1,就等价于我们在创建的队列的结构体变量:Que q;在调用接口时需要传地址过去。

3.2入栈

       接下来就是入栈,题目中给了我们两个队列,为了后续出栈操作我们需要确保一个队列为空,用于拷贝数据,所以我们入栈时需要在不为空的队列入。

void myStackPush(MyStack* obj, int x) {
    if(!IsEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

如果两个都为空那就随便选一个都可以。

3.3 出栈

       在进行出栈操作的时候,我们需要判断哪一个队列为空,然后将非空队列的前n-1个元素依次拷贝到空队列当中。这里我们可以先假设队列1为空,然后在判断队列1是否为空,如果不为空那就是队列2为空,进行修改。这个假设的方法还是很实用的。

拷贝过程如下:

       注意这里是拷贝,不是将原队列的节点插入到空队列,而是通过队头数据这个函数接口来将数据传过去,然后入队(调用入队接口),入队之后及时更新队头(出队)。

 

int myStackPop(MyStack* obj) {
    Que* Empty=&obj->q1;
    Que* NoEmpty=&obj->q2;
    if(!IsEmpty(&obj->q1))
    {
        Empty=&obj->q2;
        NoEmpty=&obj->q1;
    }
    while(QueueSize(NoEmpty)>1)
    {
        QueuePush(Empty,QueueFront(NoEmpty));
        QueuePop(NoEmpty);
    }
    int top=QueueFront(NoEmpty);//最后保存非空队列最后一个队列节点的数据,便于返回
    QueuePop(NoEmpty);          //最后一个元素出队。
    return top;
}

3.4 栈顶数据

        栈顶数据接口实现就简单了,我们前边对队列进行实现时,有队头和队尾数据的接口,我们可以直接调用。

int myStackTop(MyStack* obj) {
    if(!IsEmpty(&obj->q1))
    {
        return QueueBlack(&obj->q1);
    }
    else
    {
        return QueueBlack(&obj->q2);
    }
}

3.5 判空和 “ 栈 ” 的销毁

        判空就很简单,如果两个队列都为空,那么这个 “ 栈 ” 也就为空。

bool myStackEmpty(MyStack* obj) {
    return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2));
}

        “ 栈 ”的销毁,这里就不能直接free掉obj了,如果直接释放那我们程序中的两个队列就会丢失无法释放,所以在释放掉obj之前,我们需要先将两个队列销毁。

void myStackFree(MyStack* obj) {
    DestoryQueue(&obj->q1);
    DestoryQueue(&obj->q2);
    free(obj);
}

4. 题解

完整代码如下:

typedef int Datatype;
typedef struct QueueNode
{
  struct QueueNode* next;
  Datatype data;
 }QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
  int size;
}Que;
//初始化队列
void QueueInit(Que* pq);
//入队
void QueuePush(Que* pq, Datatype x);
//出队
void QueuePop(Que* pq);
//队头数据
Datatype QueueFront(Que* pq);
//队尾数据
Datatype QueueBlack(Que* pq);
//判空
bool IsEmpty(Que* pq);
//队列大小
int QueueSize(Que* pq);
//销毁队列
void DestoryQueue(Que* pq);
void QueueInit(Que* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Que* pq, Datatype x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  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(Que* pq)
{
  assert(pq);
  assert(!IsEmpty(pq));
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QueueNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  pq->size--;
}
Datatype QueueFront(Que* pq)
{
  assert(pq);
  assert(!IsEmpty(pq));
  return pq->head->data;
}
Datatype QueueBlack(Que* pq)
{
  assert(pq);
  assert(!IsEmpty(pq));
  return pq->tail->data;
}
bool IsEmpty(Que* pq)
{
  assert(pq);
  return (pq->head == NULL);
}
int QueueSize(Que* pq)
{
  assert(pq);
  return pq->size;
}
void DestoryQueue(Que* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
typedef struct {
Que q1;
Que q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}
void myStackPush(MyStack* obj, int x) {
    if(!IsEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj) {
    Que* Empty=&obj->q1;
    Que* NoEmpty=&obj->q2;
    if(!IsEmpty(&obj->q1))
    {
        Empty=&obj->q2;
        NoEmpty=&obj->q1;
    }
    while(QueueSize(NoEmpty)>1)
    {
        QueuePush(Empty,QueueFront(NoEmpty));
        QueuePop(NoEmpty);
    }
    int top=QueueFront(NoEmpty);
    QueuePop(NoEmpty);
    return top;
}
int myStackTop(MyStack* obj) {
    if(!IsEmpty(&obj->q1))
    {
        return QueueBlack(&obj->q1);
    }
    else
    {
        return QueueBlack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) {
    return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2));
}
void myStackFree(MyStack* obj) {
    DestoryQueue(&obj->q1);
    DestoryQueue(&obj->q2);
    free(obj);
}

 

总结

       本文队列模拟实现栈,让我们在实践中深入思考了数据结构的本质和应用,为我们的编程能力和问题解决能力提供了锻炼。本期内容到此结束,感谢阅读!

相关文章
|
6月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
178 1
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
75 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
8月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
190 11
|
8月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
11月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
931 9
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
239 59
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
367 77
|
9月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
292 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
154 9

热门文章

最新文章