栈和队列 - JUZI's blog

栈(stack)

仅限在表尾进行插入和删除操作的线性表
表尾端称为栈顶（top）
表头端称为栈底（bottom）
后进先出（last in first out）的线性表（简称LIFO结构）

入栈（Push）
出栈（Pop）
栈按存储结构可分为顺序栈和链式栈
非法状态：上溢（栈满时继续入栈）、下溢（栈空时继续出栈）

顺序栈

//定义
typedef struct
{
    int data[maxSize];	//存放栈中元素
    int top;	//栈顶指针
} SqStack;
//初始化栈
void initStack(SqStack &st)
{
    st.top = -1;	//top为-1时，栈为空
}
//判断栈是否为空
int isEmpty(SqStack st)
{
 	if(st.top == -1)
        return 1;
    else
        return 0;
}
//进栈
int push(SqStack &st, int x)
{
	if(st.top == maxSize-1)	//栈满，不能进栈
        return 0;
    ++(st.top);
    st.data[st.top] = x;
    return 1;
}
//出栈
int pop(SqStack &st, int &x)
{
    if(st.top == -1) //栈空，不能出栈
        return 0;
    x = st.data[st.top];	//取出栈顶元素
    --(st.top);
    return 1;
}

链栈

//链栈结点定义
typedef struct LNode
{
    int data;	//数据域
    struct LNode *next;	//指针域
} LNode;
//初始化
void initStack(LNode *&lst)
{
    lst = (LNode*)malloc(sizeof(LNode));	//制造一个头结点
    lst->next = NULL;
}
//进栈
void push(LNode *lst, int x)
{
    LNode *p;
    p = (LNode*)malloc(sizeof(LNode));	//为进栈元素申请结点空间
    p->next = NULL;	
    
    //头插法
    p->data = x;
    p->next = lst->next;
    lst->next = p;
}
//出栈
void pop(LNode *lst, int &x)
{
    LNode *p;
    if(lst->next = NULL)	//判断栈是否为空
        return 0;
    p = lst->next;
    x = p->data;
    lst->next = p->next;
    free(p);
    return 1;
}

共享栈

两个栈共享一片连续的存储空间，两个栈的栈底位于存储空间的两端，当两个栈的栈顶在栈空间的某处相遇时，产生上溢。

队列（queue）

先进先出（first In first out，FIFO）的线性表
队尾（rear）：允许插入元素的一端，队尾元素
队头（front）：允许删除元素的一端，队头元素
队列按存储结构可分为顺序队列和链队列

顺序队列

//定义
typedef struct
{
    int data[maxSize];
    int front;		//队首指针	
    int rear;		//队尾指针
}SqQueue;

链队列

//队列结点定义
typedef struct QNode
{
    int data;	//数据域
    struct QNode *next;	//指针域
}QNode;
//链队列类型定义
typedef struct
{
    QNode *front;	//队头指针
    QNode *rear;	//队尾指针
}LiQueue;
//初始化
void initQueue(LiQueue *&lqu)
{
    lqu=(LiQueue*)malloc(sizeof(LiQueue));
    lqu->front=lqu->rear=NULL;
}
//判断队空
int isQueueEmpty(LiQueue *lqu)
{
    if(lqu->rear==NULL||lqu->front==NULL)
        return 1;
    else
        return 0;
}
//入队
void enQueue(LiQueue *lqu,int x)
{
    QNode *p;
    p=(QNode*)malloc(sizeof(QNode));
    p->data=x;
    p->next=NULL;
    if(lqu->rear==NULL)	
        lqu->front=lqu->rear=p;
    else
    {
        lqu->rear->next=p;
        lqu->rear=p;
    }
}
int deQueue(LiQueue *lqu,int &x)
{
    QNode *p;
    if(lqu->rear==NULL)
        return 0;
    else
        p=lqu->front;
    if(lqu->front==lqu->rear)
        lqu->front=lqu->rear=NULL;
    else
        lqu->front=lqu->front->next;
    x=p->data;
    free(p);
    return 1;
}

循环队列

队列为空：qu.front == qu.rear
队列为满：(qu.rear+1)%maxSize == qu.front
非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置
假溢出：普通顺序队列在一系列进队出队操作后，两个指针最终都会到达数组末端maxSize-1处，虽然队列中没有元素或元素未满，都不能让新元素入队。因此使用循环队列

//初始化
void initQueue(SqQueue &qu)
{
    qu.front=qu.rear=0;	//队首队尾指针重合，并指向0
}
//进队
int enQueue(SqQueue &qu, int x)
{
    if((qu.rear+1)%maxSize==qu.front)	//判断队满
        return 0;
    qu.rear=(qu.rear+1)%maxSize;	//先移动指针
    qu.data[qu.rear]=x;		//存入元素
    return 1;
}
//出队
int deQueue(SqQueue &qu, int &x)
{
    if(qu.front==qu.rear)	//判断队空
        return 0；
   	qu.front=(qu.front+1)%maxSize;	//队非空，移动指针
    x=qu.data[qu.front];	//取出元素
    return 1;
}

双端队列

一种插入和删除操作在两端均可进行的线性表
输入受限的双端队列：允许在一端进行插入和删除（进队和出队），另一端只允许删除
输出受限的双端队列：允许在一端进行插入和删除（进队和出队），另一端只允许插入

算术表达式三种形式

前缀

中缀

后缀