数据结构java版第3章.ppt

第3章 栈与队列 3.1 栈和队列基本概念 3.2 栈的入栈与出栈 3.3 队列的入队与出队 3.4 栈与队列的应用 3.5 程序集锦 3.6 思考题 3.1 栈和队列基本概念 在算法（algorithms）中，栈（stack）与队列（queue）是常用到的数据结构。 栈是一个有序列表（order list），其插入（insert）和删除（delete）操作都在同一端，这一端通常称为栈顶（top）。 队列（queue）也属于线性列表，与栈不同的是加入和删除不在同一端，删除的那一端称为队头（front），而加入的一端称为队尾（rear）。 栈与队列 3.1 栈和队列基本概念 加入一个元素到栈的操作称为入栈（push），与之相反的是从栈中删除一个元素，称为出栈（pop）。栈是一种后进先出（Last In First Out，LIFO）线性表。 而队列具有先进先出（First In First Out， FIFO）的特性 。 3.2 栈的入栈与出栈 3.2.1 入栈 3.2.2 出栈 3.2.1 入栈 入栈Java程序片断 public static void push_f() { // 入栈函数 DataInputStream in = new DataInputStream(System.in); if(top = MAX-1) // 当栈已满，则显示错误 System.out.print(\n Stack is full !\n); else { top++; System.out.print(\n Please enter item to insert: ); 3.2.1 入栈 System.out.flush(); try { stack[top] = in.readLine(); } catch (IOException e) {} } } 3.2.2 出栈 出栈Java程序片断： public void pop_f( ) { // 出栈函数 if(top 0) // 当栈没有数据时，则显示错误 System.out.print(\n No item, stack is empty !\n); else { System.out.print(\n Item + stack[top] + deleted !\n); top--; } System.out.println(); } 3.3 队列的入队与出队 3.3.1 入队 3.3.2 出队 3.3.3 循环队列的入队 3.3.4 循环队列的出队 3.3.1 入队 入队是在队尾，其程序如下： public void enqueue_f( ) { // 入队函数 DataInputStream in = new DataInputStream(System.in); if(rear = MAX-1) // 当队列已满，则显示错误 System.out.println(\n Queue is full !\n); else { rear++; 3.3.1 入队 System.out.print(\n Please enter item to insert: ); System.out.flush(); try { q[rear] = in.readLine(); } catch (IOException e) {} System.out.println(); } } 3.3.2 出队 出队是在队头，其Java程序片断如下： public void dequeue_f() { // 删除函数 if(front rear) // 当队列中没有元素存在时，则显示错误 System.out.print(\n No item, queue is empty !\n); else { 3.3.2 出队 System.out.print(\n Item + q[front] + deleted !\n); front++; } System.out.println(); } 3.3.3 循环队列的入队 循环队列开始的时候，将front与rear的初值均设为MAX–1。其Java程序片断如下： public void enqueue_f() { //