AI 助理
备案控制台
开发者社区 计算巢 文章 正文

☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼

2025-02-14 32
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ### 简介本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下：1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。

1·思路：
我们首先调用创建好的队列代码，然后假设令这两个队列作为一个栈，由于我们画图可以得出一个结论：

①当有两个空队列的时候，我们push时随便push，一直往不为空的队列里面push。

②当我们要移除并返回栈顶元素的时候，我们要把不为空的队列里n-1个元素push到另一个空的队列里面，最后得到将要pop与return的元素。

③只返回栈顶元素只需要返回不为空队列的尾指针指向的元素即可。

④判空的话，就是两个队列都为空才行。

2·画图理解：

3·代码解答：
typedef int qdatatype;
typedef struct Qnode {
struct Qnode next;
qdatatype data;
}Qnode;
typedef struct queue {
int size;
Qnode head;
Qnode* tail;
}queue;

void Queueinit(queue* p) {
assert(p);

p->head =p->tail = NULL;
p->size = 0;

}

void Queuedestroy(queue p) {
assert(p);
Qnode cur = p->head;
while (cur) {
Qnode* next = cur->next;
free(cur);
cur = next;
}
p->size = 0;
p->tail = p->head = NULL;
}

void Queuebackpush(queue p, qdatatype x) {
assert(p);
Qnode newnode = (Qnode*)malloc(sizeof(Qnode));
if (newnode == NULL) {
perror(malloc);
return;
}
newnode->next = NULL;
newnode->data = x;
if (p->tail == NULL) {
p->head = p->tail = newnode;
}
else {
p->tail->next = newnode;
p->tail = newnode;
}
p->size++;

}

void Queuefrontpop(queue p) {
assert(p);
assert(p->size > 0);
if (p->head->next == NULL) {
free(p->head);
p->head = p->tail = NULL;
}
else {
Qnode next = p->head->next;
free(p->head);
p->head = next;
}
p->size--;
}

qdatatype Queuefrontdata(queue* p) {
assert(p);
assert(p->size > 0);
return p->head->data;
}

qdatatype Queuebackdata(queue* p) {
assert(p);
assert(p->size > 0);
return p->tail->data;
}

int Queuesize(queue* p) {
assert(p);
return p->size;
}

bool QueueEmpty(queue* p) {
assert(p);
return p->size == 0;
}

//以上是引用的队列的创建

typedef struct {
queue p1;
queue p2;

} MyStack;//这里定义了一个结构体类型：我的栈：里面放了两个队列结构体类型的变量

MyStack myStackCreate() {
MyStackpst=(MyStack*)malloc(sizeof(MyStack));
Queueinit(&(pst->p1));
Queueinit(&(pst->p2));
return pst;

}//在这里将MyStack结构体里面的两个队列初始化，并得到MyStack类型的指针

void myStackPush(MyStack* obj, int x) {
if( !QueueEmpty(&(obj->p1))){
Queuebackpush(&(obj->p1),x);
}
else{
Queuebackpush(&(obj->p2),x);

}

//这里我们在两个队列里面插入数据，故由于让看起来像栈的形式，我们就找有数据的队列插入新的数据即
//找不为空的队列插入

}

int myStackPop(MyStack obj) {
//这里我们用假设法来得到空与非空队列
queueempty=&(obj->p1);
queue*noempty=&(obj->p2);
if(!QueueEmpty(&(obj->p1))){
//如果假设不成立执行下面
noempty=&(obj->p1);
empty=&(obj->p2);
}
//以上操作我们就可以得到noempty empty 分别为空与非空的队列
while( Queuesize(noempty)>1){
Queuebackpush(empty,Queuefrontdata(noempty));
Queuefrontpop(noempty);
}
//下面防止找不到要得到的栈顶元素，我们在pop之前要先保存一下
int data=Queuefrontdata(noempty);
Queuefrontpop(noempty);
return data;

}//首先我们要找到空的队列，然后把非空队列获得头部元素进行插到原来空的队列里，插入n-1个

int myStackTop(MyStack* obj) {
if( !QueueEmpty(&(obj->p1))){
return Queuebackdata(&(obj->p1));

}
else{
return Queuebackdata(&(obj->p2));

}
//这里返回栈顶元素即就是我们不为空的队列的队尾元素

}

bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&(obj->p1))&&QueueEmpty(&(obj->p2));
}

void myStackFree(MyStack* obj) {
Queuedestroy(&(obj->p1));
Queuedestroy(&(obj->p2));
free(obj);
obj=NULL;
//这里由于我们在 MyStack里开辟了两个队列的链表类型空间故需要先释放掉，
//再释放obj

}

测试：

​
int main()
{
MyStack* st = myStackCreate();
myStackPush(st, 1);
myStackPush(st, 2);

int ret = myStackTop(st);

printf("%d",ret);
mystackFree(st);
return 0;

}

​
二·用两个栈实现队列：
源：oj链接：. - 力扣（LeetCode）​​​​​​

1·思路：
这里首先建立两个栈作为MyQueue，大致思路和两个队列实现栈相差不大，这里只不过是调用的事先创建的队列改成栈了，此外再删去元素的时候会多排序一次。

①push：还是找空的栈然后，依次入栈

②pop：类似于上面的实现，但是当我们把n-1个元素放到另一个空栈里面顺序与原来是相反的故需要颠倒一下，此时就要再入一次栈入到原栈里，（先保存再返回，再删除）。

③peek：由于我每次使用函数的时候，这两个栈必然有一个空有一个非空，只需要返回非空栈的下标为0的元素即可。

④empty：这里判空也是两个均为空。

2·画图理解：

3·代码解答：
typedef int typedata;
typedef struct stack {
typedata* a;
int top;
int capacity;
} ST;

void STinit(ST p) {
assert(p);
p->a = NULL;
p->capacity = p->top = 0;
}
void STpush(ST p,typedata x) {
assert(p);
//扩容
if (p->top == p->capacity) {
int newcapacity = p->capacity == 0 ? 4 : (p->capacity) 2;
typedata tmp = (typedata)realloc(p->a, sizeof(typedata)newcapacity);
if (tmp == NULL) {
perror("realloc");
return;
}
p->a = tmp;
p->capacity = newcapacity;

}
p->a[p->top] = x;
p->top++;

}
void STpop(ST* p) {
assert(p);
assert(p->top);
p->top--;

}

typedata STTop(ST* p) {
assert(p);
assert(p->top);
return p->a[p->top - 1];

}
bool STempty(ST p) {
assert(p);
return p->top == 0;
}
int STsize(ST p) {
assert(p);
return p->top;
}
void STdestroy(ST* p) {
assert(p);
free(p->a);
p->a = NULL;
p->capacity = p->top = 0;
}

//以上是对栈的实现

typedef struct {
ST s1;
ST s2;
} MyQueue;

MyQueue myQueueCreate() {
MyQueue q=(MyQueue* )malloc(sizeof(MyQueue));
STinit(&(q->s1));
STinit(&(q->s2));
return q;
//在MyQueue内开辟两个栈的空间

}

void myQueuePush(MyQueue* obj, int x) {
if(!STempty(&(obj->s1))){
STpush(&(obj->s1),x);
}
else{
STpush(&(obj->s2),x);

}//这里也是找到非空栈进行插入数据

}

int myQueuePop(MyQueue obj) {
STempty=&(obj->s1);
ST*noempty=&(obj->s2);
if(!STempty(&(obj->s1))){
noempty=&(obj->s1);
empty=&(obj->s2);
}
//通过假设法得到真实的非空与空的栈
while(STsize(noempty)>1){
STpush(empty,STTop(noempty));
STpop(noempty);

}
//首先第一个循环是得到n-1个数据到原来空的栈里面，但是顺序是反的

int data=STTop(noempty);
STpop(noempty);
//在这里保存队列即栈的第一个元素，并把它pop
while(STsize(empty)>0){
     STpush(noempty,STTop(empty));
     STpop(empty);

}
//通过再一个循环把它重新插入到原来的栈里，顺序恢复

return data;

}

int myQueuePeek(MyQueue obj) {
if(!STempty(&(obj->s1))){
return obj->s1.a[0];
}
else{
return obj->s2.a[0];
}
}
//直接返回栈的首元素即队首元素
bool myQueueEmpty(MyQueue obj) {
return STempty(&(obj->s1))&&STempty(&(obj->s2));
}

void myQueueFree(MyQueue* obj) {
STdestroy(&(obj->s1));
STdestroy(&(obj->s2));
free(obj);
obj=NULL;

}

/**

  • Your MyQueue struct will be instantiated and called as such:
  • MyQueue* obj = myQueueCreate();

  • myQueuePush(obj, x);

  • int param_2 = myQueuePop(obj);

  • int param_3 = myQueuePeek(obj);

  • bool param_4 = myQueueEmpty(obj);

  • myQueueFree(obj);
    */

    测试：

int main() {
MyQueue* m = myQueueCreate();
myQueuePush(m, 1);
myQueuePush(m, 2);
myQueuePush(m, 3);
int ret = myQueuePop(m);
printf("%d ", ret);
int n=myQueuePeek(m);
printf("%d ", n);

return 0;

}
三·设计循环队列：

源：oj链接：. - 力扣（LeetCode）​​​​​​

1·思路：
设计循环队列，首先把它设计成一个数组的形式来循环利用，这里会涉及到判空与判满如何进行，

那么我们有两种方法解决，一个是进出队列用size记录，一个是额外多开辟一个空间，，我们选择用后者。比如设置长度为k，那么就要开辟k+1个空间。而多出来的空间我们不放数据用tail指向这个空的空间。（下面的head与tail实则是下标，把它假想为指针）

①MyCircularQueue：创建一个结构体存放队列要开辟的长度k，头尾指针以及int类型的指针a。

②myCircularQueueFront：找头，可以直接对a[head]去访问。

③myCircularQueueRear：访问尾指针前一个数据的话由于可能会存在tail为0，那么上一个就是-1，明显是不可能的，故需要转化，可以把它tail-1直接变成k，也可以tail-1后＋（k+1）%(k+1).

④myCircularQueueEnQueue:插入数据先判是否full，没有的话，就放入tail++，而可能存在为k+1.那么就把它变为0，或者直接（++tail）%（k+1）。

⑤ myCircularQueueDeQueue：这里我们画图可以发现删除数据只需要head++，而tail不用变化，但是head++，当过界时候把它变为0。

⑥myCircularQueueIsEmpty：头尾指针指向同一个处，即head==tail。

⑦myCircularQueueIsFull：画图可以知道每每当填满数据的时候tail+1==head（不包括越界改变的情况），故我们还是可以在tail到k+1，把它变为0，看是否与head相同，也可以（tail+1）%（k+1）看是否==head。

2·画图理解：

3·代码解答：

typedef struct {
int head;
int tail;
int k;//要开辟的队列长度
int *a;

} MyCircularQueue;

MyCircularQueue myCircularQueueCreate(int k) {
if(k<0){
return NULL;
}
MyCircularQueueq=(MyCircularQueue)malloc(sizeof(MyCircularQueue));
int m=(int)malloc(sizeof(int)(k+1));
q->head=q->tail=0;
q->a=m;
q->k = k;//将结构体里的k初始化为队列长度k
return q;

}
bool myCircularQueueIsEmpty(MyCircularQueue obj);
bool myCircularQueueIsFull(MyCircularQueue obj);//这里由于提前调用未定义的函数故需要在前面声明

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj)){
return false;
}
else{
// obj->a[obj->tail]=value;
// obj->tail++;
// if(obj->tail==obj->k+1){
// obj->tail=0;//这里有一个情况当tail+1到达数组超过数组最大额度就变为0
obj->a[obj->tail]=value;
obj->tail++;
obj->tail%=obj->k+1;//这里取模可以简化上面的判断

}
return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return false;
}
obj->head++;
// obj->a[obj->tail++];
// if(obj->tail==obj->k+1){
// obj->tail=0;
// }
if(obj->head==obj->k+1){
obj->head=0;
}
return true;
//这里我们要删出队列的第一个元素，那么只需要head++（这里也要考虑越界变0），然后tail不变即可

}

int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return -1;
}
return obj->a[obj->head];

}

int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return -1;
}
// if(obj->tail==0){
// return obj->a[obj->k];
// }
// else{
// return obj->a[obj->tail-1];
// }
//这里是返回tail的上一个数据，故可能会出现tail为零那么tail-1=-1；实际为k
//简化：

return obj->a[(obj->tail-1+(obj->k+1))%(obj->k+1)];

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->head==obj->tail){
return true;
}
else{
return false;
}
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
// if(obj->tail==obj->k&&obj->head==0){
// return true;
// }
// if(obj->tail+1==obj->head){
// return true;
// }

//     return false;
/*这里判断是否满，我们画图可以得到在多开辟一个空间的时候，每当tail+1=head就满了，考虑到可能tail
+1为-1，故进行了讨论判断*/

//简化：
return (obj->tail+1)%(obj->k+1)==obj->head;
//%(k+1)可以将越界的下标变成-1

}

void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a=NULL;
free(obj);
obj=NULL;//先释放掉开辟的数组空间内存，再把结构体的空间释放，指针置空
}

/**

  • Your MyCircularQueue struct will be instantiated and called as such:
  • MyCircularQueue* obj = myCircularQueueCreate(k);

  • bool param_1 = myCircularQueueEnQueue(obj, value);

  • bool param_2 = myCircularQueueDeQueue(obj);

  • int param_3 = myCircularQueueFront(obj);

  • int param_4 = myCircularQueueRear(obj);

  • bool param_5 = myCircularQueueIsEmpty(obj);

  • bool param_6 = myCircularQueueIsFull(obj);

  • myCircularQueueFree(obj);
    */

测试：

int main() {
MyCircularQueue* m = myCircularQueueCreate(3);
myCircularQueueEnQueue(m, 1);
myCircularQueueEnQueue(m, 2);
myCircularQueueEnQueue(m, 3);
myCircularQueueEnQueue(m, 4);
printf("%d ", myCircularQueueRear(m));
myCircularQueueIsFull(m);
myCircularQueueDeQueue(m);
myCircularQueueEnQueue(m, 4);
printf("%d ", myCircularQueueRear(m));
myCircularQueueFree(m);

return 0;

}

文章标签：
DataX
关键词：
栈数据结构
队列数据结构
栈队列数据结构
oj数据结构
栈队列oj数据结构
羑悻的小杀马特
目录
相关文章
RossyYan
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
165 77
蓝易云
|
16天前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
26 11
ephemerals__
|
4月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
405 9
那年春天
|
4月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
66 1
RossyYan
|
2月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
63 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
54 9
RossyYan
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
50 7
德国都芳最好
|
4月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
141 21
龙大吉
|
4月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
111 5
dufadayang
|
4月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
81 4

计算巢

热门文章

最新文章

  • 1
    轻松集成私有化部署Dify文本生成型应用
  • 2
    AppFlow：无代码部署Dify并集成到企业微信
  • 3
    快速部署 RAGFlow 社区版
  • 4
    AppFlow：无代码部署Dify作为钉钉智能机器人
  • 5
    幻兽帕鲁服务器存档拷贝教程
  • 6
    Java“Could Not Create Java Virtual Machine”解决
  • 7
    一键部署开源DeepSeek并集成到企业微信
  • 8
    快速部署 Dify 社区版
  • 9
    AppFlow：无代码部署Dify成为公众号客服
  • 10
    🚀 阿里云计算巢一键部署 OpenManus 社区版：释放 AI 生产力的终极解决方案
  • 1
    Termux安卓终端美化与开发实战：从下载到插件优化，小白也能玩转Linux
    41
  • 2
    虚拟化数据恢复—VMware虚拟化环境下重装系统导致服务器崩溃的数据恢复
    29
  • 3
    🚀 阿里云计算巢一键部署 OpenManus 社区版：释放 AI 生产力的终极解决方案
    79
  • 4
    服务器数据恢复—如何预防服务器故障？服务器发生故障如何恢复数据？
    31
  • 5
    系统崩溃不用慌！VMware这个逆天功能竟能让CentOS一键回档？后悔药真实存在！
    42
  • 6
    Windows平台GIMP 2.10下载教程：零基础入门高级图像编辑
    41
  • 7
    服务器数据恢复—服务器raid5阵列中2块硬盘掉线的数据恢复案例
    23
  • 8
    30分钟拉起Ray集群并部署Stable Diffusion模型服务
    75
  • 9
    反向海淘南美市场：Cssbuy 淘宝代购集运系统搭建攻略
    24
  • 10
    服务器数据恢复—服务器raid5阵列硬盘出现坏道掉线的数据恢复案例
    18

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    获取百炼API-KEY