精华内容
下载资源
问答
  • 栈和队列

    千次阅读 2020-01-26 15:41:42
    用具体的实例介绍数据结构中的栈和队列,并以python代码用数组的方式实现栈和队列常用的基本操作

    物理结构与逻辑结构

    把物质层面的人体比作数据存储的物理结构,那么精神层面的人格则是数据存储的逻辑结构。逻辑结构是抽象的概念,它依赖于物理结构而存在。
    在这里插入图片描述
    下面我们来讲解两个常用数据结构:栈和队列。这两者都属于逻辑结构,它们的物理实现既可以利用数组,也可以利用链表来完成。

    假如有一个又细又长的圆筒,圆筒一端封闭,另一端开口。往圆筒里放入乒乓球,先放入的靠近圆筒底部,后放入的靠近圆筒入口。
    在这里插入图片描述
    那么,要想取出这些乒乓球,则只能按照和放入顺序相反的顺序来取,先取出后放入的,再取出先放入的,而不可能把最里面最先放入的乒乓球优先取出。
    在这里插入图片描述
    栈(stack)是一种线性数据结构,它就像一个上图所示的放入乒乓球的圆筒容器,栈中的元素只能先入后出(First In Last Out,简称FILO)。最早进入的元素存放的位置叫作栈底(bottom),最后进入的元素存放的位置叫作栈顶(top)。

    栈这种数据结构既可以用数组来实现,也可以用链表来实现。

    栈的数组实现如下。
    在这里插入图片描述
    栈的链表实现如下。
    在这里插入图片描述
    栈的基本操作:

    class Stack(object):
        """用数组实现栈"""
        def __init__(self):
            self.__list =[]
    
        def push(self,item):
            """添加一个新元素item到栈顶"""
            self.__list.append(item)
    
    
        def pop(self):
            """弹出栈顶元素"""
            return self.__list.pop()
    
        def peek(self):
            """返回栈顶元素"""
            if self.__list:
                return self.__list[-1]
            else:
                return None
    
        def is_empty(self):
            """判断栈是否为空"""
            return self.__list is None
    
        def size(self):
            """返回栈的元素个数"""
            return len(self.__list)
    

    队列

    假如公路上有一条单行隧道,所有通过隧道的车辆只允许从隧道入口驶入,从
    隧道出口驶出,不允许逆行。
    在这里插入图片描述
    因此,要想让车辆驶出隧道,只能按照它们驶入隧道的顺序,先驶入的车辆先驶出,后驶入的车辆后驶出,任何车辆都无法跳过它前面的车辆提前驶出。
    在这里插入图片描述
    队列(queue)是一种线性数据结构,它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出,队列中的元素只能先入先出(First In First Out,简称FIFO)。队列的出口端叫作队头(front),队列的入口端叫作队尾(rear)。

    与栈类似,队列这种数据结构既可以用数组来实现,也可以用链表来实现。

    队列的数组实现如下。
    在这里插入图片描述
    队列的链表实现如下。
    在这里插入图片描述
    队列的基本操作:

    class Queue(object):
        """用顺序表实现队列"""
        def __init__(self):
            self.__list = []
    
        def enqueue(self,item):
            self.__list.append(item)    # 入队频繁
           # self.__list.insert(0,item) # 出队少
    
        def del_queue(self):
            return self.__list.pop(0) # 入队频繁
           # return self.__list.pop() # 出队少
    
        def is_empty(self):
            return self.__list is None
    
        def size(self):
            return len(self.__list)
    

    双端队列

    双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。

    双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
    在这里插入图片描述

    双端队列的基本操作:

    class Queue(object):
        """用顺序表实现双端队列"""
        def __init__(self):
            self.__list = []
    
        def add_front(self,item):
            self.__list.append(item)  
    
        def add_rear(self,item):
            self.__list.append(item)  
    
        def pop_front(self):
            return self.__list.pop(0)
    
        def pop_rear(self):
            return self.__list.pop(0)
    
        def is_empty(self):
            return self.__list is None
    
        def size(self):
            return len(self.__list)
    

    优先队列

    还有一种队列,它遵循的不是先入先出,而是谁的优先级最高,谁先出队。
    在这里插入图片描述
    优先队列已经不属于线性数据结构的范畴了,它是基于二叉堆来实现的。关于优先队列的原理和使用情况,我们会在其它文章中进行详细介绍。

    栈和队列的应用

    栈的输出顺序和输入顺序相反,所以栈通常用于对“历史”的回溯,也就是逆流而上追溯“历史”。

    例如实现递归的逻辑,就可以用栈来代替,因为栈可以回溯方法的调用链。
    在这里插入图片描述

    栈还有一个著名的应用场景是面包屑导航,使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。
    在这里插入图片描述
    使用栈虽然很方便,但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。在这种情况下,你有两种选择。

    • 重新编写代码,转而使用循环。
    • 使用尾递归 。这是一个高级递归主题,不在本节的讨论范围内。另外,并非所有的语言都支持尾递归。

    队列
    队列的输出顺序和输入顺序相同,所以队列通常用于对“历史”的回放,也就是按照“历史”顺序,把“历史”重演一遍。

    例如在多线程中,争夺公平锁的等待队列,就是按照访问顺序来决定线程在队列中的次序的。

    再如网络爬虫实现网站抓取时,也是把待抓取的网站URL存入队列中,再按照存入队列的顺序来依次抓取和解析的。
    在这里插入图片描述

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

    万次阅读 多人点赞 2012-06-19 12:53:15
    其特殊性在于限定插入删除数据元素的操作只能在线性表的一端进行。如下所示: 结论:后进先出(Last In First Out),简称为LIFO线性表。 的基本运算有六种: 构造空栈:InitStack(S)、 判空: StackEmpty...

     

     

    1.栈


    1.1 栈的定义

    栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示:

    结论:后进先出(Last In First Out),简称为LIFO线性表。

     

    栈的基本运算有六种:

    构造空栈:InitStack(S)、

    判栈空: StackEmpty(S)、

    判栈满: StackFull(S)、

    进栈: Push(S,x)、可形象地理解为压入,这时栈中会多一个元素

    退栈: Pop(S) 、 可形象地理解为弹出,弹出后栈中就无此元素了。

    取栈顶元素:StackTop(S),不同与弹出,只是使用栈顶元素的值,该元素仍在栈顶不会改变。

        由于栈也是线性表,因此线性表的存储结构对栈也适用,通常栈有顺序栈链栈两种存储结构,这两种存储结构的不同,则使得实现栈的基本运算的算法也有所不同。

     

    我们要了解的是,在顺序栈中有"上溢"和"下溢"的概念。顺序栈好比一个盒子,我们在里头放了一叠书,当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^),那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算,哼哼),这时就是"上溢","上溢"也就是栈顶指针指出栈的外面,显然是出错了。反之,当栈中已没有书时,我们再去拿,看看没书,把盒子拎起来看看盒底,还是没有,这就是"下溢"。"下溢"本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。

    链栈则没有上溢的限制,它就象是一条一头固定的链子,可以在活动的一头自由地增加链环(结点)而不会溢出,链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要在头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。

     

    1.2 栈的顺序存储

     

    使用c++的面向对象封装:

    // Test.cpp : Defines the entry point for the console application.
    //
    #include "stdafx.h"  
    #include <iostream>
    using namespace std;
    #define MAX 10 // MAXIMUM STACK CONTENT
    class stack   
    {   
    private:   
    	int arr[MAX]; 
    	int top; 
    public:   
    	stack() 
    	{   
    		inItStack(); 
    	}
    	/************************************************************************/
    	/* 初始化栈                                                                     */
    	/************************************************************************/
    	void inItStack() 
    	{ 
    		top=-1; 
    	} 
    	/************************************************************************/
    	/* 入栈                                                                     */
    	/************************************************************************/
    	void push(int a) 
    	{   
    		top++;
    		if(top < MAX)  {   
    			arr[top]=a; 
    		}   else   {   
    			cout<<"STACK FULL!!"<<top;   
    		}   
    	}   
    	/************************************************************************/
    	/* 出栈                                                                     */
    	/************************************************************************/
    	int pop()
    	{    
    		if(isEmpty())   {   
    			cout<<"STACK IS EMPTY ";
    			return NULL;   
    		} else {   
    			int data=arr[top]; 
    			arr[top]=NULL; 
    			top--;
    			return data; 
    		}   
    	}   
    
    	/************************************************************************/
    	/* 是否为空                                                                     */
    	/************************************************************************/
    	bool isEmpty()
    	{
    		if(top == -1) return true;
    		else return false;
    	}
    };   
    int main()   
    {   
    	stack a;   
    	a.push(3);   
    	a.push(10);   
    	a.push(1);   
    	cout<<"Pop:"<<a.pop();      
    	return 0;   
    }
    

    结论:由于栈的插入和删除操作具有它的特殊性,所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题,但栈容量难以扩充的弱点仍就没有摆脱。

    在java里面的工具栈java.util.Stack,其继承了Vector的基础上拓展5个方法push()、pop()、peek()、empty()、search()而来,使用数组去实现即线性存储。

    package com.javademo.demo.datastructure;
    import java.util.Stack;
    public class StackTest {
        private Stack<Integer> stack = new Stack<Integer>();
        public static void main(String[] args) {
            int e = 1;
            StackTest stackTest = new StackTest();
            stackTest.stack.push(1);
            stackTest.stack.push(2);
            stackTest.stack.push(3);
            while (!stackTest.stack.empty()) {
                System.out.print(stackTest.stack.pop() + "\t");
            }
        }
    }

    1.3 栈的链式存储


    若是栈中元素的数目变化范围较大或不清楚栈元素的数目,就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作"链栈"。链栈通常用一个无头结点的单链表表示。如图所示:

    栈的操作是线性表操作的特例。

    简单用c实现:

    // Test.cpp : Defines the entry point for the console application.  
    //  
    #include "stdafx.h"  
    #include <stdio.h>  
    #include "stdlib.h"
    #include <iostream>
    using namespace std;
    //宏定义  
    #define TRUE   1  
    #define FALSE   0  
    #define OK    1  
    #define ERROR   0  
    #define INFEASIBLE -1  
    #define OVERFLOW -2 
    #define STACKEMPTY -3  
    
    #define LT(a,b)   ((a)<(b))  
    #define N = 100         
    
    typedef int Status;  
    typedef int ElemType;  
    
    typedef struct LNode{  
    	ElemType		data;               
    	struct LNode   *next;     
    }LNode, *LinkList; 
    
    typedef struct stack{
    	LinkList top;
    } STACK;
    
    
    /************************************************************************/
    /*     接口:
    */
    /************************************************************************/
    void InitStack(STACK &S);
    void Push(STACK &S,ElemType e);
    void Pop(STACK &S, ElemType *e);
    ElemType GetTop(STACK S,ElemType *e);
    int StackEmpty(STACK S);
    
    /************************************************************************/
    /* 
    */
    /************************************************************************/
    void InitStack(STACK &S)
    {
    	S.top=NULL;
    }
    
    /************************************************************************/
    /* 入栈 
    */
    /************************************************************************/
    void Push(STACK &S,ElemType e)
    {
    	LinkList p;
    	p = (LinkList )malloc(sizeof(LNode));
    	if (!p) exit(OVERFLOW);
    	p->data = e;
    	p->next = S.top;
    	S.top = p;
    }
    /************************************************************************/
    /* 出栈
    */
    /************************************************************************/
    void Pop(STACK &S, ElemType *e)
    {
    	LinkList p;
    	if(StackEmpty(S)) exit(STACKEMPTY);
    	*e = S.top->data;
    	p = S.top;
    	S.top = p->next; 
    	free(p);
    }
    /************************************************************************/
    /* 获取栈顶元素内容
    */
    /************************************************************************/
    ElemType GetTop(STACK S, ElemType *e)
    {
    	if(StackEmpty(S)) exit(STACKEMPTY);
    	*e = S.top->data;
    }
    
    /************************************************************************/
    /* 判断栈S是否空 
    */
    /************************************************************************/
    int StackEmpty(STACK S) 
    {
    	if(S.top==NULL) return TRUE;
    	return   FALSE;
    }
    
    void main()  
    {  
    
    	STACK S;
    	InitStack( S);
    	Push(S, 3);
    	Push(S, 4);
    	ElemType e;
    	Pop(S,&e);
    	cout<<"Pop elem:"<<e;
    }  
    

     

    1.4 栈的应用

     

    1)  数制转换

    2)语法词法分析

    3)表达式求值等

     

    1.5 栈的递归和实现

    汉诺塔的问题:

    解决:

    1)如果有一个盘子,直接从X移到Z即可。
    2)如果有n个盘子要从X移到Z,Y作为辅助。问题可以转化为,先将上面n-1个从X移动到Y,Z作为辅助,然后将第n个从X移动到Z,最后将剩余的n-1个从Y移动到Z,X作为辅助。

    完整实现代码,包括栈的实现:

     

    // Test.cpp : Defines the entry point for the console application.  
    //  
    #include "stdafx.h"  
    #include <stdio.h>  
    #include "stdlib.h"
    #include <iostream>
    using namespace std;
    //宏定义  
    #define TRUE   1  
    #define FALSE   0  
    #define OK    1  
    #define ERROR   0  
    #define INFEASIBLE -1  
    #define OVERFLOW -2 
    #define STACKEMPTY -3  
    
    #define LT(a,b)   ((a)<(b))  
    #define N = 100         
    
    typedef int Status;  
    typedef int ElemType;  
    
    typedef struct LNode{  
    	ElemType		data;               
    	struct LNode   *next;     
    }LNode, *LinkList; 
    
    typedef struct stack{
    	LinkList top;
    } STACK;
    
    
    /************************************************************************/
    /*     接口:
    */
    /************************************************************************/
    void InitStack(STACK &S);
    void Push(STACK &S,ElemType e);
    void Pop(STACK &S, ElemType *e);
    ElemType GetTop(STACK S,ElemType *e);
    int StackEmpty(STACK S);
    
    /************************************************************************/
    /* 
    */
    /************************************************************************/
    void InitStack(STACK &S)
    {
    	S.top=NULL;
    }
    
    /************************************************************************/
    /* 入栈 
    */
    /************************************************************************/
    void Push(STACK &S,ElemType e)
    {
    	LinkList p;
    	p = (LinkList )malloc(sizeof(LNode));
    	if (!p) exit(OVERFLOW);
    	p->data = e;
    	p->next = S.top;
    	S.top = p;
    }
    /************************************************************************/
    /* 出栈
    */
    /************************************************************************/
    void Pop(STACK &S, ElemType *e)
    {
    	LinkList p;
    	if(StackEmpty(S)) exit(STACKEMPTY);
    	*e = S.top->data;
    	p = S.top;
    	S.top = p->next; 
    	free(p);
    }
    /************************************************************************/
    /* 获取栈顶元素内容 
    
    */
    /************************************************************************/
    ElemType GetTop(STACK S, ElemType *e)
    {
    	if(StackEmpty(S)) exit(STACKEMPTY);
    	*e = S.top->data;
    }
    void printStack(STACK S){
    	LinkList p;
    	p = S.top;
    	printf("栈: ");
    	while (p) {
    		printf("%d ", p->data);
    		p = p->next;
    	}
    }
    /************************************************************************/
    /* 如果有一个盘子,直接从X移到Z即可。
    如果有n个盘子要从X移到Z,Y作为辅助。问题可以转化为,先将上面n-1个从X移动到Y,Z作为辅助,然后将第n个从X移动到Z,最后将剩余的n-1个从Y移动到Z,X作为辅助。
    */
    /************************************************************************/
    
    void move(STACK &Sa,STACK &Sb)
    {	
    	ElemType e;
    	Pop(Sa,&e);
    	Push(Sb, e);
    }
    void hanoi(int n,STACK  &X,STACK &Y,STACK &Z)
    {
    	if(n==1) return move(X, Z);		//将圆盘1号直接移到z
    	hanoi(n-1,X,Z,Y);				//将x上的1大n-1圆盘移到y,z做辅助塔
    	move(X, Z);						//将编号为n的圆盘移z
    	hanoi(n-1,Y,X,Z);			    //将y上的1大n-1圆盘移到z,x做辅助塔
    }
    
    /************************************************************************/
    /* 判断栈S是否空 
    */
    /************************************************************************/
    int StackEmpty(STACK S) 
    {
    	if(S.top==NULL) return TRUE;
    	return   FALSE;
    }
    
    void main()  
    {  
    
    	STACK Sx, Sy,Sz;
    	InitStack( Sx);
    	InitStack( Sy);
    	InitStack( Sz);
    	int i, n = 10;
    	for (i = 10 ; i>=1 ;i--) {
    		Push(Sx, i);
    	}
    	printStack(Sx);
    	hanoi(n,  Sx,Sy,Sz);
    	printStack(Sz);
    }  
    

     

     

     

     

     

     

    1.队列


    1.1 队列定义 

    队列(Queue)也是一种运算受限的线性表它的运算限制与栈不同,是两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进)允许删除的一端称为队尾(rear),允许插入的一端称为队头 (Front)

    ,队列的操作原则是先进先出的,所以队列又称作FIFO表(First In First Out)

    队列的基本运算也有六种:

    置空队 :InitQueue(Q)

    判队空: QueueEmpty(Q)

    判队满: QueueFull(Q)

    入队 : EnQueue(Q,x)

    出队 : DeQueue(Q)

    取队头元素: QueueFront(Q),不同与出队,队头元素仍然保留。

     

    队列也有顺序存储和链式存储两种存储结构,前者称顺序队列,后者为链队

    对于顺序队列,我们要理解"假上溢"的现象。

    我们现实中的队列比如人群排队买票,队伍中的人是可以一边进去从另一头出来的,除非地方不够,总不会有"溢出"的现象,相似地,当队列中元素完全充满这个向量空间时,再入队自然就会上溢,如果队列中已没有元素,那么再要出队也会下溢。

    那么"假上溢"就是怎么回事呢?

    因为在这里,我们的队列是存储在一个向量空间里,在这一段连续的存储空间中,由一个队列头指针和一个尾指针表示这个队列,当头指针和尾指针指向同一个位置时,队列为空,也就是说,队列是由两个指针中间的元素构成的。在队列中,入队和出队并不是象现实中,元素一个个地向前移动,走完了就没有了,而是指针在移动,当出队操作时,头指针向前(即向量空间的尾部)增加一个位置,入队时,尾指针向前增加一个位置,在某种情况下,比如说进一个出一个,两个指针就不停地向前移动,直到队列所在向量空间的尾部,这时再入队的话,尾指针就要跑到向量空间外面去了,仅管这时整个向量空间是空的,队列也是空的,却产生了"上溢"现象,这就是假上溢。

    为了克服这种现象造成的空间浪费,我们引入循环向量的概念,就好比是把向量空间弯起来,形成一个头尾相接的环形,这样,当存于其中的队列头尾指针移到向量空间的上界(尾部)时,再加1的操作(入队或出队)就使指针指向向量的下界,也就是从头开始。这时的队列就称循环队列

    通常我们应用的大都是循环队列。由于循环的原因,光看头尾指针重叠在一起我们并不能判断队列是空的还是满的,这时就需要处理一些边界条件,以区别队列是空还是满。方法至少有三种,一种是另设一个布尔变量来判断(就是请别人看着,是空还是满由他说了算),第二种是少用一个元素空间,当入队时,先测试入队后尾指针是不是会等于头指针,如果相等就算队已满,不许入队。第三种就是用一个计数器记录队列中的元素的总数,这样就可以随时知道队列的长度了,只要队列中的元素个数等于向量空间的长度,就是队满。


    2.2 队列的顺序存储

    顺序存储如图:

    由于是顺序存储结构的存储空间是静态分配的,所以在添加数据的时,有可能没有剩余空间的情况。

    解决这种“假溢出”情况,使用循环队列在c语言中,不能用动态分配的一维数组来实现循环队列。若使用循环队列,必须设置最大队列长度,若无法估计最大长度,就使用链式队列。

    c实现:

     

    // Test.cpp : Defines the entry point for the console application.  
    //  
    #include "stdafx.h"  
    #include <stdio.h>  
    #include "stdlib.h"
    #include <iostream>
    using namespace std;
    //宏定义  
    #define TRUE   1  
    #define FALSE   0  
    #define OK    1  
    #define ERROR   0  
    #define INFEASIBLE -1  
    #define OVERFLOW -2 
    #define QUEUEEMPTY  -3  
          
    #define MAX_QUEUE 10 //队列的最大数据元素数目
    
    typedef int Status;  
    typedef int ElemType;  
    
    typedef struct queue{  
    	ElemType		elem[MAX_QUEUE] ;     ///假设当数组只剩下一个单元时认为队满          
    	int front;		//队头指针
    	int	rear;		//队尾指针   
    }QUEUE; 
    
    
    /************************************************************************/
    /*     各项基本操作算法。
    */
    /************************************************************************/
    void InitQueue(QUEUE *&Q);
    void EnQueue(QUEUE *Q,ElemType elem);
    void DeQueue(QUEUE *Q,ElemType *elem);
    int QueueEmpty(QUEUE Q);
    
    /************************************************************************/
    /* 
      初始化
      直接使用结构体指针变量,必须先分配内存地址,即地址的指针
    */
    /************************************************************************/
    void InitQueue(QUEUE *&Q) 
    {
    
    	Q = (QUEUE *) malloc (sizeof(QUEUE));
    	Q->front = Q->rear = -1;
    
    }
    /************************************************************************/
    /*     入队                                                              
    */
    /************************************************************************/
     
    void EnQueue(QUEUE *Q, ElemType elem)
    {
    	if((Q->rear+1)% MAX_QUEUE == Q->front) exit(OVERFLOW);
    	Q->rear = (Q->rear + 1)%MAX_QUEUE;
    	Q->elem[Q->rear] = elem; 
    }
    /************************************************************************/
    /*     出队                                                               
    */
    /************************************************************************/
    void DeQueue(QUEUE *Q,ElemType *elem)
    {
    	if (QueueEmpty(*Q))  exit(QUEUEEMPTY);
    	Q->front =  (Q->front+1) % MAX_QUEUE;
    	*elem=Q->elem[Q->front];
    }
    /************************************************************************/
    /*    获取队头元素内容                                                            
    */
    /************************************************************************/
    
    void GetFront(QUEUE Q,ElemType *elem) 
    {
    	if ( QueueEmpty(Q) )  exit(QUEUEEMPTY);
    	*elem = Q.elem[ (Q.front+1) % MAX_QUEUE ];
    }
    /************************************************************************/
    /*    判断队列Q是否为空                                                             
    */
    /************************************************************************/
    int QueueEmpty(QUEUE Q)
    {
    	if(Q.front==Q.rear) return TRUE;
    	else return FALSE;
    }
    
    void main()  
    {  
    
    	QUEUE *Q;
    	InitQueue( Q);
    	EnQueue( Q, 1);
    	EnQueue( Q, 2);
    	ElemType e;
    	DeQueue( Q,&e);
    	cout<<"De queue:"<<e;
    }  
    


    注意:InitQueue(QUEUE *&Q) 传的是指针的地址。

     

     

    2.3 链式队列:

    // Test.cpp : Defines the entry point for the console application.  
    //  
    #include "stdafx.h"  
    #include <stdio.h>  
    #include "stdlib.h"
    #include <iostream>
    using namespace std;
    //宏定义  
    #define TRUE   1  
    #define FALSE   0  
    #define OK    1  
    #define ERROR   0  
    #define INFEASIBLE -1  
    #define OVERFLOW -2 
    #define QUEUEEMPTY  -3  
          
    
    typedef int Status;  
    typedef int ElemType;  
    
    typedef struct LNode {			//链式队列的结点结构
    	ElemType elem;			//队列的数据元素类型
    	struct LNode *next;		 //指向后继结点的指针
    }LNode, *LinkList;
    
    typedef struct queue{	//链式队列
    	LinkList front;		//队头指针
    	LinkList rear;		//队尾指针
    }QUEUE; 
    
    /************************************************************************/
    /*     各项基本操作算法。
    */
    /************************************************************************/
    void InitQueue(QUEUE *Q);
    void EnQueue(QUEUE *Q,ElemType elem);
    void DeQueue(QUEUE *Q,ElemType *elem);
    void GetFront(QUEUE Q,ElemType *elem) ;
    bool QueueEmpty(QUEUE Q);
    
    /************************************************************************/
    
    
    /*初始化队列Q  */
    void InitQueue(QUEUE *Q)
    {
    	Q->front = (LinkList)malloc(sizeof(LNode));
    	if (Q->front==NULL) exit(ERROR);
    	Q->rear= Q->front;
    }
    /*入队 */ 
    void EnQueue(QUEUE *Q,ElemType elem)
    {
    	LinkList s;
    	s = (LinkList)malloc(sizeof(LNode));
    	if(!s) exit(ERROR);
    	s->elem = elem;
    	s->next = NULL;
    	Q->rear->next = s;
    	Q->rear = s;
    }
    
    /*出队  */ 
    void DeQueue(QUEUE *Q,ElemType *elem)
    {
    	LinkList s;
    	if(QueueEmpty(*Q)) exit(ERROR);
    	*elem = Q->front->next->elem;
    	s = Q->front->next;
    	Q->front->next = s->next;
    	free(s);
    }
    /*获取队头元素内容  */ 
    
    void GetFront(QUEUE Q,ElemType *elem) 
    {
    	if(QueueEmpty(Q)) exit(ERROR);
    	*elem = Q.front->next->elem;
    }
    /*判断队列Q是否为空   */ 
    bool QueueEmpty(QUEUE Q)
    {
    	if(Q.front == Q.rear) return TRUE;
        return FALSE;
    }
    
    void main()  
    {  
    
    	QUEUE Q;
    	InitQueue( &Q);
    	EnQueue( &Q, 1);
    	EnQueue( &Q, 2);
    	ElemType e;
    	DeQueue( &Q,&e);
    	cout<<"De queue:"<<e;
    }  
    

     

     

    2. 4.队列的应用
    【举例1】银行排队
    【举例2】模拟打印机缓冲区。
    在主机将数据输出到打印机时,会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然,这样会降低主机的使用效率。为此人们设想了一种办法:为打印机设置一个打印数据缓冲区,当主机需要打印数据时,先将数据依次写入这个缓冲区,写满后主机转去做其他的事情,而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印,这样做即保证了打印数据的正确性,又提高了主机的使用效率。由此可见,打印机缓冲区实际上就是一个队列结构。
    【举例3CPU分时系统
    在一个带有多个终端的计算机系统中,同时有多个用户需要使用CPU运行各自的应用程序,它们分别通过各自的终端向操作系统提出使用CPU的请求,操作系统通常按照每个请求在时间上的先后顺序,将它们排成一个队列,每次把CPU分配给当前队首的请求用户,即将该用户的应用程序投入运行,当该程序运行完毕或用完规定的时间片后,操作系统再将CPU分配给新的队首请求用户,这样即可以满足每个用户的请求,又可以使CPU正常工作。
     

    展开全文
  • 2022年考研数据结构_3 栈和队列

    万次阅读 2020-12-28 16:37:40
    栈和队列3.1 栈3.1.1 栈的定义3.1.2 栈的实现3.1.3 栈的应用(1)递归(2)四则运算表达式求解①中缀表达式转后缀表达式②后缀表达式的计算3.2 队列3.2.1 队列的定义3.2.2 队列的实现3.2.2 队列的应用3. 3 应用3.3.1 ...

    https://gitee.com/fakerlove/Data-Structure

    3. 栈和队列

    3.1 栈

    3.1.1 栈的定义

    栈是限定仅在表尾进行插入和删除操作的线性表。把允许插入的一端称为栈顶,另一端称为栈底,不含任何元素的栈称为空栈。栈是后进先出的线性表

    3.1.2 栈的实现

    栈的实现有数组和链表两种方式。其中,数组方式很简单,就是定义一个数组,然后用一个int类型的变量用来标识栈顶,每次入栈的时候将新元素插入到数组尾处,这里就不实现了。因为在链表一节中已经实现了单链表,以及在其尾部插入(相当于入栈操作)的算法,我们这里直接就继承我们实现的单链表,增加栈的弹栈、是否为空的判断两个方法。实现代码如下:

    • Java
    public class LinkStack<T> extends LinkList<T> {
        public boolean isEmpty(){
            return length==0;
        }
    
        /**
         * 弹栈
         * @return
         */
        public T pop(){
            if (this.head!=null){
                return remove(this.length-1);
            }
            return null;
        }
    }
    
    1234567891011121314151617
    

    上述代码中,LinkList的实现见链表一节。使用示例如下:

    		LinkStack<String> stack=new LinkStack<>();
            stack.pushBack("0");
            stack.pushBack("1");
            stack.pushBack("2");
            System.out.println(stack);
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
    12345678
    

    此处的链表是使用的尾插法,但是这样其实在弹栈以及入栈的时候性能并不好,因为每次入栈和弹栈都需要遍历链表,所以应该使用头插法,此处就需要重写单链表中的pushBack方法。重写后的链式存储栈的代码如下:

    public class LinkStack<T> extends LinkList<T> {
        public boolean isEmpty(){
            return length==0;
        }
    
        /**
         * 弹栈
         * @return
         */
        public T pop(){
            if (this.head!=null){
                return remove(0);
            }
            return null;
        }
         /**
         * 获取栈尾元素,但并不弹出
         * @return
         */
        public T peek(){
            if (this.head!=null){
                return get(0);
            }
            return null;
        }
        
        /**
         * 重写pushback方法,使用头插法,每次将节点插入到链表的头部
         * @param data
         */
        @Override
        public void pushBack(T data) {
            insert(0,data);
        }
    
        /**
         * 重写toString方法,从后往前输出
         * @return
         */
        @Override
        public String toString() {
            String result="";
            Node node=head;
            while (node!=null){
                result=node.getData()+","+result;
                node=node.getNext();
            }
            return result;
        }
    }
    1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
    

    在重写pushBack和pop方法的同时,还要重写toString,让输出是从后往前输出。使用头插法以后,这个链式栈的性能就好多了。同理,我们用C++来实现头插法的链式栈。其中父类LinkList的实现仍见链表一节。

    • C++
    #include "../LinkList/LinkedList.h"
    template<class T>
    class LinkStack:LinkList<T>
    {
    public:
    	/*
    	 * 重写插入方法,使用头插法
    	 */
    	void pushBack(T data)
    	{
    		insert(0, data);
    	}
    	T peek(){
            if (this->head!=null){
                return get(0);
            }
            return NULL;
        }
    	
    	T pop()
    	{
    		if(this->head)
    		{
    			return remove(0);
    		}
    		return NULL;
    	}
    };
    
    1234567891011121314151617181920212223242526272829
    

    使用示例为:

        LinkStack<string> link_stack;
    	link_stack.pushBack("0");
    	link_stack.pushBack("1");
    	link_stack.pushBack("2");
    	cout << link_stack.pop()<<",";
    	cout << link_stack.pop()<<",";
    	cout << link_stack.pop()<<",";
    1234567
    

    3.1.3 栈的应用

    栈最最常见的应该是平时软件中用到的撤销或者回退了吧。除此之外,栈还有很多的应用,下面介绍几个应用。

    (1)递归

    函数自己调用自己,就是递归。递归的调用需要栈的辅助,在每次调用自己之前,都要将当前的变量压栈存储起来,以便回退时恢复。
    在这里,我想说一个以前没有搞清楚的应该使用递归解决的例子。

    • 问题描述: 求0—n-1这n个数的全排列
    • 样例: 输入3,输出012,021,102,120,210,201。
    • 分析: 求1—n-1的全排列,过程应是这样的:先将第一个数固定,然后求剩下的n-1个数的全排列。求n-1个数的全排列的时候,还是一样,将第一个数固定,求n-2个数的全排列。直到剩下一个数,那他的全排列就是自己。那这个固定的数字应该有多种取值,比如求0,1,2三个数的全排列,固定的第一个数,应有0,1,2三种取值对吧,当固定第一个数,比如固定了0,那剩下1,2两个数,再固定一个数,这个数有1和2两种取值,有没有发现什么?我们发现,这个固定的数的取值,不就是将固定的位置的数和剩下的数字不断交换的过程么。理解了这个,来写代码看看(此处只写java代码,因为我这里每个例子都是用内部类定义的,所以class前面都有public和static关键字)。
    • Java实现
    public static class FullArrange{//全排列
    
            /**
             * 将list中,下标为i和下标为j的两个元素交换
             * @param list
             * @param i
             * @param j
             */
            public void swap(int[] list,int i,int j){
                int tmp=list[i];
                list[i]=list[j];
                list[j]=tmp;
            }
    
            public void perm(int[] list,int start,int end){
                if (start==end-1){
                    String tmp="";
                    for (int i=0;i<end;i++)
                       tmp+=list[i]+",";
                    System.out.println(tmp);
                }else {
                    for (int i=start;i<end;i++){
                        swap(list,start,i);
                        perm(list,start+1,end);
                        swap(list,start,i);
                    }
                }
            }
    
            /**
             * 测试函数,输出0——n的全排列
             * @param n
             */
            public void test(int n){
                int[] list=new int[n];
                for (int i=0;i<n;i++)
                    list[i]=i;
                perm(list,0,n);
            }
        }
    12345678910111213141516171819202122232425262728293031323334353637383940
    

    上述代码,其他的都很好理解,关键在于下面这三句代码:

    swap(list,start,i);
    perm(list,start+1,end);
    swap(list,start,i);
    123
    

    其中,第一句很好理解,就是那个固定的数的所有取值,第二句也好理解,就是求当一个数字固定后,剩下的数的全排列(这里就是递归),那第三句是干啥的呢?其实也比较好理解,第三句的作用是将第一句元素交换后的数组还原,你在第一句代码中将数组中的元素交换过了,求过递归以后,应该把数组还原,不然数组就和原来的不一样了。
    使用示例:

     FullArrange arrange=new FullArrange();
     arrange.test(3);
    12
    

    输出结果

    0,1,2,
    0,2,1,
    1,0,2,
    1,2,0,
    2,1,0,
    2,0,1,
    123456
    

    (2)四则运算表达式求解

    四则运算表达式应该是栈的一个最常见的应用了。对于一个四则运算表达式“9+(3-1)×3+10÷2”,要计算其值,首先应该把这个中缀表达式转换为后缀表达式,然后再对后缀表达式进行求解。

    ①中缀表达式转后缀表达式

    有关什么是中缀表达式,什么是后缀表达式我这里就不赘述了,大家自行百度。中缀表达式转后缀表达式的规则为:

    • 1)读取到数字,直接输出
    • 2)当读取到左括号"("时,直接压栈,当读取到运算符时,分两种情况讨论
      a.当运算符栈为空或者栈顶操作符的优先级小于当前运算符优先级时(如+和-的优先级低于 * 和 /),直接入栈
      b.当运算符不为空时且栈顶操作符的优先级大于或等于当前运算符优先级时,循环执行出栈操作并输出,直到遇到优先级小于当前运算符的元素为止。循环执行完后再将当前运算符压栈。另外需要注意的是,只有遇到右括号时,左括号才出栈
    • 3)当遇到右括号")"时,循环执行出栈操作并加入到list中,直到遇到左括号为止。并将左括号弹出,但不加入list中
    • 4)表达式的值读取完后,将操作符栈中的所有元素弹出并输出

    如“9+(3-1)×3+10÷2”,先输出9;加号进栈;左括号进栈;输出3;减号进栈;输出1;遇到右括号,一直输出栈顶元素直到遇到左括号,所以减号和左括号输出;×进栈;输出3;遇到加号,×和-出栈,+入栈;输出10;÷入栈;输出2;栈中元素全部出栈,得到最后结果:9 3 1 - 3 × + 10 2 ÷ +。

    ②后缀表达式的计算

    后缀表达式也会用到栈,其具体规则为:从左到右遍历后缀表达式的每个数字和符号,遇到数字就进栈,遇到符号,就将处于栈顶的两个数字出栈,进行运算,并将运算结果进栈,一直到最终获得结果
    下面仍然用Java来实现中缀表达式转后缀表达式以及后缀表达式的求解(因为我这里每个例子都是用内部类定义的,所以class前面都有public和static关键字),C++的过程和此类似,我这里就不写了。

    • Java
    public static class CalculateMathExpression{//四则运算表达式求解
    
            /**
             * 将输入的中缀表达式转换成后缀表达式
             * @param inString 中缀表达式的字符串
             * @return 分离得到的后缀表达式
             */
            public static List<String> inTransPost(String inString) throws Exception {
                ArrayList<String> result=new ArrayList<>();
                LinkStack<String> stack=new LinkStack<>();
                for (int i=0;i<inString.length();i++){
                    char item=inString.charAt(i);
                    if ((item>='0'&&item<='9')||item=='.'){//如果是数字加入到输出队列
                        //此处进行两位数的处理
                        String tmp=String.valueOf(item);
                        int j=i+1;
                        while (j<inString.length()){
                            char item2=inString.charAt(j);
                            if ((item2>='0'&&item2<='9')||item2=='.')
                            {
                                tmp+=String.valueOf(item2);
                                j++;
                            }
                            else
                                break;
                        }
                        result.add(tmp);
                        if (j!=i+1)//数字是一位数
                            i=j-1;
                        continue;
                    }
                    else if (item=='(')
                    {
                        stack.pushBack(String.valueOf('('));
                        continue;
                    }
                    else if (item=='+'||item=='-'){
                        while (!stack.isEmpty()&&!stack.peek().equals("("))
                            result.add(stack.pop());
                        stack.pushBack(String.valueOf(item));
                        continue;
                    }
                    else if (item=='*'||item=='/'){
                        while (!stack.isEmpty()&&(stack.peek().equals("*")||stack.peek().equals("/")))
                            result.add(stack.pop());
                        stack.pushBack(String.valueOf(item));
                        continue;
                    }
                    else if (item==')'){
                        while (!stack.isEmpty()&&!stack.peek().equals("("))
                            result.add(stack.pop());
                        stack.pop();
                        continue;
                    }else
                        throw new Exception("遇到未知操作符");
                }
                while (!stack.isEmpty())
                    result.add(stack.pop());
                return result;
            }
    
            /**
             * 计算中缀表达式的值
             * @param inString
             * @return
             */
            public static float calcExpressionValue(String inString){
                List<String> postStr=null;
                try {
                    postStr=inTransPost(inString);
                }catch (Exception e){
                    System.out.println("输入数据中有未知字符!");
                    return Float.NaN;
                }
                if (postStr!=null){
                    String outStr="输入的中缀表达式转换成后缀表达式为:";
                    LinkStack<Float> stack=new LinkStack<>();
                    for (String str:postStr)
                    {
                        outStr+=str+" ";
                        try {
                            if (str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){//如果遇到操作符,则弹出两个操作数,将计算结果压栈
                                Float val2=stack.pop();
                                Float val1=stack.pop();
                                float result=operate(val1,val2,str);
                                stack.pushBack(result);
    
                            }else {//如果遇到数字直接压栈
                                Float val=Float.valueOf(str);
                                stack.pushBack(val);
                            }
                        }
                        catch (NumberFormatException e){//捕获字符串转数字时出现异常
                            System.out.println("字符串转换成数字出错!");
                            return Float.NaN;
                        }
                    }
                    System.out.println(outStr);
                    return stack.pop();
                }
                return Float.NaN;
            }
    
            /**
             * 根据操作符计算两个数的值
             * @param val1 第一个操作数
             * @param val2 第二个操作数
             * @param operator 操作符,+ - * /中的一个
             * @return
             */
            private static float operate(Float val1,Float val2,String operator){
                if (operator.equals("+"))
                    return val1+val2;
                else if (operator.equals("-"))
                    return val1-val2;
                else if (operator.equals("*"))
                    return val1*val2;
                else
                    return (float) (val1*1.0/val2);
            }
        }
    123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121
    

    上面的例子支持多位数的加减运算,且支持小数。其中,用到的LinkStack类就是本文章上面实现的链式栈。使用示例:

    System.out.println(CalculateMathExpression.calcExpressionValue("10.2+((2+3)*4)-5"));
    1
    

    输出结果为:

    输入的中缀表达式转换成后缀表达式为:10.2 2 3 + 4 * + 5 - 
    25.2
    12
    

    3.2 队列

    3.2.1 队列的定义

    队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。

    3.2.2 队列的实现

    同理,队列的实现方式也有顺序表和链表两种方式。

    • 顺序表:用顺序表实现队列,就是用一个数组和一个指针来实现。每次入队的时插入到数组尾,出队的时将数组第一个元素移除,然后后面的元素整体后移。但是这样效率很低,为了提高效率,可以设置两个指针,一个指针front指向队头,一个指针rear指向队尾,这样队头就不一定在数组下标为0的位置了。使用此种方式时,应该解决假溢出的问题。解决假溢出的方式是使用循环队列,即当队尾满了时,插入到队头。
      循环队列当队空和队满时,都是front和rear相等,为了解决此问题,当队满时,我们留一个元素。如下所示:
      循环队列
      此时,
      队满的条件为
      (rear+1)%QueueSize==front
      计算队长的公式为
      (rear-front+QueueSize)%QueueSize
    • 链式结构
      队列的链式存储结构,就是在链表的基础上,限制数据的插入和弹出:将链表头部当成队首,尾部当成队尾。因为经常需要在队尾进行入队操作,为了减少链表的遍历次数,提高性能,此处我们的队列的Java代码实现基于双向循环链表实现,而C++结构则基于单链表实现(C++的双向循环链表太懒了没实现,只能用单链表了hhh)。有关双向循环链表的实现,见上一篇博客。具体实现如下:
    • Java实现
    public class LinkQueue<T> extends DoublyLinkedList<T> {
        /**
         * 入队操作
         * @param data
         */
        public void enQueue(T data){
            insert(this.length,data);
        }
    
        /**
         * 出队操作
         * @return
         */
        public T deQueue(){
            if (!isEmpty())
                return remove(0);
            return null;
        }
    
        /**
         * 判断队列是否为空
         * @return 空返回true,非空返回false
         */
        public boolean isEmpty(){
            return this.length==0;
        }
    }
    123456789101112131415161718192021222324252627
    

    其中,DoublyLinkedList双向循环链表的实现见上一篇博客。使用示例如下:

    		LinkQueue<String> queue=new LinkQueue<>();
            queue.enQueue("0");
            queue.enQueue("1");
            queue.enQueue("2");
            System.out.println(queue);
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
    12345678
    

    输出结果为:

    0,1,2,
    0
    1
    2
    1234
    
    • C++实现
    template<class T>
    class LinkQueue:LinkList<T>
    {
    public:
    	/**
    	 * 入队操作
    	 */
    	void enQueue(T data)
    	{
    		insert(length, data);
    	}
    
    	/**
    	 * 出队操作
    	 */
    	T deQueue()
    	{
    		if (!isEmpty())
    		{
    			return this->remove(0);
    		}
    		return NULL;
    	}
    
    	bool isEmpty()
    	{
    		return this->length == 0;
    	}
    };
    1234567891011121314151617181920212223242526272829
    

    同理,LinkList的定义见上一篇博客。此处因为使用的是单链表,频繁出队入队的话,效率应该不是很高。使用示例如下:

    	LinkQueue<string> queue;
    	queue.enQueue("0");
    	queue.enQueue("1");
    	queue.enQueue("2");
    	cout << queue.deQueue() << endl;
    	cout << queue.deQueue() << endl;
    	cout << queue.deQueue() << endl;
    1234567
    

    输出结果为:

    0
    1
    2
    123
    

    3.2.2 队列的应用

    队列也有很多应用,比如各种排队系统,特别是在网络请求的时候,当有多个请求任务时,不能一下子全部请求,需要排队请求。还有就是树的层次遍历中会用到队列,这个等写到树的时候再详细介绍。

    3. 3 应用

    3.3.1 表达式

    表达式一般分为前缀表达式,中缀表达式和后缀表达式。

    其中我们最为熟悉的是中缀表达式,也就是书本上最常用的表示形式。中缀表达式是将运算符放在两个操作数的中间。

    语言表示1–中缀转后缀

    1.从左到右进行遍历
    2.运算数,直接输出.
    3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈)
    4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出)
    5.运算符,将该运算符与栈顶运算符进行比较,
    如果优先级高于栈顶运算符则压入堆栈(该部分运算还不能进行),
    如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出,然后比较新的栈顶运算符.
    (低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算)
    直到优先级大于栈顶运算符或者栈空,再将该运算符入栈.
    6.如果对象处理完毕,则按顺序弹出并输出栈中所有运算符.

    语言表述2–中缀转后缀

    如何将中缀转后缀思路: 假如表达式是一个字符串

    创建一个符号栈和一个字符串队列

    遍历各个字符信息

    判断该字符是 运算符、括号、数值

    • 运算符

      判断当前字符优先级是否小于等于栈顶字符优先级,此时栈顶元素中的左括号(,优先级最小

      • 小于等于 将符号栈栈顶内容弹出且存入到字符串队列中,将当前字符存入到符号栈中
      • 大于将当前字符存入到符号栈中
    • 括号

      • 左括号存入到符号栈中
      • 右括号 依次将符号栈中的运算符弹出进入到字符串队列中直到在符号栈中弹出出现左括号停止弹栈 数值 直接进入到字符串队列中
    • 数值

      直接输出

    遍历结束后 判断符号栈中是否有元素

    优先级

    运算符 (左括号 +加,-减 *乘,/除,%取模 ^幂
    优先级 0 1 2 3

    代码–中缀转后缀

    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <set>
    #include <stack>
    #include <string>
    #include <vector>
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    using namespace std;
    #define MAX 1000
    char *change(char data[]);
    bool compare(char a, char b);
    int priority(char a);
    // (40  括号在算术上优先级最高,但是在 栈的优先级是最低的,为了其他符号正常入栈 优先级最低
    //  /* 优先级最高 , +- 优先级最低
    
    // true 的情况 只有a 是*/ b是+-的情况
    int priority(char a)
    {
        if (a == '(')
        {
            return  0;
        }
        else if (a == '+' || a == '-')
        {
            return  1;
        }
        else
        {
            return  2;
        }
    }
    // 比较优先级 ,a 的优先级比b 高,就返回true
    bool compare(char a, char b)
    {
        return  priority(a) > priority(b);
    }
    // 中缀表达式--> 后缀表达式(逆波兰表达式)
    // 返回字符串数组
    char *change(char data[])
    {
    
        char *hou = (char *)malloc(MAX * sizeof(char));
        stack<char> s;
        int index = 0; // 后缀表达式的长度
        int length = strlen(data);
        // 1. 判断类型
        for (int i = 0; i < length; i++)
        {
            // 如果是运算数,直接输出,
            if (data[i] >= '0' && data[i] <= '9')
            {
                hou[index] = data[i];
                index++;
            }
            else if (data[i] == ')')
            {
                // 不断的弹出栈元素并输出直到遇到左括号结束
                while (!s.empty() && s.top() != '(')
                {
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.pop(); //退出左括号
            }else if(data[i]=='('){
                 s.push(data[i]);
            }
            else
            {
                // 表示 运算符优先级小于等于 栈顶元素,就退出栈顶元素,并输出
                // 包含情况data[i]='(',compare 返回false
                
                while (!s.empty() && !compare(data[i], s.top()))
                {
                    printf("%c %c %d\n",data[i],s.top(),compare(data[i], s.top()));
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.push(data[i]);
            }
            printf("此时输出内容 %-20s \t参加运算的符号 %c  \t\t栈的元素个数%d \n", hou, data[i], s.size());
        }
    
        // 输出栈内所有元素
        while (!s.empty())
        {
            hou[index] = s.top();
            index++;
            s.pop();
        }
        return  hou;
    }
    
    // 后缀表达式的计算
    int main(int argc, char const *argv[])
    {
        // 样例 2*(9+6/3-5)+4
        // 结果 2963/+5-*4+
        char s[MAX] = "2*2*2*2+2";
        char *result;
        result = change(s);
        printf("%s\n", result);
        return  0;
    }
    
    

    展开全文
  • 栈和队列的常见面试题-栈实现队列-队列实现栈 1) 用栈结构实现队列结构2) 如何用队列结构实现栈结构 ) 1) 用栈结构实现队列结构 解析: 用两个栈:push栈,pop栈 push栈:存储数据 pop  栈:只要本栈数据不为...

    栈和队列的常见面试题-栈实现队列-队列实现栈


    )

    1) 用栈结构实现队列结构

    解析:
    用两个栈:push栈,pop栈
    push栈:存储数据
    pop  栈:只要本栈数据不为空,便将push栈数据倒出致此,实现队列

    public static class TwoStacksQueue {
    		public Stack<Integer> stackPush;
    		public Stack<Integer> stackPop;
    
    		public TwoStacksQueue() {
    			stackPush = new Stack<Integer>();
    			stackPop = new Stack<Integer>();
    		}
    
    		// push栈向pop栈倒入数据
    		private void pushToPop() {
    			if (stackPop.empty()) {
    				while (!stackPush.empty()) {
    					stackPop.push(stackPush.pop());
    				}
    			}
    		}
    
    		/*add & push
    		共同点:
    		  add,push都可以向stack中添加元素。
    		不同点:
    		  add是继承自Vector的方法,且返回值类型是boolean。
    		  push是Stack自身的方法,返回值类型是参数类类型。*/
    		public void add(int pushInt) {
    			stackPush.push(pushInt);
    			pushToPop();
    		}
    
    		//返回栈顶元素,并且将该元素出栈。
    		public int pop() {
    			if (stackPop.empty() && stackPush.empty()) {
    				throw new RuntimeException("Queue is empty!");
    			}
    			pushToPop();
    			return stackPop.pop();
    		}
    
    		//返回栈顶元素,但不弹出该元素。
    		public int peek() {
    			if (stackPop.empty() && stackPush.empty()) {
    				throw new RuntimeException("Queue is empty!");
    			}
    			pushToPop();
    			return stackPop.peek();
    		}
    	}
    

    2) 如何用队列结构实现栈结构

    解析:
    用两个栈:push栈,pop栈
    push,help两栈相互倒元素(只剩一个元素),实现栈功能

        public static class TwoQueueStack<T> {
            public Queue<T> queue;
            public Queue<T> help;
    
            public TwoQueueStack() {
                queue = new LinkedList<>();
                help = new LinkedList<>();
            }
    
            public void push(T value) {
                queue.offer(value);// add()和offer()
            }
    
            //返回元素,并弹出该元素
            public T poll() {
                while (queue.size() > 1) {
                    help.offer(queue.poll());// poll()和remove()拿出来
                }
                T ans = queue.poll();
                Queue<T> tmp = queue;
                queue = help;
                help = tmp;
                return ans;
            }
            //返回元素,但不弹出
            public T peek() {
                while (queue.size() > 1) {
                    help.offer(queue.poll());
                }
                T ans = queue.poll();
                help.offer(ans);
                Queue<T> tmp = queue;
                queue = help;
                help = tmp;
                return ans;
            }
    
            public boolean isEmpty() {
                return queue.isEmpty();
            }
    
        }
    

    3. 扩展

    前言:
    图的 宽度优先遍历一般使用队列实现 深度优先遍历一般使用栈实现
    若用栈怎么实现图的宽度优先遍历?
    若用队列怎么实现图的深度优先遍历?
    答案显而易见的

    展开全文
  • 3.1 栈和队列的定义和特点1 1、普通线性表的插入和删除操作 2、栈和队列的定义和特点 栈和队列是两种常用的、重要的数据结构。 栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 栈和队列是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,246
精华内容 14,898
关键字:

栈和队列