stack and queue(3)

• 栈和队列是一种逻辑结构
• 都可以用数组 or 链表来实现(物理结构)

stack

• 先入后出(FILO)
• 入栈：push
• 出栈: pop
• c++中基本语法：

头文件:#include<stack>
定义一个stack: stack<int>s;
入栈: s.push(int 型);
出栈: s.pop()
栈的大小: s.size()
判断当前栈是否为空: s.empty()
获取栈顶元素: s.top();

入栈出栈只涉及一个元素，时间复杂度都是o(1)

queue

• 先进先出(FIFO)
• 队尾入队，对头出队
• 循环队列：头尾相接的顺序存储队列称为循环队列
  

1. 队列已满：(rear+1）% 数组的长度 = front
2. queue的长度：(rear-front+数组的长度)%数组的长度
3. 队尾指针的位置永远空出一位，队列最大容量比数组长度小1

用c++实现循环队列的入队出队操作

#include<iostream>
#include <stdlib.h>
using namespace std;//数组长度 
#define capacity 5//creat
int* queueCreat(int cap)
{
    int* myQueue = new int[cap];return myQueue;	
} //push
void pushQueue(int* queue, int &rear, int &front, int cap, int tmp)
{
    if((rear+1) % cap == front){
    cout<<"queue is full"<<endl;return; }//cout<<rear<<endl;queue[rear] = tmp;rear = (rear+1)	% cap;	
}//queueSize
int queueSize(int &rear, int &front, int cap)
{
    return (rear-front+cap)%cap;	
} //pop
void popQueue(int* queue, int &rear, int &front, int cap)
{
    if(rear == front){
    cout<<"queue is empty"<<endl;return;}front = (front+1) % cap;
}//打印
void output(int* queue,int &rear,int &front,int cap)
{
    for(int i=front;i!=rear;i=(i+1)%cap){
    cout<<queue[i]<<" ";}cout<<"queueSize:"<<queueSize(rear, front, cap)<<endl;	
} int main()
{
    int rear = 0;int front = 0;int* myQueue = queueCreat(capacity);for(int i = 0;i< capacity; i++){
    int ele = rand()%30;pushQueue(myQueue, rear, front, capacity, ele);		} 	output(myQueue,rear,front,capacity);popQueue(myQueue,rear,front,capacity);popQueue(myQueue,rear,front,capacity);output(myQueue,rear,front,capacity);pushQueue(myQueue, rear, front, capacity, rand()%30);output(myQueue,rear,front,capacity);popQueue(myQueue,rear,front,capacity);popQueue(myQueue,rear,front,capacity);popQueue(myQueue,rear,front,capacity);	popQueue(myQueue,rear,front,capacity);output(myQueue,rear,front,capacity);	pushQueue(myQueue, rear, front, capacity, rand()%30);output(myQueue,rear,front,capacity);return 0; } 

输出：
queue is full
11 17 4 10 queueSize:4
4 10 queueSize:2
4 10 4 queueSize:3
queue is empty
queueSize:0
18 queueSize:1

Process exited after 0.1961 seconds with return value 0
请按任意键继续. . .

双端队列

• 队头：可以入队合出队
• 队尾：可以入队和出队

优先队列

• 谁的优先级高谁先出队
• 底层是二叉堆（非线性结构）