- -, (insert) (delete) - - (insert) (delete) (top ) - - (insert) (rear) (delete) (front)
A A B top A B C top push(a) push(b) push(c) A B top pop() top A B D push(d) top
#define MAX_STACK_SIZE 100 int stack[max_stack_size]; int top = -1; /* top 1. */
void push(int item) { if(top >= MAX_STACK_SIZE - 1) { stack_full(); return; } stack[++top] = item; }
int pop( ) { if(top == -1) return stack_empty(); return stack[top--]; }
int isempty() { if( top < 0 ) return(1); else return(0); } int isfull() { if ( top >= MAX_STACK_SIZE 1 ) return(1); else return(0); }
#include <stdio.h> #define MAX_STACK_SIZE 100 int stack[max_stack_size]; int top = -1; void push(int item) { if(top >= MAX_STACK_SIZE - 1) { printf("stack_full()\n"); return; } stack[++top] = item; } int pop() { if(top == -1) { printf("stack_empty()\n"); exit(); } return stack[(top)--]; }
int isempty() { if( top == -1 ) return(1); else return(0); } int isfull() { if ( top >= MAX_STACK_SIZE -1 ) return(1); else return(0); } int main() { int e; push(20); push(40); push(60); printf(" Begin Stack Test...\n"); } while(!isempty()) { e = pop(); printf("value = %d\n", e); }
// Stack.java // to run this program: C>java StackApp import java.io.*; // for I/O //////////////////////////////////////////////////////////////// class StackX { private int maxsize; // size of stack array private double[] stackarray; private int top; // top of stack //-------------------------------------------------------------- public StackX(int s) // constructor { maxsize = s; // set array size stackarray = new double[maxsize]; // create array top = -1; // no items yet } //-------------------------------------------------------------- public void push(double j) // put item on top of stack { stackarray[++top] = j; // increment top, insert item } //-------------------------------------------------------------- public double pop() // take item from top of stack { return stackarray[top--]; // access item, decrement top } //-------------------------------------------------------------- public double peek() // peek at top of stack { return stackarray[top]; } //-------------------------------------------------------------- public boolean isempty() // true if stack is empty { return (top == -1); } //-------------------------------------------------------------- public boolean isfull() // true if stack is full { return (top == maxsize-1); } //-------------------------------------------------------------- } // end class StackX
//////////////////////////////////////////////////////////////// class StackApp { public static void main(string[] args) { StackX thestack = new StackX(10); // make new stack thestack.push(20); // push items onto stack thestack.push(40); thestack.push(60); thestack.push(80); while(!thestack.isempty() ) // until it's empty, { // delete item from stack double value = thestack.pop(); System.out.print(value); // display it System.out.print(" "); } // end while System.out.println(""); } // end main() } // end class StackApp
A front=rear A B front rear front A B C B C insert(a) insert(b) insert(c) rear delete(a) front rear B C D insert(d) front rear
#define MAX_QUEUE_SIZE 100 typedef struct { int key; /* other fields */ } element; element queue[max_queue_size]; int rear = -1; int front = -1;
void insert(int *rear, element item) { if(*rear == MAX_QUEUE_SIZE - 1) { queue_full(); /*? */ return; } queue[++*rear] = item; }
element delete(int *front, int rear) { if(*front == rear) return queue_empty(); /* return an error key */ return queue[++*front]; }
int isempty() { if( front == rear ) return(1); else return(0); } int isfull() { if ( rear == MAX_QUEUE_SIZE 1 ) return(1); else return(0); }
front rear Q[0] Q[1] Q[2] Q[3] -1-1 -1 0 J1 Job 1-1 1 J1 J2 Job 2-1 2 J1 J2 J3 Job 3 0 2 J2 J3 Job 1 1 2 J3 Job 2
4. (circular queue)
J2 J3 J1 front = 0 front = 0 rear = 0 rear = 3 3
[Full ] [Full ] J2 J3 J8 J9 J1 J4 J7 J5 J6 J5 front = 0 rear = 5 front = 4 rear = 3 Full
*rear = (*rear +1) % MAX_QUEUE_SIZE ; -delete front front = (front +1) % MAX_QUEUE_SIZE ;
- () front rear -1?
Review