C++用数组实现一个固定大小的栈/队列

   
   

     
     

      
      

     
     
     
     

      
      

       
       #include<iostream>
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #include<exception>
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       using 
       
       namespace 
       
       std;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #define NUM 5
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       //用数组结构实现大小固定的队列和栈
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       class ArrayIndexOutOfBoundsException:
       
       public exception
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       private:
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       const 
       
       char*ptr;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       public:
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	ArrayIndexOutOfBoundsException(
       
       const 
       
       char*ptr)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       this->ptr = ptr;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       virtual char const *what()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       cout<<
       
       this->ptr<<
       
       endl;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       return ptr;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       };
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       class MyStack
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       private:
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int *
       
       array;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int idx;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int N;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       public:
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	MyStack(
       
       int N);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	~MyStack();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       void push(int element);
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int pop();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int peek();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       void printStack();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       };
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       MyStack::MyStack(
       
       int N)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       this->N = N;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       array = 
       
       new 
       
       int[N];
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	idx=
       
       0;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       MyStack::~MyStack()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       delete[] 
       
       this->
       
       array;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       void MyStack::push(int element)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       if(idx == N)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       throw ArrayIndexOutOfBoundsException(
       
       "栈已满");
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       else
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       array[idx++] = element;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       int MyStack::pop()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       if(idx == 
       
       0)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       throw ArrayIndexOutOfBoundsException(
       
       "栈中无元素");
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       else
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       return 
       
       array[--idx];
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       int MyStack::peek()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       if(idx == 
       
       0)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       return 
       
       -1;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       else
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       return 
       
       array[idx
       
       -1];
       
       //注意这里是看栈顶元素，但并不把元素去除所以用idx-1而不用--idx；
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       void MyStack::printStack()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       for(
       
       int i=
       
       0;i<N;i++)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       cout<<
       
       array[i]<<
       
       " ";
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       cout<<
       
       endl;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       int main()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       MyStack stack1(NUM);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	stack1.push(
       
       1);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	stack1.push(
       
       2);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	stack1.push(
       
       3);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	stack1.push(
       
       4);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	stack1.push(
       
       15);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	stack1.printStack();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       for(
       
       int i=
       
       0;i<NUM;i++)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       cout<<
       
       "pop = "<<stack1.pop()<<
       
       endl;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       cout<<
       
       "peek = "<<stack1.peek()<<
       
       endl;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       cout<<
       
       endl;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	stack1.printStack();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       return 
       
       0;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     
   
   

栈的实现相对简单，队列复杂一点。

   
   

     
     

      
      

     
     
     
     

      
      

       
       #include<iostream>
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #include<exception>
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       using 
       
       namespace 
       
       std;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #define NUM 5
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       //用数组结构实现大小固定的队列和栈
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       class ArrayIndexOutOfBoundsException:
       
       public exception
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       private:
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       const 
       
       char*ptr;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       public:
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	ArrayIndexOutOfBoundsException(
       
       const 
       
       char*ptr)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       this->ptr = ptr;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       virtual char const *what()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       cout<<
       
       this->ptr<<
       
       endl;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       return ptr;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       };
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       class MyQuene
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       private:
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int *
       
       array;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int start;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int end;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int size;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int len;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       public:
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	MyQuene(
       
       int N);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	~MyQuene();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       void push(int);
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int poll();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int peek();
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       };
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       MyQuene::MyQuene(
       
       int N)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	size = 
       
       0;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	start =
       
       0;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	end = 
       
       0;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	len = N;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       array = 
       
       new 
       
       int[len];
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       MyQuene::~MyQuene()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       delete[] 
       
       array;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       void MyQuene::push(int element)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       if(end == len)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       throw 
       
       new ArrayIndexOutOfBoundsException(
       
       "The qunen is full");
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	size++;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       array[end] = element;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	end = end == len 
       
       -1 ? 
       
       0 : end+
       
       1;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       int MyQuene::poll()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       if(size == 
       
       0)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       throw 
       
       new ArrayIndexOutOfBoundsException(
       
       "The qunen is empty");
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	size--;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       int tmp = start;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	start = start == len
       
       -1 ? 
       
       0 : start +
       
       1;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       int MyQuene::peek()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       if(size == 
       
       0)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	{
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       cout<<
       
       "The qunen is empty"<<
       
       endl;
      
      
     
     

     
     

      
      

     
     
     
     

      
      
		
       
       return 
       
       -1;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	}
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       return 
       
       array[start];
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       int main()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       {
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       MyQuene myQ(NUM);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	myQ.push(
       
       1);
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	myQ.poll();
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       	myQ.peek();
      
      
     
     

     
     

      
      

     
     
     
     

      
      
	
       
       return 
       
       0;
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       }