精华内容
下载资源
问答
  • 文章来自解学武学习网站的免费章节 目录什么是栈进栈和出栈栈的应用什么是队列队列的出队和...,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。拿图 1 的栈来说,从图中数据的

    文章来自解学武学习网站的免费章节

    什么是栈

    同顺序表和链表一样,栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构,如图 1 所示。
    图一
    从图 1 我们看到,栈存储结构与之前所学的线性存储结构有所差异,这缘于栈对数据 “存” 和 “取” 的过程有特殊的要求:
    栈只能从表的一端存取数据,另一端是封闭的,如图 1 所示;
    在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。拿图 1 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。

    因此,我们可以给栈下一个定义,即栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。

    通常,栈的开口端被称为栈顶;相应地,封口端被称为栈底。因此,栈顶元素指的就是距离栈顶最近的元素,拿图 2 来说,栈顶元素为元素 4;同理,栈底元素指的是位于栈最底部的元素,图 2 中的栈底元素为元素 1。
    在这里插入图片描述

    进栈和出栈

    基于栈结构的特点,在实际应用中,通常只会对栈执行以下两种操作:
    向栈中添加元素,此过程被称为"进栈"(入栈或压栈);
    从栈中提取出指定元素,此过程被称为"出栈"(或弹栈);
    栈的具体实现
    栈是一种 “特殊” 的线性存储结构,因此栈的具体实现有以下两种方式:
    顺序栈:采用顺序存储结构可以模拟栈存储数据的特点,从而实现栈存储结构;
    链栈:采用链式存储结构实现栈结构;
    两种实现方式的区别,仅限于数据元素在实际物理空间上存放的相对位置,顺序栈底层采用的是数组,链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。

    栈的应用

    基于栈结构对数据存取采用 “先进后出” 原则的特点,它可以用于实现很多功能。

    例如,我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A,然后关闭了页面 A 跳转到页面 B,随后又关闭页面 B 跳转到了页面 C。而此时,我们如果想重新回到页面 A,有两个选择:
    重新搜索找到页面 A;
    使用浏览器的"回退"功能。浏览器会先回退到页面 B,而后再回退到页面 A。

    浏览器 “回退” 功能的实现,底层使用的就是栈存储结构。当你关闭页面 A 时,浏览器会将页面 A 入栈;同样,当你关闭页面 B 时,浏览器也会将 B入栈。因此,当你执行回退操作时,才会首先看到的是页面 B,然后是页面 A,这是栈中数据依次出栈的效果。

    不仅如此,栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号(小括号、中括号和大括号),括号的错误使用(通常是丢右括号)会导致程序编译错误,而很多开发工具中都有检测代码是否有编辑错误的功能,其中就包含检测代码中的括号匹配问题,此功能的底层实现使用的就是栈结构。

    同时,栈结构还可以实现数值的进制转换功能。例如,编写程序实现从十进制数自动转换成二进制数,就可以使用栈存储结构来实现。

    什么是队列

    队列,和栈一样,也是一种对数据的"存"和"取"有严格要求的线性存储结构。

    与栈结构不同的是,队列的两端都"开口",要求数据只能从一端进,从另一端出,如图 1 所示:
    在这里插入图片描述

    队列的出队和入队

    通常,称进数据的一端为 “队尾”,出数据的一端为 “队头”,数据元素进队列的过程称为 “入队”,出队列的过程称为 “出队”。

    不仅如此,队列中数据的进出要遵循 “先进先出” 的原则,即最先进队列的数据元素,同样要最先出队列。拿图 1 中的队列来说,从数据在队列中的存储状态可以分析出,元素 1 最先进队,其次是元素 2,最后是元素 3。此时如果将元素 3 出队,根据队列 “先进先出” 的特点,元素 1 要先出队列,元素 2 再出队列,最后才轮到元素 3 出队列。
    栈和队列不要混淆,栈结构是一端封口,特点是"先进后出";而队列的两端全是开口,特点是"先进先出"。

    因此,数据从表的一端进,从另一端出,且遵循 “先进先出” 原则的线性存储结构就是队列。

    队列的实现

    队列存储结构的实现有以下两种方式:
    顺序队列:在顺序表的基础上实现的队列结构;
    链队列:在链表的基础上实现的队列结构;

    两者的区别仅是顺序表和链表的区别,即在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。
    队列的实际应用
    实际生活中,队列的应用随处可见,比如排队买 XXX、医院的挂号系统等,采用的都是队列的结构。

    拿排队买票来说,所有的人排成一队,先到者排的就靠前,后到者只能从队尾排队等待,队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后,才轮到自己买票。这就不是典型的队列结构吗?

    展开全文
  • 数据结构之 栈和队列

    2020-05-27 13:20:37
    一、栈 ...2,,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。 栈的使用案例1: 浏览器 “回退” 功能的实现,底层使用的就是栈存储结构。 当你关闭页面 A

    一、栈

    1、描叙

    栈和队列是计算机中基本的两个数据结构,栈可以达到后进先出,队列可以先进先出。在实际应用上,我们可以使用栈进行逆序遍历链表,非递归中序遍历二叉树,括号匹配,函数调用等等;可以使用队列对二叉树进行层次遍历,打印机的打印服务,通信中的消息队列等等。

    栈的储存规则:
    1,栈只能从表的一端存取数据,另一端是封闭的
    2,在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。

    栈的使用案例1:
    浏览器 “回退” 功能的实现,底层使用的就是栈存储结构。
    当你关闭页面 A 时,浏览器会将页面 A 入栈;同样,当你关闭页面 B 时,浏览器也会将 B入栈。因此,当你执行回退操作时,才会首先看到的是页面 B,然后是页面 A,这是栈中数据依次出栈的效果。

    栈的使用案例2:
    栈存储结构还可以帮我们检测代码中的括号匹配问题。
    多数编程语言都会用到括号(小括号、中括号和大括号),括号的错误使用(通常是丢右括号)会导致程序编译错误,而很多开发工具中都有检测代码是否有编辑错误的功能,其中就包含检测代码中的括号匹配问题,此功能的底层实现使用的就是栈结构。

    2、图文示例

    先进后出
    在这里插入图片描述

    3、代码示例

    package stackAndQueue;
    
    /**
     * TODO 栈,先进后出
     */
    public class Stack {
    
        // 底层基于数组
        private int[] arr;
        // 数据长度, 最后一个数据的索引=数据长度-1
        private int size;
    
        // 容量设置
        public Stack() {
            arr = new int[16];
        }
    
        public Stack(int length) {
            arr = new int[length];
        }
    
        /**
         * 添加
         */
        public void plus(int val) {
            arr[size++] = val;
        }
    
        /**
         * 获取并弹出元素, 最后一个数据的索引=size-1
         */
        public int pop() {
            return arr[--size];
        }
    
    
        /**
         * 判断是否为空
         */
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * 容量是否满了,添加可先判断容量,进行扩容操作
         */
        public boolean isFull() {
            return size == arr.length;
        }
    }
    
    
    
    

    测试代码

    // 测试
    class Test {
        public static void main(String[] args) {
            Stack stack = new Stack(5);
            stack.plus(1);
            stack.plus(2);
            stack.plus(3);
            stack.plus(4);
            stack.plus(5);
            System.out.println("容量是否满了-->" + stack.isFull());
            while (!stack.isEmpty()) {
                System.out.println(stack.pop());
            }
        }
    }
    
    
    // 输出
    容量是否满了-->true
    5
    4
    3
    2
    1
    

    二、队列

    1、描叙

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
    队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。 [1]

    队列的实现
    队列存储结构的实现有以下两种方式:
    顺序队列:在顺序表的基础上实现的队列结构;
    链队列:在链表的基础上实现的队列结构;

    两者的区别仅是顺序表和链表的区别,即在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。

    队列的实际应用
    实际生活中,队列的应用随处可见,比如排队买 XXX、医院的挂号系统等,采用的都是队列的结构。

    拿排队买票来说,所有的人排成一队,先到者排的就靠前,后到者只能从队尾排队等待,队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后,才轮到自己买票。这就不是典型的队列结构吗?

    2、图文示例

    普通队列

    先进先出
    在这里插入图片描述
    循环队列

    先进先出
    在这里插入图片描述

    3、代码示例

    package stackAndQueue;
    
    
    /**
     * TODO 队列,先进先出
     */
    public class Queue {
    
        // 底层基于数组
        private int[] arr;
        // 数据长度
        private int size;
        // 开头元素索引 (每获取一次数据 front+1)
        private int front;
        // 结尾元素索引(每添加一次数据rear+1,每获取一次数据rear-1 )--> 数据长度=rear+1
        private int rear;
    
        // 容量设置
        public Queue() {
            arr = new int[16];
            front = -1;
            rear = -1;
        }
    
        public Queue(int length) {
            arr = new int[length];
            front = -1;
            rear = -1;
        }
    
        /**
         * 获取当前数据长度
         */
        public int size() {
            return this.size;
        }
    
        /**
         * 插入元素
         */
    
        public void plus(int val) {
            // 判断数组是否满了
            if (isFull()) {
                System.out.println("插入["+val+"]失败,数组容量已满");
            } else {
                // 循环插入,--元素尾添加
                if (rear == arr.length - 1) {
                    rear = -1;
                }
                size++;
                arr[++rear] = val;
            }
        }
    
    
        /**
         * 获取并弹出元素
         */
        public int pop() {
            // 循环读取--元素头开始读取
            if (front == arr.length - 1) {
                front = -1;
            }
            size--;
            return arr[++front];
        }
    
        /**
         * 判断元素是否为空
         */
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * 容量是否满了,添加可先判断容量,进行扩容操作
         */
        public boolean isFull() {
            return size == arr.length;
        }
    }
    
    

    测试代码

    // 测试
    class Test1 {
        public static void main(String[] args) {
            Queue queue = new Queue(5);
            queue.plus(1);
            queue.plus(2);
            queue.plus(3);
            queue.plus(4);
            queue.plus(5);
            System.out.println("容量是否满了-->" + queue.isFull() + "  当前数据长度:" + queue.size());
            //消费--> size=0
            while (!queue.isEmpty()) {
                System.out.println(queue.pop());
            }
            // 添加数据,size=0
            queue.plus(6);
            queue.plus(7);
            queue.plus(8);
            queue.plus(9);
            queue.plus(10);
            System.out.println("弹出--> " + queue.pop());
            queue.plus(11);
            //
            queue.plus(12);
            queue.plus(13);
            queue.plus(14);
            while (!queue.isEmpty()) {
                System.out.println(queue.pop());
            }
        }
    }
    
    // 打印
    容量是否满了-->true  当前数据长度:5
    1
    2
    3
    4
    5
    弹出--> 6
    插入[12]失败,数组容量已满
    插入[13]失败,数组容量已满
    插入[14]失败,数组容量已满
    7
    8
    9
    10
    11
    

    本文到此结束,如果觉得有用,劳烦各位点赞关注一下呗,将不定时持续更新更多的内容…,感谢大家的观看!

    展开全文
  • 栈(Stack)和队列(Queue) 栈和队列,也属于线性表,都用于存储...,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。从图可看出数据的存储状态,元素 1 是最先进的栈。因此,

    栈(Stack)和队列(Queue)

    栈和队列,也属于线性表,都用于存储逻辑关系为 “一对一” 的数据。
    栈也可分为顺序栈和链表,队列也分为顺序队列和链队列。

    栈(Stack)

    栈同顺序表和链表一样,栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构,且遵循"先进后出(FILO)"原则。

    栈的开口端被称为栈顶,封口端被称为栈底。栈顶元素指的就是距离栈顶最近的元素,栈底元素指的是位于栈最底部的元素。

    如下图所示:
    在这里插入图片描述

    1. 栈只能从表的一端存取数据,另一端是封闭的。
    2. 在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。从图中可看出数据的存储状态,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。

    进栈和出栈

    • 向栈中添加元素,此过程被称为"进栈"(入栈或压栈);
    • 从栈中提取出指定元素,此过程被称为"出栈"(或弹栈);

    栈的实现方式

    • 顺序栈:采用顺序存储结构可以模拟栈存储数据的特点,从而实现栈存储结构;
    • 链栈:采用链式存储结构实现栈结构;

    顺序栈

    顺序栈是利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的元素数据。分别使用top指针和base指针指向栈顶和栈底。

    初始化顺序栈
    1. 分配存储空间。
    2. 置栈为空栈,即栈顶指针和栈底指针都指向栈底。
    int InitStack(SqStack &S){
    	S.base=new int[MAX];
    	if(!S.base){
    		return 0;
    	}
    	S.top=S.base; 
    	S.stacksize=MAX;
    	return 1;
    }
    
    入栈
    1. 将入栈元素压入栈顶。
    2. 然后栈顶指针加1。
    int Push_S(SqStack &S,int e){
    	//将元素e入栈 
    	if(S.top-S.base==S.stacksize){//判断栈是否满 
    		return 0;
    	}
    	*S.top++=e;
    	return 1;
    }
    
    出栈
    1. 首先判断栈是否为空,若空返回ERROR,若不空,执行下一句。
    2. 栈顶指针减1,然后栈顶元素出栈。
    int Pop_S(SqStack &S,int &e){
    	//用e返回出栈的元素
    	if(S.top==S.base){//栈空 
    		return 0;
    	} 
    	e=*--S.top;
    	return 1;
    }
    

    链栈

    链栈的存储结构与单链表的存储结构相同。
    由于栈是在栈顶进行删除和添加元素的,因此,将链表头部作为栈顶的一端,可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。

    链表的头部作为栈顶,意味着:

    • 在实现数据"入栈"操作时,需要将数据从链表的头部插入;
    • 在实现数据"出栈"操作时,需要删除链表头部的首元节点;

    因此,链栈实际上就是一个只能采用头插法插入或删除数据的链表。

    初始化链栈
    typedef struct StackNode{
    	int data;
    	struct StackNode *next;
    }StackNode,*LinkStack;
     
    int InitStack(LinkStack &S){
    	S=NULL;//将栈顶指针置空
    	return 1; 
    }
    
    入栈
    int Push(LinkStack &S,int e){
    	//元素e入栈
        //链栈要注意指针的方向是从栈顶指向栈底的 
    	struct StackNode *p;
    	p=new StackNode;
    	p->data=e;
    	p->next=S;
    	S=p;	
    }
    
    出栈
    int Pop(LinkStack &S,int &e){
    	if(S==NULL){
    		return 0;
    	}
    	e=S->data;
    	struct StackNode *q;
    	q=new StackNode;
    	q=S;
    	S=S->next;
    	delete q;
    	return 1;
    }
    

    队列(Queue)

    队列,和栈一样,也是一种对数据的"存"和"取"有严格要求的线性存储结构。与栈结构不同的是,队列的两端都"开口",要求数据只能从一端进,从另一端出,遵循 "先进先出"(FIFO)的原则。

    通常,称进数据的一端为 “队尾(rear)”,出数据的一端为 “队头(front)”,数据元素进队列的过程称为 “入队”,出队列的过程称为 “出队”。

    在这里插入图片描述

    队列实现方式

    • 顺序队列:在顺序表的基础上实现的队列结构;
    • 链队列:在链表的基础上实现的队列结构;

    两者的区别仅是顺序表和链表的区别,即在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。

    顺序队列

    顺序队列,即采用顺序表模拟实现的队列结构,底层使用的是数组,因此需预先申请一块足够大的内存空间初始化顺序队列。

    顺序队列的实现
    #include <stdio.h>
    int enQueue(int *a,int rear,int data){
        a[rear]=data;
        rear++;
        return rear;
    }
    void deQueue(int *a,int front,int rear){
        //如果 front==rear,表示队列为空
        while (front!=rear) {
            printf("出队元素:%d\n",a[front]);
            front++;
        }
    }
    int main() {
        int a[100];
        int front,rear;
        //设置队头指针和队尾指针,当队列中没有元素时,队头和队尾指向同一块地址
        front=rear=0;
        //入队
        rear=enQueue(a, rear, 1);
        rear=enQueue(a, rear, 2);
        rear=enQueue(a, rear, 3);
        rear=enQueue(a, rear, 4);
        //出队
        deQueue(a, front, rear);
        return 0;
    }
    

    程序输出结果:

    出队元素:1
    出队元素:2
    出队元素:3
    出队元素:4
    

    此实现方式出现问题,随着入队出队的进行,会使整个队列整体向后移动,这样就出现了队尾指针已经移到了最后,再有元素入队就会出现溢出,而事实上此时队中并未真的“满员”,这种现象为“假溢出”,这是由于队尾入,队头出的受限操作,以及为避免数据元素移动,队头队尾不固定造成的。

    解决假溢出的方法有:

    • 固定队头,出队后,队列中的所有元素向前移动。

    • 固定队尾,入队时,队列中的所有元素向前移动。

    • 将队列的数据区看成头尾相接的循环结构,头尾指针的关系不变,将其称为“循环队列”

    循环队列的实现
    #include <stdio.h>
    #define max 5//表示顺序表申请的空间大小
    int enQueue(int *a,int front,int rear,int data){
        //添加判断语句,如果rear超过max,则直接将其从a[0]重新开始存储,如果rear+1和front重合,则表示数组已满
        if ((rear+1)%max==front) {
            printf("空间已满");
            return rear;
        }
        a[rear%max]=data;
        rear++;
        return rear;
    }
    int  deQueue(int *a,int front,int rear){
        //如果front==rear,表示队列为空
        if(front==rear%max) {
            printf("队列为空");
            return front;
        }
        printf("%d ",a[front]);
        //front不再直接 +1,而是+1后同max进行比较,如果=max,则直接跳转到 a[0]
        front=(front+1)%max;
        return front;
    }
    int main() {
        int a[max];
        int front,rear;
        //设置队头指针和队尾指针,当队列中没有元素时,队头和队尾指向同一块地址
        front=rear=0;
        //入队
        rear=enQueue(a,front,rear, 1);
        rear=enQueue(a,front,rear, 2);
        rear=enQueue(a,front,rear, 3);
        rear=enQueue(a,front,rear, 4);
        //出队
        front=deQueue(a, front, rear);
        //再入队
        rear=enQueue(a,front,rear, 5);
        //再出队
        front=deQueue(a, front, rear);
        //再入队
        rear=enQueue(a,front,rear, 6);
        //再出队
        front=deQueue(a, front, rear);
        front=deQueue(a, front, rear);
        front=deQueue(a, front, rear);
        front=deQueue(a, front, rear);
        return 0;
    }
    

    程序输出结果:

    1 2 3 4 5 6
    

    使用此方法需要注意的是,顺序队列在判断数组是否已满时,出现下面情况:

    • 当队列为空时,队列的头指针等于队列的尾指针;
    • 当数组满员时,队列的头指针等于队列的尾指针;

    链式队列

    链式队列,简称"链队列",即使用链表实现的队列存储结构。
    链式队列的实现思想同顺序队列类似,只需创建两个指针(命名为 front 和 rear)分别指向链表中队列的队头元素和队尾元素。

    链式队列的实现
    //链表中的节点结构
    typedef struct QNode{
        int data;
        struct QNode * next;
    }QNode;
    //创建链式队列的函数
    QNode * initQueue(){
        //创建一个头节点
        QNode * queue=(QNode*)malloc(sizeof(QNode));
        //对头节点进行初始化
        queue->next=NULL;
        return queue;
    }
    
    入队

    新的数据元素入队,只需进行以下 3 步操作:

    • 将该数据元素用节点包裹,例如新节点名称为 elem;
    • 与 rear 指针指向的节点建立逻辑关系,即执行 rear->next=elem;
    • 最后移动 rear 指针指向该新节点,即 rear=elem
    QNode* enQueue(QNode * rear,int data){
        //1、用节点包裹入队元素
        QNode * enElem=(QNode*)malloc(sizeof(QNode));
        enElem->data=data;
        enElem->next=NULL;
        //2、新节点与rear节点建立逻辑关系
        rear->next=enElem;
        //3、rear指向新节点
        rear=enElem;
        //返回新的rear,为后续新元素入队做准备
        return rear;
    }
    
    出队

    元素出队,需要做以下 3 步操作:

    • 通过 top 指针直接找到队头节点,创建一个新指针 p 指向此即将出队的节点;
    • 将 p 节点(即要出队的队头节点)从链表中摘除;
    • 释放节点 p,回收其所占的内存空间;
    void DeQueue(QNode * top,QNode * rear){
        if (top->next==NULL) {
            printf("队列为空");
            return ;
        }
        // 1、
        QNode * p=top->next;
        printf("%d",p->data);
        top->next=p->next;
        if (rear==p) {
            rear=top;
        }
        free(p);
    }
    

    本篇完!!!

    展开全文
  • ,无论是存数据还是取数据,都必须遵循先进后出的原则,即最先进栈的元素最后出栈。 简单来说:栈是一种只能从表的一端存取数据且遵循“先进后出”原则的线性存储结构 栈顶:栈的开口端 栈底:栈的封口端 ...

    栈和队列

    1)概述

    和顺序表和链表一样,栈也是用来存储逻辑关系为“一对一”数据的线性存储结构

    栈对数据存和去的过程有特殊的要求:

    1. 栈只能从表的一端存取数据,另一端是封闭的
    2. 在栈中,无论是存数据还是取数据,都必须遵循先进后出的原则,即最先进栈的元素最后出栈。

    简单来说:栈是一种只能从表的一端存取数据且遵循“先进后出”原则的线性存储结构

    栈顶:栈的开口端

    栈底:栈的封口端

    栈顶元素指的是距离栈顶最近的元素,而栈底元素指的是,位于栈最底部的元素

    进栈和出栈:

    基于栈结构的特点,在实际的应用中通常会对栈执行下面的两种操作:

    1. 向栈中添加元素,此过程被称为“进栈”(入栈或压栈)
    2. 从栈中提取出指定元素,此过程中被称为出栈(或弹栈)

    栈的具体实现:

    栈是一种特殊的线性存储结构,因此栈的具体实现有以下两种方式:

    1. 顺序栈:采用顺序存储结构,可以模拟栈存储数据的特点,从而实现栈存储结构
    2. 莲栈:采用链式存储结构实现栈

    2)顺序栈

    顺序栈,也就是用顺序表来实现栈存储结构(就是说用数组来实现)。

    如果仔细观察顺序表和栈结构就会发现,他们存储数据的方式高度相似,只不过栈对数据的存取过程有特殊的限制,而顺序表没有。

    在使用顺序表模拟栈存储结构常用的实现思路,就是在顺序表中设定一个实时指向栈顶元素的**变量(**top),top的初值为-1,表示栈中没有存储任何数据元素,也就是说栈是空栈,一旦数据元素进栈,top就 +1,如果元素出栈 top 就-1

    理解:

    top代表栈顶元素的索引值

    元素“入栈”

    最初的时候栈是空栈,即数组是空的,top的初始值为-1。

    向栈中添加元素1,则top = 0然后依次存储

    typedef struct SortStack{
        int* array;
        int top ;
    }*sortStack;
    
    
    
    int push(sortStack stack,int elem){
        stack->array[++(stack->top)]=elem;
        return stack->top;
    }
    

    分析:

    从代码中定义了一个SortStack的数据结构,这个数据结构中一个属性用于存储一个数组,另一个用于存储top指针。

    push方法用于向数组中添加一个数据。

    这样的行为称之为“入栈”

    元素“出栈”

    top变量其实对模拟数据入栈的操作没有什么实际的帮助,但是它是为了实现数据出栈而准备的。

    出栈时需要把数据一个个的扔出栈,直到取到对应位置的元素,而这里的对应的位置索引就是通过top来完成指向的。

    /**
     * 弹出栈的最后一个元素
     * @param array
     * @return
     */
    int pop(sortStack stack){
        if (stack->top == -1){
            INFO_LOG("This stack is a empty stack");
            return -1;
        }
        int tempData = stack->array[stack->top];
        printf("The last elem is : %d",tempData);
        stack->top--;
        return tempData;
    }
    

    分析:

    由于top总是指向栈顶元素,所以每次都会把栈定的元素弹出来。

    如果top的值为-1则说明这个栈是一个空栈

    3)链栈

    链栈就是用链表实现栈存储结构

    顺序栈是将顺序表的一端作为栈底,另一端作为栈顶,而链栈也是这样的,通常我们将链表的头部作为栈顶,尾部作为栈底。

    对于这个也很显而易见,对于栈来说,我们无法随机存取,这和链表的顺序存取结构也是十分契合的。

    这里以头为顶更便于栈的理解。

    元素“入栈”

    linkStackNode push(linkStackNode head,int element){
        linkStackNode newNode = (linkStackNode)malloc(sizeof (struct LinkStackNode));
        //让新结点的next指向head
        newNode->next = head;
        newNode->data = element;
        head = newNode;
        //把新结点作为head返回
        return head;
    }
    

    元素“出栈”

    linkStackNode pop(linkStackNode head){
        if (head){
            //保证栈内是有元素的
            linkStackNode temp = head;
            //然后把栈顶元素进行更新
            head = head->next;
            printf("出栈元素 :%d",temp->data);
            if (head){
                printf("新栈顶元素 %d\n",head->data);
            } else{
                printf("栈已空");
            }
            free(temp);
        } else{
            printf("栈内已无元素");
            return head;
        }
        return head;
    }
    

    出栈的思想也很简单,就是把栈顶元素弹出,然后更新栈顶元素即可。

    注意整个过程中避免栈内无数据还要做数据出栈的错误操作

    4)用栈结构求表达式的值

    如何用栈结构求一个表达式的值?

    所谓表达式,就是由变量、常量以及运算符组合而成的式子,常用的运算符有(!,^,+,-,*,/,())这几种

    用栈结构去求一个表达式的值,已经设计好了全新的表示表达式方法,称为后缀表达式或者逆波兰表达式。和普通表达式不同,后缀表达式习惯把运算符写在它的运算项之后,而且整个表达式的过程中不用() 表明运算的优先级关系

    比如说:表达式-> !3 + 4*2/(1-5)^2

    就可以转换为后缀表达式:

    3 !  4 2 * 1 5 - 2 ^ / +
    

    虽然后缀表达式相比于普通的表达式来说,能轻松的借助栈存储结构求得值,但是却完全舍弃了表达式该有的可读性。

    具体求值的过程:当用户给定一个后缀表达式时,按照从左到右的顺序依次扫描表达式中的各个运算项和运算符

    1. 遇到运算项时,直接入栈
    2. 遇到运算符时,将位于栈顶的运算项出栈,对于单目运算符去一个运算项,对于双目运算符去两个运算项,第一个取出来的运算向作为右运算项,另一个作为左运算项,求得表达式的值后将其入栈
    3. 直到栈中存在一个运算项为止,此运算项即为整个表达式的值

    5)队列

    队列和栈一样也是一种对数据的存取由严格要求的“线性存储结构”

    和栈结构不同的是,队列的两端都开口,,要求数据只能从一端进,从另一端出

    进数据的一端叫做队尾,出数据的一段叫做队头,数据元素进队列的过程叫做入队,出队列的过程叫做出队。

    队列中数据的进出要求遵循,先进先出的原则,最先进队列的数据元素最先出队列,最后进队列的元素,最后出队列

    区分:

    对于栈来说是先进后出,而对于队列来说是先进先出。栈是一端开口,队列是两端开口

    根据存储结构的实现可分为:

    1. 顺序队列:在顺序表的基础上实现的队列结构
    2. 链队列:在链表的基础上实现的队列结构

    两者的区别仅是顺序表和链表的去呗,即在实际的物理空间中,如果数据几种存储就是用的顺序队列,如果数据分散存储就是用的链队列。

    6)顺序队列

    顺序队列使用的是数组,因此需要提前申请一块足够大的内存空间初始化顺序队列,初次之外,满足顺序队列中数据从队尾进,队头出且先进先出的要求,需要定义两个指针(top 和 rear) 分别指向队列的队头元素和队尾元素。

    当数据元素进队列时,对应的操作应该是将其存储在rear指向的数组的位置,然后rear + 1,当需要出队列的时候,就需要做 top +1 的操作

    方法一:

    #include <stdio.h>
    #define DEBUG_LOG
    #define INFO
    #include "log.h"
    #include "malloc.h"
    
    typedef struct SortQueue{
        int* array;
        int top;
        int rear;
    }*sortQueue;
    
    /**
     * 初始化具有阿巴个元素的队列
     * @param n
     * @return
     */
    sortQueue init(){
        sortQueue queue = (sortQueue)malloc(sizeof (struct SortQueue));
        int array[] = {1,2,3,4};
        queue->array = array;
        queue->rear = 4;
        queue->top = 0;
    }
    
    /**
     * 进队列的方法
     * @param queue
     * @return
     * 把data放到queue 里面
     */
    sortQueue inQueue(sortQueue queue,int data){
        int rearIndex = queue->rear;
        queue->array[rearIndex] = data;
        queue->rear += 1;
    
        return queue;
    }
    
    /**
     * 出队列的方法
     * @param queue 
     * @return 
     */
    sortQueue outQueue(sortQueue queue){
        int topIndex = queue->top;
        int rearIndex = queue->rear;
        if (topIndex == rearIndex){
            INFO_LOG("There is not element!Can't out queue");
        } else{
            printf("The top element is >>>%d",queue->array[queue->top]);
        }
        queue->top+=1;
        return queue;
    }
    

    这种方法穿在一个问题:

    当数据全部出队后,top和rear的重合指向了a[4]而不是a[0],也就是说,整个顺序队列在数据的不断进队出队的过程中,在顺序表中的位置不断的后移

    影响:

    1. 顺序队列之前的数组存储空间将无法再被使用,造成空间浪费
    2. 如果顺序表申请的空间不够大,就容易造成溢出,产生溢出错误

    所以就有了方法二

    方法二:

    将顺序表打造成一个环状

    代码修改:

    /**
     * 进队列的方法
     * @param queue
     * @return
     * 把data放到queue 里面
     */
    sortQueue inQueue(sortQueue queue,int data){
        /*
         * 新增判断语句,如果再增加的一个元素的下一个元素大于max,则从a[0]重新开始存储
         * 如果rear +1 和 front 重合,则表明数组已满
         *
         */
        if (((queue->rear)+1)%sizeMax == queue->top){
            /**
             * 这里就表示空间已满,rear队尾指针和头指针重合
             */
            printf("The space if full");
            return queue;
        }
        int rearIndex = queue->rear;
        queue->array[rearIndex % sizeMax] = data;
        queue->rear = (rearIndex % sizeMax) + 1;
    
        return queue;
    }
    
    /**
     * 出队列的方法
     * @param queue
     * @return
     */
    sortQueue outQueue(sortQueue queue){
        int topIndex = queue->top;
        int rearIndex = queue->rear;
        //如果front == rear 表示队列为空
        if (topIndex == rearIndex){
            INFO_LOG("There is not element!Can't out queue");
        } else{
            printf("The top element is >>>%d",queue->array[queue->top]);
        }
        queue->top = (queue->top+1)%sizeMax;
        return queue;
    }
    

    通过取余的方式来实现最后可以接到表头,这样其实是一种很巧妙的方式实现顺序队列的头尾相接,且不用再本身的物理结构上进行修改,因为对于这个顺序队列还是线性的,但是在逻辑上已经是环状的了。

    注意:

    1. 当队列为空的时候,队列的头指针会等于队列的尾指针
    2. 当队列满员的时候,队列的头指针会等于队列的尾指针

    7)链式队列

    链式队列,通过链表实现队列的存储结构

    通过链表实现队列的方式和顺序队列是一样的,都需要借助一个top指针和一个rear指针,一个指向队列头,一个指向队列尾。

    #include <stdio.h>
    #include"log.h"
    #include <malloc.h>
    
    /*
     *定义链式队列的结点
     */
    typedef struct LinkQueueNode{
    	struct LinkQueueNode * next;
    	int data;
    }*linkQueueNode;
    
    /*
     * 向队列中插入数据应该向队尾插入
     * 对于链式队列来说就不存在会有空间满了的情况了
     * 传入链表的最后一个结点,直接把结点添加最后即可
     */
    linkQueueNode inQueue(linkQueueNode rear,int newData){
    	linkQueueNode newNode = (linkQueueNode)malloc(sizeof(struct LinkQueueNode));
    	newNode->next = NULL;
    	newNode->data = newData;
    	rear->next = newNode;
    	rear = newNode;
    	return newNode;
    }
    
    /*
     * 向队列中退出一个元素,将top指针所指向的首元素出队
     *	出队之后要根据对列的长度保证 top 指针和 rear 指针指向正确	
     *  如果队列出队后的长度大于等于1,则rear 指针不用管
     * 但是如果队列出队后的长度为0,这个时候就意味着rear指针的之前指向已经出队的node 这个时候就需要更新指针的指向了 
     */
    linkQueueNode outQueue(linkQueueNode top,linkQueueNode rear){
    	if (top == NULL || top->next == NULL)
    	{
    		printf("There is a empty queue");
    	}
    
    	linkQueueNode outNode = top;
    	printf("出栈元素是>>>>%d\n",outNode->data);
    	top = top->next;
    	/*
    	 * 如果尾指针指向一开始的首元素,且队列的长度为1,那么让他指向新的空结点
    	 */
    	if (rear == outNode)
    	{
    		rear = top;
    	}
    	free(outNode);
    }
    
    

    在出队元素的时候一定要提前判断队列中是否还有元素,要提示用户无法做出出队操作,保证程序的健壮性

    8)小结

    首先:虽然栈和队列存储结构不同,但是两者都是线性结构

    线性结构:用于存储逻辑关系为”一对一“数据的存储结构,比如说顺序存储结构和链式存储结构

    展开全文
  • 队列的模拟实现

    2016-11-29 14:39:41
    “排队”我们日常生活是经常遇到的,“先来先服务”的原则即排队问题的本质,实际上,操作系统,作业调度和输入输出管理都遵循“队列”。在数据结构队列是这样定义的:它是一种限定存取位置的线性表,只...
  • 堆栈这种数据结构数据的存取会服“先进后出”原则。 生活最常见的例子就是打开抽屉,假如有一排抽屉我们需要一一打开检查,我们会从下往上打开抽屉,再从上往下关闭——“先进后出”,先打开的抽屉最后再...
  • 栈和队列

    2020-10-25 18:59:11
    (2),无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。拿图 1 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈取出元素 1 时,根据"先进...
  • 堆栈队列

    2020-05-18 14:44:49
    使用是一级缓存,栈是向低地址扩展的数据结构,是一块连续内存区域,是数据暂时储存地方,栈元素个数为零时称为空栈,它是一种运算受限线性表,仅允许一端进行插入和删除运算(遵循先进后出原则),此...
  • 中存取数据的原则是 B A先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2 若将整数 12 34 依次进栈则不可能得到的出栈序列是 D A1234 B. 1324 C. 4321 D. 1423 3 链栈中进行出栈操作时 B A 需要判断栈是否满 ...
  • 中存取数据的原则是 B A 先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2 若将整数 12 3 4 依次进栈则不可能得到的出栈序列是 D A 1234 B. 1324 C. 4321 D. 1423 3 链栈中进行出栈操作时 B A 需要 判断栈...
  • 1.基本概念:栈是一种只能从表一端存取数据且遵循 "先进后出" 原则的线性存储结构。通常,栈开口端被称为栈顶;相应地,封口端被称为栈底。因此,栈顶元素指就是距离栈顶最近元素。 2.基本操作:基于栈结构...
  • 名师整理 优秀资源 数据结构 一单项选择题 1若某线性表最常用的操作是存取任一指定序号的元素和最后进行插入和删除运算则采用 存储方式最节省时间 [ C] 带头结点的双循环链表 2队列操作的原则是 [ D] 先进先出 3某...
  • 2009年9月全国计算机二级笔试试卷VISUAL FOXPRO数据程序设计一、选择题(每小题2分共70分)下列各题A B C D 四个...带连线2)下列数据结构,能按照“先进后出”原则存取数据的是A.循环队列B.栈C. 队列D.二叉树3)对...
  • 栈是一种只能从表一端存取数据且遵循 LIFO(先进后出)原则的线性存储结构。 栈开口端被称为栈顶 封口端被称为栈底。 通常只会对栈执行以下两种操作: 向栈添加元素,此过程被称为"进栈"(入栈或压栈); 从栈...
  • 不过在存取元素时候必须遵循先进先出原则,队列是一种特殊线性表,它只允许前端进行删除操作,而后端进行插入操作,进行插入操作端称为队尾,进行删除操作端称为队头,队列中没有元素时,称为空...
  • 数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    (1)数据结构课程数据的逻辑结构,数据的存储结构及数据的运算之间存在着怎样的关系? (2)若逻辑结构相同但存储结构不同,则为不同的数据结构。这样的说法对吗?举例说明之。 (3)给定的逻辑结构及其...
  • 下列各题ABCD四个选项只有一个选项是正确请将正确选项涂写答题卡相应位置上答试卷上不得分 1下列数据结构属于非线性结构是_ A)循环队列 B)带链队列 C)二叉树 D)带链栈 2下列数据结构能够按照...
  • 下列各题ABCD四个选项只有一个选项是正确请将正确选项涂写答题卡相应位置上答试卷上不得分 1下列数据结构属于非线性结构是_ A)循环队列 B)带链队列 C)二叉树 D)带链栈 2下列数据结构能够按照...
  • 18.1.4 函数抛出异常 546 18.1.5 异常说明 547 18.2 异常处理编程技术 549 18.2.1 抛出异常时机 549 18.2.2 异常类层次结构 552 18.2.3 测试可用内存 552 18.2.4 再次抛出异常 552 第19章 标准...
  • 下列数据结构,能够按照“先进后出”原则存取数据的是()。A.循环队列B.栈C.队列D.二叉树3.对于循环队列,下列叙述正确的是()。A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队...
  • 线性结构-栈

    2021-03-02 22:21:47
    文章目录栈和队列一 栈一.什么是栈进栈和出栈栈实现方法...栈是一种只能从表一端存取数据,且遵循"先进后出"原则的线性存储结构 进栈和出栈 进栈:将数据存储到站里面 出栈:将数据从栈中间取出 栈实现方法 栈:"特殊
  • 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出线性表 D. 队列是先进后出线性表 (24) 对建立良好程序设计风格,下面描述正确是(A) 注:P48 A. 程序应简单、清晰、可读性好 B. 符号名...
  • (2)下列数据结构,能够按照“先进后出”原则存取数据的是( )。 A)循环队列 C)队列 (3)对于循环队列,下列叙述正确的是( A)队头指针是固定不变的 B)队头指针一定大于队尾指针 C)队头指针一定小于...
  • Javascript 知识扫盲(一)

    2020-08-18 11:06:24
    Javascript 知识扫盲(一) ...存取数据类似于key/value,依据属性名获取对应值。 栈:栈是一种数据内存中的存储区域,它表达是一种存取方式,遵循先进后出,后进先出基本原则。同时它可以用来规定代码
  • (2) 数据的逻辑结构计算机存储空间的存放形式称为数据的______。 答:模式#逻辑模式#概念模式 (3) 若按功能划分,软件测试的方法通常分为白盒测试方法和______测试方法。 答:黑盒 (4) 如果一个工人可管理多个...
  • 以往只能运行浏览器中的 JavaScript 也可以运行服务器上,前端工程师可以用自己最熟悉语言来写服务端代码。于是前端工程师开始使用 Node.js 做全栈开发,开始由前端工程师向全栈工程师方向...
  • 队列中的元素是按照q1,q2,…,qn顺序进入,退出队列也只能按照这个次序依次退出,即只有q1,q2,…,qn-1都退队之后,qn才能退出队列。因最先进入队列元素将最先出队,所以队列具有先进先出特性,体现...
  • C++标准程序库STL.pdf

    千次下载 热门讨论 2013-02-26 11:05:11
    经典的数据结构数量有限,但是我们常常重复着一些为了实现向量、链表等结构而编写的代码,这些代码都十分相似,只是为了适应不同数据的变化而细节上有所出入。STL容器就为我们提供了这样的方便,它允许我们重复...

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

在队列中存取数据的原则是