栈和队列

Suzhou
• 阅读 77
栈原理

栈(stack)又名堆栈,是一种只能在表尾进行插入和删除操作的线性表。能够进行操作的这一端被称为栈顶,相对地,把另一端称为栈底。 ::: warning 栈内元素操作时先进后出,类似于电梯上下成员,最后进去的人最先出来。 ::: 栈和队列 向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 栈和队列 如上图,top代表栈顶,栈S是一个结构体。S.top=-1时栈为空,当入栈第一个元素时,S.data[++S.top]=1,S.top前置++后数组下标变为0,依次向下可以入栈后面的元素。 栈和队列 上图中x表示要出栈的值(栈顶的那个值),S.data[S.top]=4,出栈后元素下标-1,变为S.top- -,下次要出栈的值变为3,即S.data[S.top- -]=3。 栈和队列 S.top是数组的下标,最大值为maxsize-1。


初始化栈及入栈出栈
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef int Elemtype;
typedef struct
{
    Elemtype data[MaxSize];
    int top;  //始终指向栈顶的变量
}SqStack;

//初始化栈
void InitStack(SqStack& S)
{
    S.top = -1;  //使得栈为空即为初始化栈,栈空即为S.top = -1
}

//判断栈是否为空
bool StackEmpty(SqStack S)
{
    if (-1 == S.top)  //定义指针时候才可以使用->
    {
        return true;
    }
    else
    {
        return false;
    }
}

//入栈
bool Push(SqStack& S, Elemtype x)  
{
    if (S.top == MaxSize - 1)  //栈满
    {
        return false;
    }
    S.data[++S.top] = x;
    return true;
}

//获取栈顶元素
bool GetTop(SqStack S, Elemtype &x)  //x需要引用&,原因是要对x赋值传递出去
{
    if (-1 == S.top)  //栈不能为空
    {
        return false;
    }
    /*或者使用嵌套调用如下:
    if (StackEmpty(S))
    {
        return false;
    }*/
    x = S.data[S.top];  //拿到栈顶元素
    return true;
}

//弹栈(即出栈)
bool Pop(SqStack &S, Elemtype &x)
{
    if (StackEmpty(S))  //栈不能为空
    {
        return false;
    }
    x = S.data[S.top];  //拿到栈顶元素
    x = S.data[S.top--];  //元素出栈
    return true;
}

int main()
{
    SqStack S;  //定义一个栈
    InitStack(S);
    bool flag;
    flag = StackEmpty(S);  //判断栈是否为空
    if (flag)
    {
        printf("stack is empty\n");
    }

    Push(S, 3);  //入栈元素3
    Push(S, 4);  //入栈元素4
    Push(S, 5);  //入栈元素5
    Elemtype m;
    flag = GetTop(S, m);  //获取栈顶元素
    if (flag)
    {
        printf("get top element %d\n", m);  //打印栈顶元素
    }
    flag = Pop(S, m);  //弹出栈顶元素
    if (flag)
    {
        printf("pop element %d\n", m);  //打印弹出元素
    }
    return 0;
}
stack is empty
get top element 5
pop element 5

栈和队列 弹栈的作用是将S.top- -,上述代码中S.top指向4,即数组下标为1的位置,下次再有入栈的元素会覆盖掉数组下标为2的元素5。 栈和队列 ::: warning 弹栈不改变栈元素,只是改变了栈顶指针S.top指向的位置。 :::


队列原理

FIFO:全称First in, First out,先进先出。 队列简称队,只允许在表的一端进行插入,另一端进行删除。队列中插入元素称为入队(进队),删除元素称为出队(离队)。 栈和队列

数组实现循环队列

栈和队列 循环队列可以使用数组或链表实现,这里使用数组。 栈和队列 如上图,Q.front=Q.rear时,队列为空。每次入队一个元素,rear+1;每次出队一个元素,front+1。 当放到元素f时,需要模上数组长度((Q.rear)%MaxSize=Q.front),然后把数组下标Q.rear置为0。 如果f后继续放g,此时队列头Q.front和队列尾Q.rear相等,都指向下标为1的位置,相等会认为是循环队列为空,所以不能放入g。 循环每次空出一个位置,如果rear+1=front,表示rear追上front,判断循环队列已经放满。 栈和队列 栈和队列 ::: warning 循环队列为空时不一定下标为0,只要Q.front=Q.rear队列就为空。 ::: Q.front指向的元素就是要出队的元素。 上图中如果Q.front指向数组下标5的元素,Q.front+1变为6,Q.front%MaxSize变为0,即Q.front又从0开始向后循环。

队列链式存储 栈和队列 队列尾部插入,头部删除。 栈和队列 front指向链表头第一个元素的位置,rear指向链表尾最后一个元素后面一个可以存放元素的位置。 有元素入队后rear向后+1,需要判断是否超出MaxSize,如果超过MaxSize,需要回到开头(位置0)。代码是:Q.rear = (Q.rear + 1) % MaxSize。

循环队列代码:

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 5

typedef int Elemtype;
typedef struct
{
    Elemtype data[MaxSize];
    Elemtype front, rear;
}SqQueue;

//初始化循环队列
void InitQueue(SqQueue &Q)
{
    Q.front = Q.rear = 0;  //循环队列初始化是将队列头尾都指向0号元素
}

//判断是否为空队列
bool IsEmpty(SqQueue Q)
{
    return Q.front = Q.rear;
}

//入队
bool EnQueue(SqQueue& Q, Elemtype x)
{
    if ((Q.rear + 1) % MaxSize == Q.front)  //判断队列是否已满,已满不能入队
    {
        return false;
    }
    Q.data[Q.rear] = x;  //入队。rear始终指向队尾可以存放元素的位置
    Q.rear = (Q.rear + 1) % MaxSize;  //判断rear+1后是否超出MaxSize,如果超出rear要回到起始位置0
    return true;
}

//出队
bool DeQueue(SqQueue& Q, Elemtype& x)
{
    if (Q.rear == Q.front)  //判断队列是否为空
    {
        return false;  //队列为空时无法出队
    }
    x = Q.data[Q.front];  //队列从头部出队,尾部入队
    Q.front = (Q.front + 1) % MaxSize;  //判断front+1后是否超出MaxSize,如果超出front要回到起始位置0
}
int main()
{
    SqQueue Q;
    InitQueue(Q);  //初始化循环队列
    bool ret;
    ret = IsEmpty(Q);
    if (ret)
    {
        printf("SqQueue is Empty\n");
    }
    else
    {
        printf("SqQuene is not Empty\n");
    }
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    ret = EnQueue(Q, 6);
    ret = EnQueue(Q, 7);
    if (ret)
    {
        printf("EnQueue success\n");
    }
    else
    {
        printf("EnQueue failed\n");
    }
    Elemtype element;  //存储出队元素
    ret = DeQueue(Q, element);
    if (ret)
    {
        printf("DeQueue success\n");
    }
    else
    {
        printf("DeQueue failed\n");
    }
    ret = EnQueue(Q, 7);
    if (ret)
    {
        printf("EnQueue success\n");
    }
    else
    {
        printf("EnQueue failed\n");
    }
    return 0;

执行结果如下: 栈和队列 上述代码第一次末尾入队元素7时,超出MaxSize值,无法入队,在出队队首的一个元素后,元素7入队成功,在主函数结束时打断点查看调试信息,可以看到元素7成功入队,front+1指向队列下标1处,rear模MaxSize后指向下标0处。此时(rear+1)%MaxSize=front,循环列表放满。


链表实现普通队列: 链表实现的普通队列可以有很长,不考虑链表填满的问题。 ::: tip 出队过程中,front从指向头节点开始,每次出队节点都是Q.front->next,即front指向出队节点的前一个,rear指向出队节点的后一个。 :::

::: warning front始终指向头节点,data域不放数据。rear始终指向链表尾,next域置为NULL。 ::: 链表实现的普通队列代码:

#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LinkNode
{
    Elemtype data;
    struct LinkNode* next;
}LinkNode;

typedef struct
{
    LinkNode* front, * rear;  //链表头、链表尾(队头、队尾)
}LinkQueue;  //队列先进先出(队头出队尾进)

//队列初始化,使用带头节点的链表实现
void InitQueue(LinkQueue& Q)
{
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));  //开辟空间是头节点
    Q.front->next = NULL;
}

//入队
void EnQueue(LinkQueue& Q, Elemtype x)  //入队时从队列尾部入队,Q会改变
{
    LinkNode* pnew = (LinkNode*)malloc(sizeof(LinkNode));
    pnew->data = x;
    pnew->next = NULL;  //入队的节点next置为NULL,否则需要遍历链表时无法找到链表结束位置
    Q.rear->next = pnew;  //队尾插入,原队列尾部节点的next指向新入队的节点
    Q.rear = pnew;  //rear指向新的队列尾部
}

//出队
bool DeQueue(LinkQueue& Q, Elemtype& x)  //元素出队时链表Q会改变,取出出队元素,x会改变,使用&
{
    if (Q.front == Q.rear)  //front和rear都指向头节点时队列为空
    {
        return false;
    }
    //Q.front->next = Q.front->next->next;
    //free(Q.front->next);
    //Q.front->next = NULL;
    x = Q.front->next->data;
    LinkNode* p = Q.front->next;
    Q.front = p->next;
    if (Q.rear == p)  //当链表中只剩下一个节点时,该节点被删除(出队)时要改变rear
    {
        Q.rear = Q.front;
    }
    free(p);
    p = NULL;
    return true;
}

int main()
{
    LinkQueue Q;
    InitQueue(Q);  //初始化队列
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 7);
    EnQueue(Q, 3);
    EnQueue(Q, 9);
    bool ret;
    Elemtype element;
    ret = DeQueue(Q, element);
    if (ret)
    {
        printf("DeQueue success element = %d\n", element);
    }
    else 
    {
        printf("DeQueue falied");
    }
    return 0;
}

题目解读

栈和队列 上图是一个空的循环队列,队列中的节点data域为空,next域指向自己,起始时front和rear都指向该空闲节点。(循环队列没有固定的头节点) 栈和队列 当入队一个新节点pnew时,front指向空闲节点不变,rear的next域由指向空闲节点变为指向新节点pnew:rear->next=pnew,rear指向新的队列尾部节点:rear=pnew或rear=rear->next,新节点的next域指向空闲节点:rear->next=front,此时循环队列是填满状态。 要求出队元素的空间可重复使用,即每次malloc开辟的空间在使用完毕后不会free,使用循环队列。 要求占用空间只增不减,即不能使用数组形式,定义数组时数组所占空间就已经确定了。 (链式存储结构使用链表,顺序存储结构使用数组。) 栈和队列 栈和队列 入队时,先判断队列是否已满,已满则在rear后开辟新节点,rear->next由front指向新节点,入队元素保存在rear指向节点的data域,rear=rear->next。未满则在新节点放在rear->next位置上,rear指向新节点,rear=rear->next。 出队时,先判断队列是否为空,不为空时front指向的节点出队,front=front->next。 代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LNode {
    Elemtype data;
    struct LNode* next;
}LNode, * LinkList;

//入队
void EnQueue(LinkList front, LinkList& rear, Elemtype value)
{
    LinkList pnew;
    if (rear->next == front)  //队列已满
    {
        pnew = (LinkList)malloc(sizeof(LNode));  //申请空间存放入队元素
        rear->data = value;  //根据题目要求将入队元素直接放在rear的data域中
        rear->next = pnew;  //做分隔
        //rear = rear->next;
        //rear->next = front;
        pnew->next = front;
        rear = pnew;
    }
    else
    {
        rear->data = value;
        rear = rear->next;
    }
}

//出队
void DeQueue(LinkList& front, LinkList rear)
{
    if (front == rear)
    {
        printf("队列为空\n");
    }
    else
    {
        //循环队列空间可以重复使用,出队时不会释放空间
        printf("出队的值为%d\n", front->data);
        front = front->next;
    } 
}

//循环队列操作的总流程
void CircleQueue(LinkList& front, LinkList& rear)
{
    //假设带头节点的链表
    front = (LinkList)malloc(sizeof(LNode));  //申请空间使rear和front都指向这个头节点
    rear = front;
    rear->next = front;  //构建循环队列
    //入队
    EnQueue(front, rear, 3);
    EnQueue(front, rear, 4);
    //出队
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
}

int main()
{
    LinkList front, rear;
    CircleQueue(front, rear);
    return 0;
}
出队的值为3
出队的值为4
队列为空
点赞
收藏
评论区
推荐文章
九路 九路
2年前
5 手写Java Stack 核心源码
Stack是Java中常用的数据结构之一,Stack具有"后进先出(LIFO)"的性质。只能在一端进行插入或者删除,即压栈与出栈栈的实现比较简单,性质也简单。可以用一个数组来实现栈结构。1.入栈的时候,只在数组尾部插入2.出栈的时候,只在数组尾部删除我们来看一下Stack的用法:如下publicstaticvoidmai
Stella981 Stella981
1年前
Goroutine(协程)为何能处理大并发?
简单来说:协程十分轻量,可以在一个进程中执行有数以十万计的协程,依旧保持高性能。进程、线程、协程的关系和区别:进程拥有自己独立的堆和栈,既不共享堆,亦不共享栈,进程由操作系统调度。线程拥有自己独立的栈和共享的堆,共享堆,不共享栈,线程亦由操作系统调度(标准线程是的)。协程和线程一样共享堆
Wesley13 Wesley13
1年前
C语言利用va_list、va_start、va_end、va_arg宏定义可变参数的函数
在定义可变参数的函数之前,先来理解一下函数参数的传递原理:1、函数参数是以栈这种数据结构来存取的,在函数参数列表中,从右至左依次入栈。2、参数的内存存放格式:参数的内存地址存放在内存的堆栈段中,在执行函数的时候,从最后一个(最右边)参数开始入栈。因此栈底高地址,栈顶低地址,举个例子说明一下:voidtest(inta,floatb,ch
Stella981 Stella981
1年前
JVM 字节码指令表
字节码助记符指令含义0x00nop什么都不做0x01aconst\_null将null推送至栈顶0x02iconst\_m1将int型1推送至栈顶0x03iconst\_0将int型0推送至栈顶0x04iconst\_1将int型1推送至栈顶0x05ic
Stella981 Stella981
1年前
JVM技术总结
1.程序计数器:记录正在执行的虚拟机的字节码的指令地址。2.java虚拟机栈:每个Java方法在执行的同时会创建一个栈帧用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程,就对应着一个栈帧在Java虚拟机栈中入栈和出栈的过程。该区域可能抛出以下异常:1.当线程请求的栈深度超过最大值,会抛出
Wesley13 Wesley13
1年前
java实现队列的详细代码
一、什么是队列结构一种线性结构,具有特殊的运算法则【只能在一端(队头)删除,在另一端(队尾)插入】。分类:1.顺序队列结构2.链式队列结构基本操作:1.入队列2.出队列  二:准备数据staticfinal intQUEUELEN15;classDATA{          String
Wesley13 Wesley13
1年前
C++栈和队列
使用标准库的栈和队列时,先包含相关的头文件include<stackinclude<queue定义栈如下:stack<intstk;定义队列如下:queue<intq;栈提供了如下的操作s.empty()如果栈为空返回true,否则返回fals
Stella981 Stella981
1年前
JVM总结3
    垃圾收集GarbageCollection通常被称为“GC”,它诞生于1960年MIT的Lisp语言,经过半个多世纪,目前已经十分成熟了。    jvm 中,程序计数器、虚拟机栈、本地方法栈都是随线程而生随线程而灭,栈帧随着方法的进入和退出做入栈和出栈操作,实现了自动的内存清理,因此,我们的内存垃圾回收主要集中于java堆和
Wesley13 Wesley13
1年前
20165322 第一周结队编程
结队编程四则运算阶段总结学习笔记中缀表达式转换为后缀表达式如果遇到数字,我们就直接将其输出。如果遇到非数字时,若栈为空或者该符号为左括号或者栈顶元素为括号,直接入栈。如果遇到一个右括号,持续出栈并输出符号
Wesley13 Wesley13
1年前
PHP优先级队列
优先级队列首先,我们要了解一下什么叫队列:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。从定义来看,队列是无法更改顺序的线性集合。线性集合一般有几种规则:先进先出(队
Suzhou
Suzhou
Lv1
这个网站设计堪称垃圾。CTRL+S过后的东西,重启电脑只能保存5行。多按几次CTRL+S还提示频繁保存不了。吐了。
17
文章
2
粉丝
3
获赞