算法---栈和队列

栈和队列

  • 1 栈
    • 栈的顺序存储
    • 栈的链式存储
  • 2 队列
    • 队列的顺序存储
    • 队列的链式存储
  • 3 栈和队列的应用
    • 用栈实现队列
    • 用队列实现栈
    • 最小栈

1 栈

参考文章：
https://zhuanlan.zhihu.com/p/346164833
https://zhuanlan.zhihu.com/p/120965372#:~:text=%E6%A0%88%E6%98%AF%E4%B8%80%E7%A7%8D%20%E5%90%8E%E8%BF%9B%E5%85%88%E5%87%BA%EF%BC%88LIFO%EF%BC%89,%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E8%BF%9B%E6%A0%88%E7%9A%84%E9%A1%BA%E5%BA%8F%E4%B8%BAa1%2Ca2%2Ca3%2Ca4%2Ca5%EF%BC%8C%E5%87%BA%E6%A0%88%E7%9A%84%E9%A1%BA%E5%BA%8F%E4%B8%BAa5%2Ca4%2Ca3%2Ca2%2Ca1

栈是一种特殊的线性表，仅允许在一端进行插入和删除。被允许插入和删除的一端为栈顶（top），另一端称为栈底（bottom），栈底是固定的，不允许进行插入和删除
在这里插入图片描述
栈的主要基本操作有：

  1. InitStack(&S)：初始化栈
  2. StackEmpty(S)：判断一个栈是否为空
  3. Push(&S,x)：进栈，若栈未满，则将x加入到栈顶
  4. pop(&S,&x)：出栈，若栈非空，则将栈顶元素出栈，并用x返回

栈的顺序存储

采用顺序存储的栈称为顺序栈，用数组实现。
栈的定义为：

#define STACK_SIZE 100typedef int ElmType;typedef struct{int top;    /* 栈顶指针 */ElmType data[STACK_SIZE];   /* 顺序栈 */
}SqStack;
  • 栈顶指针：S.top，初始时设置S.top = -1；栈顶元素：S.data[top]；
  • 进栈操作：先判断S.top==STACK_SIZE-1，若栈不满，S.top加1，然后将值送到栈顶。
  • 出栈操作：栈非空时，先去栈顶元素值，然后再将栈顶指针减1
  • 栈空条件：S.top==-1
  • 栈满条件：S.top==STACK_SIZE-1
  • 栈长：S.top+1

栈的链式存储

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，top指向栈顶元素，
请添加图片描述
链栈的存储可定义为：

typedef int ElemType;
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkStack;

2 队列

队列是只允许在一端进程插入操作，在另一端进行删除操作的线性表。被允许插入的一端叫队尾（rear），被允许删除的一端叫队头（front）。

请添加图片描述
队列的主要基本操作有：

  1. InitQueue(&Q)：初始化队列
  2. QueueEmpty(Q)：判断队列是否为空
  3. QueueLenght(Q)：判断队列中元素的个数
  4. push(&Q,x)：入队，如果队列没有满，就在队尾插入x
  5. pop(&Q,&x)：出队，如果队列非空，就在队首删除一个元素，并用x返回

队列的顺序存储

类型定义为：

#define QUEUE_SIZE 100
typedef int ElemType;
typedef struct 
{ElemType data[QUEUE_SIZE];  /* 队列 */int front;  /* 队首 */int rear;   /* 队尾 */
}SqQueue;

由于普通队列存在溢出问题，所以我们用循环队列，循环队列的定义和普通队列定义一样。
请添加图片描述

说明：这里浪费一个存储空间

  • 初始化：rear=front=0
  • 添加一个元素：如果队列没有满，则插入，即Q[rear] = x,rear= （rear+1）%QUEUE_SIZE
  • 删除一个元素：如果队列非空，则删除，即*x=Q[front]，front = （front+1）% QUEUE_SIZE
  • 判断队列是否为空：rear==front
  • 判断队列是否满：(rear+1)%QUEUE_SIZE==front
  • 队列元素个数：(rear-front+QUEUE_SIZE)%QUEUE_SIZE

队列的链式存储

队列的数组实现比较麻烦，需要考虑各种边界情况，所以通常使用链表形式来实现队列。

使用单向链表来实现链式队列，链式队列中存储front和rear即可。

typedef int ElemType;
typedef struct node
{int date;struct node *next;
}LinkNode;
typedef struct queue{LinkNode *front;LinkNode *rear;
}LinkQueue;

3 栈和队列的应用

用栈实现队列

参考文章：https://cloud.tencent.com/developer/article/1643318

LeedCode题目位置：232. 用栈实现队列

队列的特性是新加入的元素在队尾，最先入队的元素排在队首，按队首到队尾的顺序依次出栈。用栈实现队列，需要把新加入的元素保留在栈底，保证栈顶是队列最先加入的元素。

所以我们用两个栈A、B来实现，每次入队时，先把存放数据的栈A弹出到另一个栈B，然后把数据存到A，最后把B中的元素依次弹出压入A栈中，这样保证了新加入的元素在栈底。
请添加图片描述
队列出队是把队列队首的删除，对应栈是把栈A的栈顶元素删除。

实现代码如下：

#include <stdlib.h>typedef char bool;#define SIZE 100
#define false 0
#define true 1
/* 栈的定义 */
typedef struct{int length;int data[SIZE];
}Stack;/* 初始化栈 */
Stack *initStack()
{Stack * ret = malloc(sizeof(Stack));ret->length=-1;return ret;
}/* 判断栈是否为空 */
bool StackEmpty(Stack *s)
{return s->length==-1;
}/* 入栈操作 */
bool stackPush(Stack *s,int x)
{if(s->length==SIZE-1){return false;}s->length++;s->data[s->length]=x;return true;
}
/* 出栈操作 */
bool stackPop(Stack *s,int *x)
{if(s->length==-1){return false;}*x = s->data[s->length];s->length--;return true;
}/* 释放栈 */
void freeStack(Stack *s)
{free(s);
}typedef struct {Stack *inStack;Stack *outStack;
} MyQueue;/* 创造队列 */
MyQueue* myQueueCreate() {MyQueue *ret = (MyQueue *)malloc(sizeof(MyQueue));ret->inStack = initStack();ret->outStack = initStack();return ret;
}void myQueuePush(MyQueue* obj, int x) {int y;/* 先把栈A的元素依次弹出放到栈B */while(stackPop(obj->inStack,&y)){stackPush(obj->outStack,y);}/* 把入队的元素放到栈A的栈底 */stackPush(obj->inStack,x);/* 依次弹出栈B的元素放到栈A */while(stackPop(obj->outStack,&y)){stackPush(obj->inStack,y);}
}int myQueuePop(MyQueue* obj) {int x;/* 删除栈A的栈顶元素 */stackPop(obj->inStack,&x);return x;
}int myQueuePeek(MyQueue* obj) {return obj->inStack->data[obj->inStack->length];
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj->inStack);
}void myQueueFree(MyQueue* obj) {free(obj->inStack);free(obj->outStack);free(obj);
}/*** 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);
*/

在这里插入图片描述

用队列实现栈

参考文章：https://cloud.tencent.com/developer/article/1643318
LeedCode题目位置：225. 用队列实现栈
栈的特性是新加入的元素出现在栈顶，删除的元素也在栈顶，队列的特性是新加入的特性在队尾，删除的元素在队首。
我们可以让数据先入队列，然后把队列的以前的数据依次出队再入队，这样保证了新压入的数据在队首，对应栈的栈顶。
请添加图片描述
出栈的话，对应队列的操作就是把队首的元素删除即可。
实现代码如下：

#include <stdlib.h>#define false 0
#define true 1
#define SIZE 101typedef struct{int front;  // 队首int rear;   //队尾int data[SIZE];
}Queue;/* 初始化队列 */
Queue * initQueue()
{Queue * ret = (Queue *)malloc(sizeof(Queue));ret->front=0;ret->rear=0;return ret;
}
/* 判断队列是否为空 */
bool QueueEmpty(Queue *q)
{if(q->front==q->rear){return true;}elsereturn false;
}/* 入队 */
bool queuePush(Queue *q,int x)
{/* 队满 */if(q->front == (q->rear+1)%SIZE){return false;}q->data[q->rear]=x;q->rear =(q->rear+1)%SIZE;return true;
}
/* 出队 */
bool QueuePop(Queue *q,int *x)
{/* 队列是否为空 */if(q->front==q->rear)return false;*x = q->data[q->front];q->front = (q->front+1)%SIZE;return true;
}
/* 获取队首元素 */
int getQueueTop(Queue *q)
{return q->data[q->front];
}
typedef struct {Queue *q;
} MyStack;MyStack* myStackCreate() {MyStack *ret = (MyStack *)malloc(sizeof(MyStack));ret->q = initQueue();return ret;
}void myStackPush(MyStack* obj, int x) {int y;/* 计算现在有多少个元素 */int length = (obj->q->rear-obj->q->front+SIZE)%SIZE;/* x入队 */queuePush(obj->q,x);for(int i=0;i<length;i++){/* 出队 */QueuePop(obj->q,&y);/* 入队 */queuePush(obj->q,y);}
}
/* 只需将队首元素删除 */
int myStackPop(MyStack* obj) {int x;QueuePop(obj->q,&x);return x;
}int myStackTop(MyStack* obj) {return getQueueTop(obj->q);
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj->q);
}void myStackFree(MyStack* obj) {free(obj->q);free(obj);
}/*** 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);
*/

在这里插入图片描述

最小栈

LeedCode位置：155. 最小栈
题目要求在常数时间内检索到最小元素的栈，所以我们在栈里面设置一个变量min来记录最小元素的位置。

当插入元素，如果插入的元素比栈内的元素都要小，这个时候需要更新min；当删除元素时，如果此时最小的元素在栈顶，也需要更新min值。

代码实现如下：

#include <stdlib.h>#define SIZE 30000typedef struct {int length;    //记录元素个数,始终指向栈顶元素int min;    //记录最小元素的位置int data[SIZE];
} MinStack;int getStackMin(MinStack *s)
{int min =0;for(int i=1;i<=s->length;i++){if(s->data[min]>s->data[i]){min = i;}}return min;
}MinStack* minStackCreate() {MinStack *ret = (MinStack *)malloc(sizeof(MinStack));ret->length = -1;ret->min = 0;return ret;
}void minStackPush(MinStack* obj, int val) {obj->data[++obj->length]=val;/* 插入的元素比栈内的元素都要小，这个时候需要更新min */if(val<obj->data[obj->min])obj->min = obj->length;
}void minStackPop(MinStack* obj) {obj->length--;/* 删除元素时，如果此时最小的元素在栈顶，也需要更新min值 */if(obj->min==(obj->length+1)){obj->min = getStackMin(obj);}
}int minStackTop(MinStack* obj) {return obj->data[obj->length];
}int minStackGetMin(MinStack* obj) {return obj->data[obj->min];
}void minStackFree(MinStack* obj) {free(obj);
}/*** Your MinStack struct will be instantiated and called as such:* MinStack* obj = minStackCreate();* minStackPush(obj, val);* minStackPop(obj);* int param_3 = minStackTop(obj);* int param_4 = minStackGetMin(obj);* minStackFree(obj);
*/

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.pswp.cn/news/379587.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

学习网站LIST

学习网站LIST

面向对象的脚本语言Rubyhttp://rubycn.ce-lab.net/20020101.htmlRUBY文档中心http://www.moer.net/ruby/doc/TCL脚本http://www.tclchina.com/Python快速入门http://wiki.woodpecker.org.cn/moin/WeiZhong/2006-01-17Python 研究(Dive Into Python)http://www.woodpecker.org.c…
阅读更多...
再次参加（第七届）商学院徒步戈壁挑战赛，赋词几首

再次参加（第七届）商学院徒步戈壁挑战赛，赋词几首

2012年5月21-25日&#xff0c;再次踏上甘肃莫贺延碛戈壁&#xff0c;参加第七届商学院徒步戈壁挑战赛。时隔五年&#xff0c;时空转换。 少年游 ——戈壁缘 江南物华&#xff0c;远水碧山&#xff0c;灯火相掩映。暮宴朝欢&#xff0c;酒绿灯红&#xff0c;踯躅夜归人。 孤城落…
阅读更多...
Java StackTraceElement toString（）方法与示例

Java StackTraceElement toString（）方法与示例

StackTraceElement类的toString()方法 (StackTraceElement Class toString() method) toString() method is available in java.lang package. toString()方法在java.lang包中可用。 toString() method is used to represent stack trace element as a string or in other word…
阅读更多...
增删改查

增删改查

web层代码如下&#xff1a; package beyondwsq.web;import java.io.IOException; import java.sql.SQLException; import java.util.List;import javax.servlet.ServletException; import javax.servlet.http.HttpServlet; import javax.servlet.http.HttpServletRequest; imp…
阅读更多...
在WebBrowser中通过模拟键盘鼠标操控网页中的文件上传控件

在WebBrowser中通过模拟键盘鼠标操控网页中的文件上传控件

引言 这两天沉迷了Google SketchUp&#xff0c;刚刚玩够&#xff0c;一时兴起&#xff0c;研究了一下WebBrowser。 我在《WebBrowser控件使用技巧分享》一文中曾谈到过“我现在可以通过WebBrowser实现对各种Html元素的操控&#xff0c;唯独无法控制Html的上传控件”&#xff0c…
阅读更多...
编写最简单的字符设备驱动

编写最简单的字符设备驱动

编写最简单的字符设备驱动1 编写驱动代码2 编写makefile3 编译和加载驱动4 编写应用程序测试驱动参考文章&#xff1a; linux驱动开发第1讲&#xff1a;带你编写一个最简单的字符设备驱动 linux驱动开发第2讲&#xff1a;应用层的write如何调用到驱动中的write 1 编写驱动代码…
阅读更多...
Java ObjectStreamField toString（）方法与示例

Java ObjectStreamField toString（）方法与示例

ObjectStreamField类toString()方法 (ObjectStreamField Class toString() method) toString() method is available in java.io package. toString()方法在java.io包中可用。 toString() method is used to return a string that defines this field. toString()方法用于返回定…
阅读更多...
linux内核文件描述符fd、文件索引节点inode、文件对象file关系

linux内核文件描述符fd、文件索引节点inode、文件对象file关系

文件描述符fd、文件索引节点inode、文件对象file关系1 VFS对象1.1 超级块对象1.2 索引节点对象1.3 文件对象1.4 进程描述符1.5 files_struct2 如何根据文件描述符fd找到文件&#xff1f;1 VFS对象 在说fd、inode和file关系之前&#xff0c;我们先了解VFS的几个概念。分别是进程…
阅读更多...
sql2005 获取表字段信息和视图字段信息

sql2005 获取表字段信息和视图字段信息

获取表字段名,和字段说明SELECT[Table Name]OBJECT_NAME(c.object_id), [ColumnName]c.name, [Description]ex.value FROMsys.columns c LEFTOUTERJOINsys.exte…
阅读更多...
解析css之position

解析css之position

CSS的很多其他属性大多容易理解&#xff0c;比如字体&#xff0c;文本&#xff0c;背景等。有些CSS书籍也会对这些简单的属性进行大张旗鼓的介绍&#xff0c;而偏偏忽略了对一些难缠的属性讲解&#xff0c;有避重就轻的嫌疑。CSS中主要难以理解的属性包括盒型结构&#xff0c;以…
阅读更多...
Java ObjectInputStream readLong（）方法（带示例）

Java ObjectInputStream readLong（）方法（带示例）

ObjectInputStream类readLong()方法 (ObjectInputStream Class readLong() method) readLong() method is available in java.io package. readLong()方法在java.io包中可用。 readLong() method is used to read 8 bytes (i.e. 64 bit) of long value from this ObjectInputSt…
阅读更多...
交换瓶子（蓝桥杯）

交换瓶子（蓝桥杯）

有N个瓶子&#xff0c;编号 1 ~ N&#xff0c;放在架子上。 比如有5个瓶子&#xff1a; 2 1 3 5 4 要求每次拿起2个瓶子&#xff0c;交换它们的位置。 经过若干次后&#xff0c;使得瓶子的序号为&#xff1a; 1 2 3 4 5 对于这么简单的情况&#xff0c;显然&#xff0c;至少…
阅读更多...
Linux设备驱动开发---字符设备驱动程序

Linux设备驱动开发---字符设备驱动程序

字符设备驱动程序1 主设备和次设备的概念设备号的注册和释放静态方法动态方法区别2 设备文件操作struct file_operations与struct file、struct inode关系3 分配和注册字符设备class_createcdev_adddevice_create4 字符设备驱动程序字符设备通过字符&#xff08;一个接一个的字…
阅读更多...
Java LinkedHashMap getOrDefault（）方法与示例

Java LinkedHashMap getOrDefault（）方法与示例

LinkedHashMap类的getOrDefault()方法 (LinkedHashMap Class getOrDefault() method) getOrDefault() method is available in java.util package. getOrDefault()方法在java.util包中可用。 getOrDefault() method is used to get the value associated with the given key el…
阅读更多...
Java中的异常栈轨迹和异常链

Java中的异常栈轨迹和异常链

Java中允许对异常进行再次抛出&#xff0c;以提交给上一层进行处理&#xff0c;最为明显的例子为Java的常规异常。 常规异常&#xff1a;有Java所定义的异常&#xff0c;不需要异常声明&#xff0c;在未被try-catch的情况下&#xff0c;会被默认上报到main()方法。 Example: pu…
阅读更多...
贪心算法---背包问题（物品可以分割问题）

贪心算法---背包问题（物品可以分割问题）

问题背景&#xff1a; 有一天&#xff0c;阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时&#xff0c;远处突然出现一股烟尘&#xff0c;弥漫着直向上空飞扬&#xff0c;朝他这儿卷过来&#xff0c;而且越来越近。靠近以后&#xff0c;他才看清原来是一支马队&#xff0c;他…
阅读更多...
同步---信号量

同步---信号量

信号量1 信号量2 驱动程序和测试程序3 内核的具体实现总结1 信号量 Linux中的信号量是一种睡眠锁。如果有一个任务试图获得一个已经被占用的信号量时&#xff0c;信号量会将其放到一个等待队列&#xff0c;然后让其睡眠&#xff0c;这时处理器去执行其他代码。当持有信号量的进…
阅读更多...
Java Float类floatToIntBits（）方法与示例

Java Float类floatToIntBits（）方法与示例

Float类floatToIntBits()方法 (Float class floatToIntBits() method) floatToIntBits() method is available in java.lang package. floatToIntBits()方法在java.lang包中可用。 floatToIntBits() method follows IEEE 754 floating-point standards and according to standa…
阅读更多...
解释三度带和六度带的概念以及各坐标系如何定义

解释三度带和六度带的概念以及各坐标系如何定义

★ 地形图坐标系&#xff1a;我国的地形图采用高斯&#xff0d;克吕格平面直角坐标系。在该坐标系中&#xff0c;横轴&#xff1a;赤道&#xff0c;用&#xff39;表示&#xff1b;纵轴&#xff1a;中央经线&#xff0c;用&#xff38;表示&#xff1b;坐标原点&#xff1a;中央…
阅读更多...
0-1背包问题（物品不可分割）

0-1背包问题（物品不可分割）

问题背景&#xff1a; 所谓“钟点秘书”&#xff0c;是指年轻白领女性利用工余时间为客户提供秘书服务&#xff0c;并按钟点收取酬金。“钟点秘书”为客户提供有偿服务的方式一般是&#xff1a;采用电话、电传、上网等“遥控”式 服务&#xff0c;或亲自到客户公司处理部分业务…
阅读更多...
最新文章

Copyright @ 2022~2023