精华内容
下载资源
问答
  • 主要介绍了java 数据结构栈和队列的实例详解的相关资料,主要使用数组与线性表的方法来实现,需要的朋友可以参考下
  • 主要介绍了java 数据结构队列的相关资料,这里对java中的栈和队列都做出实现实例来帮助大家理解学习数据结构,需要的朋友可以参考下
  • 进行数据插入删除操作的一端称为栈顶,另一端称为底。 原则:后进先出LIFO(Last In First Out) 压栈:的插入操作,入数据在栈顶 出栈:的删除操作,出数据也在栈顶 的实现 一头进出 一般可以使用...

    相关概念

    • 栈是一种特殊的线性表
    • 只允许在固定的一端进行插入和删除元素操作。
    • 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
    • 原则:后进先出LIFO(Last In First Out)
    • 压栈:栈的插入操作,入数据在栈顶
    • 出栈:栈的删除操作,出数据也在栈顶

    在这里插入图片描述
    在这里插入图片描述
    栈的实现

    • 一头进出
    • 栈一般可以使用数组或链表实现,数组结构更优
    class Stack{
        int[] array;
        int top;
    }
    
    //顺序表实现栈
    Stack(){
        this.array = new int[100];
        this.top = top;
    }
    
    /**
     * 压入一个数据,插入一个数据
     * 压栈
     * @param v
     */
     public void push(int v){
         this.array [this.top++] = v;
     }
    
    /**
     * 弹栈,出栈
     * 先进后出
     * @return 栈顶元素
     */
    public int pop() {
        return this.array[--this.top];
    }
    
    /**
     * 查看栈顶元素
     * @return 栈顶元素
     */
    public int peek() {
        return this.array[this.top - 1];
    }
    
    /**
     * 返回栈的元素个数
     * @return 栈顶元素
     */
    public int size() {
        return this.top;
    }
    
    /**
     * 判断栈空
     * @return
     */
    public boolean isEmpty() {
        return this.top == 0;
    }
    

    队列

    相关概念

    • 队列只允许队尾插入数据,队头删除数据
    • 队列具有先进先出FIFO(First In First One)原则
      在这里插入图片描述

    队列的实现

    • 一头进另一头出
    • 队列可利用数组或链表结构实现,链表结构更优
      在这里插入图片描述
    class Node{
        int value;
        int next;
    }
    
    Node head;
    Node last;
    
    Queue(){
        this.head = this.last = null;
    }
    
    /**
     * 将数据插到队尾
     * @param v
     */
    public void push(int v){
        Node node= new Node();
        node.val = v;
        node.next = null;
        if(this.head == null){
            this.head = this.last = node;
        } else {
            this.last.next = this.last = node;
        }
    }
    
    /**
     * 将数据从队头删除
     * @return v = this.head.val
     */
    public int pop() {
        int v = this.head.val;
        this.head = this.head.next;
        if (this.head == null) {
            this.last = null;
        }
        return v;
    }
    
    /**
     * 返回队首元素
     * @return
     */
    public int front() {
        return this.head.val;
    }
    

    在这里简单介绍一下循环队列

    • 循环队列其操作表现基于FIFO(先进先出)原则并且队尾被链接在队首之后形成一个循环,也被称作“环形缓冲器”
    • 循环队列的好处在于我们可以利用这个队列之前用过的空间,在一个普通队列里,一旦一个队列满了就不能再插入下一个元素了,即使这个队列前面还有空间。但是使用循环队列,我们能使用这些空间取存储新的值
      在这里插入图片描述
      在这里插入图片描述

    循环队列的实现

    1. 定义size
    • front指向一个进队列的第一个元素,rear指向队尾元素的下一个可用空间
    • 当size = 0,front和rear指向同一个地方,代表此时队列为null
    • 当size != 0时,front和rear指向同一个地方,代表此时队列为full
    1. 当rear指向的下一个可用空间的下一个空间为队首元素
      -如图,当队列仅剩下一个可用空间(图中rear所指处)的时候,就不再允许元素进队列,以此判空rear
      在这里插入图片描述
    展开全文
  • 主要介绍了Java模拟栈和队列数据结构的基本示例,的后进先出和队列的先进先出是数据结构中最基础的知识,本文则又对Java实现栈和队列结构的方法进行了细分,需要的朋友可以参考下
  • 算法与数据结构JAVA语言描述 模块3 栈和队列 模块3 栈和队列 学习目的与要求 重点 栈和队列的特点 栈和队列的进出运算 循环队列的特点及基本运算 难点 栈和队列的相关运算 使用栈和队列解决实际应用问题 模块3 栈和...
  • 算法与数据结构JAVA语言描述 模块3 栈和队列 ;学习目的与要求;模块3 栈和队列;3.2.1 的概念及基本运算;3.2.1 的概念及基本运算;3.2.1 的概念及基本运算;3.2.1 的概念及基本运算;3.2.2 的顺序存储结构及其...
  • 数据结构-栈和队列

    万次阅读 多人点赞 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正常工作。
     

    展开全文
  • 今天的是一些数据结构栈和队列的基本操作,算是作为用java描述数据结构的一个开始。之前学的都是用c语言描述,现在因为开始准备java方向的一些事情,所以打算开始过一遍java数据结构 的特点是,里面的...

    今天的是一些数据结构中栈和队列的基本操作,算是作为用java描述数据结构的一个开始。

    之前学的都是用c语言描述,现在因为开始准备java方向的一些事情,所以打算开始过一遍java的数据结构。

       栈的特点是,栈里面的元素是先进后出的形式。比如把1,2,3依次放进一个栈里面,取出之后的顺序就变成了3,2,1。栈在java里是用数组的形式表现,相当于是吧一个一个的数存进数组里,然后设置一个top表示当前最高位,采用arr[top]的形式读入和取出栈顶元素。下面看代码的实现:

        MyStack类:
    public class MyStack {
    	//数组实现
    	private long arr[];
    	private int top;
    	
    	//默认
    	public MyStack() {
    		arr = new long[10];
    		top = -1;
    	}
    	
    	//带参构造方法
    	public MyStack(int maxsize) {
    		arr = new long[maxsize];
    		top = -1;
    	}
    	
    	//加入数据
    	public void push(int data) {
    		arr[++top] = data;
    	}
    	
    	//pop移除数据
    	public long pop() {
    		return arr[top--];
    	}
    	
    	//查看数据
    	public long LookTopData() {
    		return arr[top];
    	}
    	
    	//判断是否为空
    	public boolean isEmpty() {
    		return top == -1;
    	}
    	
    	//判断是否满
    	public boolean isFull() {
    		return top == arr.length - 1;
    	}
    }
    

    测试程序:(省略了public static void main等框架)
    //测试栈
    MyStack a = new MyStack(4);
    a.push(23);
    a.push(12);
    a.push(1);
    a.push(90);
    System.out.println(a.isEmpty());
    System.out.println(a.isFull());
    System.out.println(a.LookTopData());
    while(!a.isEmpty()) {
    	System.out.println(a.pop()+" ");
    }
    

    队列

       队列的特点是,队列里面的元素是先进先出的形式。比如把1,2,3依次放进一个队列里面,取出之后的顺序就仍然是1,2,3。队列在java里也是用数组的形式表现,相当于是吧一个一个的数存进数组里,然后设置一个队头和队尾,采用数组循环存放的形式实现队列。下面看代码的实现:

    MyQueue类:
    public class MyQueue {
    	//底层使用数组
    	private long[] arr;
    	//大小
    	private int elements;
    	//队头
    	private int front;
    	//队尾
    	private int end;
    	
    	//默认构造方法
    	public MyQueue() {
    		arr = new long[10];
    		elements = 0;
    		front = 0;
    		end = -1;
    	}
    	
    	//带参数构造方法,参数为数组大小
    	public MyQueue(int maxsize) {
    		arr = new long[maxsize];
    		elements = 0;
    		front = 0;
    		end = -1;
    	}
    	
    	//添加数据
    	public void insert(long data) {
    		if(end == arr.length - 1 ) {
    			end = -1;
    		}
    		arr[++end] = data;
    		elements++;
    	}
    	
    	//删除数据,从队头删除
    	public long remove() {
    		long data = arr[front++];
    		if(front == arr.length) {
    			front = 0;
    		}
    		elements--;
    		return data;
    	}
    	
    	//查看数据,队头
    	public long Look() {
    		return arr[front];
    	}
    	
    	//判断是否为空
    	public boolean isEmpty() {
    		return elements == 0;
    	}
    	
    	//判满
    	public boolean isFull() {
    		return elements == arr.length;
    	}
    	
    }
    

    测试程序:(省略了public static void main等框架)

    MyQueue mq = new MyQueue(4);
    mq.insert(23);
    mq.insert(45);
    mq.insert(13);
    mq.insert(1);
    		
    System.out.println(mq.isEmpty());
    System.out.println(mq.isFull());
    		
    System.out.println(mq.Look());
    		
    while(!mq.isEmpty()) {
    	System.out.print(mq.remove() + " ");
    }
    展开全文
  • Java 数据结构和算法 栈和队列

    千次阅读 2017-04-29 11:55:43
    栈栈是一种抽象的数据结构只允许访问一个数据项,即最后插入的数据项,移除这个数据项之后才能访问倒数第二个数据,后进先出的原则。 class StackX { private int maxSize; // 的大小 private long[] ...

    栈是一种抽象的数据结构,栈只允许访问一个数据项,即最后插入的数据项,移除这个数据项之后才能访问倒数第二个数据,后进先出的原则。

    
    class StackX
       {
       private int maxSize;        // 栈的大小
       private long[] stackArray;
       private int top;            // 栈顶
    //--------------------------------------------------------------
       public StackX(int s)         
          {
          maxSize = s;             // 设置栈的大小
          stackArray = new long[maxSize];  // 创建一个数组
          top = -1;                // 没有元素的时候  置为-1
          }
    //--------------------------------------------------------------
       public void push(long j)    // 加入元素
          {
          stackArray[++top] = j;     
          }
    //--------------------------------------------------------------
       public long pop()           // 取出栈顶元素
          {
          return stackArray[top--];  
          }
    //--------------------------------------------------------------
       public long peek()          
          {
          return stackArray[top];
          }
    //--------------------------------------------------------------
       public boolean isEmpty()    // 判断栈是否为空
          {
          return (top == -1);
          }
    //--------------------------------------------------------------
       public boolean isFull()     // 判断栈是否已满
          {
          return (top == maxSize-1);
          }
    //--------------------------------------------------------------
       }  
    
    public class StackApp
       {
       public static void main(String[] args)
          {
          StackX theStack = new StackX(10);  //创建一个栈
          theStack.push(20);               // 装入元素
          theStack.push(40);
          theStack.push(60);
          theStack.push(80);
    
          while( !theStack.isEmpty() )     
             {                            
             long value = theStack.pop();
             System.out.print(value);      
             System.out.print(" ");
             }  // end while
          System.out.println("");
          }  
       }  
    
    

    栈的应用实例

    单词逆序:
    输入一个单词,输出字母顺序倒置后的词。

    import java.io.*;
    import java.util.Scanner;
    
    class StackX {
        private int maxSize;
        private char[] stackArray;
        private int top;
    
    
        public StackX(int max) {
            maxSize = max;
            stackArray = new char[maxSize];
            top = -1;
        }
    
        public void push(char j) {
            stackArray[++top] = j;
        }
    
    
        public char pop() {
            return stackArray[top--];
        }
    
    
        public char peek() {
            return stackArray[top];
        }
    
    
        public boolean isEmpty() {
            return (top == -1);
        }
    }
    
    public  class ReverseApp {
        public static void main(String[] args) {
            System.out.println(doRev(getString()));
        }
    
        public static String getString() {
            Scanner scan = new Scanner(System.in);
            return scan.nextLine();
        }
    
        public static String doRev(String str) {
            StackX theStack = new StackX(str.length());
    
            for (int j = 0; j < str.length(); j++) {
                char ch = str.charAt(j); // get a char from input
                theStack.push(ch); // push it
            }
    
            String result = "";
            while (!theStack.isEmpty()) {
                char ch = theStack.pop();
                result += String.valueOf(ch);
            }
            return result;
        }
    
    }
    

    应用:匹配括号

    栈常用来解析某种类型的文本串,比如解析一串字符中括号是否匹配,{ } () [ ] ,基本方法就是 遇见左括号时压入栈,遇见右括号时取出栈顶元素检查是否匹配,以此类推,如果所有匹配,则匹配成功,否则匹配失败。

    
    import java.util.Scanner;
    
    class StackX {
        private int maxSize;
        private char[] stackArray;
        private int top;
    
    
        public StackX(int s) {
            maxSize = s;
            stackArray = new char[maxSize];
            top = -1;
        }
    
        public void push(char j) 
        {
            stackArray[++top] = j;
        }
    
        public char pop() //取出栈顶元素
        {
            return stackArray[top--];
        }
    
        public char peek() //得到栈顶元素   栈并没有改变
        {
            return stackArray[top];
        }
    
        public boolean isEmpty() 
        {
            return (top == -1);
        }
    }
    
    public class BracketsApp {
        public static void main(String[] args) {
            check(getString());
    
        }
    
        public static String getString() {
            Scanner scan = new Scanner(System.in);
            return scan.nextLine();
        }
    
        public static void check(String str) {
            int stackSize = str.length(); 
            StackX theStack = new StackX(stackSize);
    
            for (int j = 0; j < str.length(); j++) 
            {
                char ch = str.charAt(j); 
                switch (ch) {
                case '{': 
                case '[':
                case '(':
                    theStack.push(ch); 
                    break;
    
                case '}': 
                case ']':
                case ')':
                    if (!theStack.isEmpty()) 
                    {
                        char chx = theStack.pop(); 
                        if ((ch == '}' && chx != '{') || (ch == ']' && chx != '[') || (ch == ')' && chx != '('))
                            System.out.println("Error: " + ch + " at " + j);
                    } else 
                        System.out.println("Error: " + ch + " at " + j);
                    break;
                default: 
                    break;
                } 
            } 
    
            if (!theStack.isEmpty())
                System.out.println("匹配失败");
        } 
    }
    

    这里写图片描述


    队列

    队列也是一种数据结构,有点类似栈,但是在队列中类似于排队,先来的先服务,也可以想象成管道,即先进先出。
    代码展示:

    class Queue {
        private int maxSize;
        private long[] queArray;
        private int front;
        private int rear;
        private int nItems;
    
        public Queue(int s) {
            maxSize = s;
            queArray = new long[maxSize];
            front = 0;// 队头标志
            rear = -1;// 队尾标志
            nItems = 0;// 队列中元素个数
        }
    
        public void insert(long j) {
            if (rear == maxSize - 1)
                rear = -1;
            queArray[++rear] = j;
            nItems++;
        }
    
        public long remove() {
            long temp = queArray[front++];
            if (front == maxSize)
                front = 0;
            nItems--;
            return temp;
        }
    
        public long peekFront() {
            return queArray[front];
        }
    
        public boolean isEmpty() {
            return (nItems == 0);
        }
    
        public boolean isFull() {
            return (nItems == maxSize);
        }
    
        public int size() {
            return nItems;
        }
    
    }
    
    public class QueueApp {
        public static void main(String[] args) {
            Queue theQueue = new Queue(5);
    
            theQueue.insert(10);
            theQueue.insert(20);
            theQueue.insert(30);
            theQueue.insert(40);
    
            theQueue.remove();
            theQueue.remove();
            theQueue.remove();
    
            theQueue.insert(50);
            theQueue.insert(60);
            theQueue.insert(70);
            theQueue.insert(80);
    
            while (!theQueue.isEmpty()) {
                long n = theQueue.remove(); // (40, 50, 60, 70, 80)
                System.out.print(n);
                System.out.print(" ");
            }
            System.out.println("");
        }
    }
    
    • 双端队列
      双端队列就是两端都是结尾的队列,队列的每一端都可以插入或者移除数据

    优先级队列

    优先级队列是比栈和队列更专用的数据结构,像普通队列一样,它也有一个一个对头和一个队尾,并且也是从队头移除数据项,不过在优先级队列中,数据按关键字的值有序,数据插入的时候会按照顺序插入到合适的位置以保证队列有序。

    class PriorityQ {
        // array in sorted order, from max at 0 to min at size-1
        private int maxSize;
        private long[] queArray;
        private int nItems;
    
        public PriorityQ(int s) {
            maxSize = s;
            queArray = new long[maxSize];
            nItems = 0;
        }
    
        public void insert(long item) {
            int j;
    
            if (nItems == 0)
                queArray[nItems++] = item; // 队列为空 直接插入
            else {// 否则要排序
                for (j = nItems - 1; j >= 0; j--) {
                    if (item > queArray[j])
                        queArray[j + 1] = queArray[j];
                    else
                        break;
                }
                queArray[j + 1] = item;
                nItems++;
            }
        }
    
        public long remove() {
            return queArray[--nItems];
        }
    
        public long peekMin() {
            return queArray[nItems - 1];
        }
    
        public boolean isEmpty() {
            return (nItems == 0);
        }
    
        public boolean isFull() {
            return (nItems == maxSize);
        }
    
    }
    
    public class PriorityQApp {
        public static void main(String[] args) {
            PriorityQ thePQ = new PriorityQ(5);
            thePQ.insert(30);
            thePQ.insert(50);
            thePQ.insert(10);
            thePQ.insert(40);
            thePQ.insert(20);
    
            while (!thePQ.isEmpty()) {
                long item = thePQ.remove();
                System.out.print(item + " "); // 10, 20, 30, 40, 50
            }
            System.out.println("");
        }
    }
    

    优先级队列与队列在代码实现上不同之处主要在于插入的时候要排序。


    栈和队列暂时就写这么多,下一节实现栈和队列的综合应用。计算表达式。

    展开全文
  • 队列
  • 主要介绍了Java数据结构之链表、队列、树的实现方法,结合实例形式分析了Java数据结构中链表、队列、树的功能、定义及使用方法,需要的朋友可以参考下
  • Java数据结构与算法 - 栈和队列

    千次阅读 2017-07-27 13:31:27
    主要涉及三种数据存储类型:队列,优先级队列
  • 栈和队列是什么? 是概念!是逻辑结构!不是真是存在的!寄托载体不固定! 栈和队列的特征? :先进后出,队列:先进先出 int、double……是数据类型 ...一下是用java写出的栈和队列的代码示例: 1、定义数据节...
  • 优先级队列是比栈和队列更为专用的数据结构,它普通的队列一样有一个队尾一个队头,并且每一次移除数据项时,都从队头处移除,不同的地方在于,优先级队列是按照关键字有序排列的,比如在本文中,我们将优先级...
  • 数据结构Java实现——栈和队列

    千次阅读 2011-03-21 22:35:00
    的线性结构,只支持在栈顶的插入弹出。 队列(Queue)作为一个先进先出(FIFO) 的线性结构,支持在队首获取元素,在对尾插入元素。   的实现: <br />  package ds.linerlist; /*...
  • 算法与数据结构JAVA语言描述 模块3 栈和队列 ;模块3 栈和队列;学习目的与要求;模块3 栈和队列;3.1 实例引入;3.1 实例引入;模块3 栈和队列;3.2.1 的概念及基本运算;3.2.1 的概念及基本运算;3.2.1 的概念及基本...
  • 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 ...
  • JAVA数据结构——队列和栈

    千次阅读 2017-04-28 16:10:06
    队列和栈
  • 数据结构栈和队列

    千次阅读 2017-11-02 21:13:21
    title: 数据结构栈和队列 categories: 数据结构版权声明:本站采用开放的[知识共享署名-非商业性使用-相同方式共享 许可协议]进行许可所有文章出现的代码,将会出现在我的github中,名字可以根据类全名来找,我在...
  • Java实现数据结构栈stack和队列Queue

    千次阅读 2013-05-29 09:39:25
    Java实现数据结构栈stack和队列Queue Google后发现大多数文章都是通过LinkedList类实现,当然JDK有自带的Stack类   回顾JDK提供的集合类 容器(集合)框架如下:  集合类存放于java.util包中。集合类存放的都...
  • 栈和队列:  面试的时候,栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容:  (1)的创建  (2)队列的创建  (3)两个实现一个队列  (4)两个队列实现一个  (5)设计含最小函数min()...
  • Java数据结构与算法之栈和队列

    千次阅读 2014-06-09 10:18:56
    此类数据结构和算法更多是作为程序员的工具来运用。他们主要作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短得多。在程序操作执行期间它们才被创建,通常用...
  • 数据结构,一门数据处理的艺术,精巧的结构在一个又一个算法下发挥着他们无与伦比的高效精密之美,在为信息技术打下坚实地基的同时,也令无数开发者探索者为之着迷。 也因如此,它作为博主大二上学期最重要的...
  • 数据结构栈和队列

    2019-08-24 16:20:05
    数据结构栈和队列栈 Stack的应用的实现队列 Queue队列的实现数组队列与循环队列 Stack 是一种线性结构 相比数组,对应的操作是数组的子集 只能从一端添加元素,也只能从同一端取出元素(添加删除都在...
  • 无意中发现LinkedList 不仅仅实现了List接口,同时也实现了Queue接口,因此在这里就模拟一下数据结构和队列数据结构。为以后的面试做准备。/** * @author yikai * 类型的数据结构的特点就是先进后出,那么...
  • Web全栈~23.数据结构(栈和队列)

    千次阅读 多人点赞 2021-01-19 16:38:08
    Web全栈~23.数据结构(栈和队列) 上一期 相关博客 栈和队列的基本概念 顺序栈和链栈 顺序栈和链栈的应用 顺序队链队
  • 不含任何数据元素的称为空栈。又成为后进先出(LIFO)表,后进入的元素最先出来。 首先,是一个线性表,元素之间具有线性关系,即前驱后继关系,其次,它是一种特殊的线性表,只能在表尾进行插入删除操作。...
  • 数据结构――队列和树 开发者可以使用数组与链表的变体来建立更为复杂的数据结构。本节探究三种这样的数据结构:、队列与树。当给出算法时,出于简练,直接用Java代码。 是这样一个数据结构,其数据项...
  • ——先进后出 1.常用操作 初始化 压栈/弹 查看当前栈顶元素 判断为空 返回元素个数 2.实现 链表可以实现 LinkedList push/pop 头插/头删 顺序表可以实现 Strack(class) 尾插/尾删 自己实现 利用顺序表实现...
  • 数据是基础,算法是灵魂 版权声明,本文来自门心叼龙的博客,属于原创内容,转载请注明出处。... 源码下载地址:... 初级篇:Java数据结构与算法初级篇之数组、集合散列表 中级篇:Ja...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,484
精华内容 33,393
关键字:

java数据结构栈和队列

java 订阅
数据结构 订阅