#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stackADT.h"

#define OPERATOR_TYPE 4
char Operator[OPERATOR_TYPE] = {'+', '-', '*', '/'};
char *Expression = "12+3*85-/";

void suffixExpression(char *inputStr)
{
	int cnt, cnt2;
	int operateNum1, operateNum2;
	Stack s = CreateStack();
	for (cnt = 0; inputStr[cnt] != '\0'; cnt++) {
		if ((inputStr[cnt] >= '0') && (inputStr[cnt] <= '9')) {
			printf("Push %d\n", (inputStr[cnt] - '0'));
			Push((inputStr[cnt] - '0'), s);
		}

		for (cnt2 = 0; cnt2 < OPERATOR_TYPE; cnt2++) {
			if (inputStr[cnt] == Operator[cnt2]) {
				operateNum2 = Top(s);
				Pop(s);
				operateNum1 = Top(s);
				Pop(s);
				printf("operator=%c, num1=%d, num2=%d\n", Operator[cnt2], operateNum1, operateNum2);

				switch (cnt2) {
					case 0: {
						Push((operateNum1 + operateNum2), s);
						printf("Push %d\n", operateNum1 + operateNum2);
						break;
					}
					case 1: {
						Push((operateNum1 - operateNum2), s);
						printf("Push %d\n", operateNum1 - operateNum2);
						break;
					}
					case 2: {
						Push((operateNum1 * operateNum2), s);
						printf("Push %d\n", operateNum1 * operateNum2);
						break;
					}
					case 3: {
						Push((operateNum1 / operateNum2), s);
						printf("Push %d\n", operateNum1 / operateNum2);
						break;
					}
					default:
						break;
				}
			}
		}
	}
	
	operateNum1 = Top(s);
	Pop(s);
	DistroyStack(s);
	printf("result=%d\n", operateNum1);
}

void main()
{
	suffixExpression(Expression);
}

• 中缀到后缀的转换: 当读到一个操作数的时候，立即把它放到输出中，操作符不立即输出，从而必须先存在某个地方。正确的做法是将已经见到过的操作符放到栈中，而不是放到输出中。当遇到左圆括号时我们也要将其推入栈中，从一个空栈开始计算。如果见到一个右括号，那么就将栈元素弹出，将弹出的符号写出直到我们遇到一个左括号，但是这个左括号和右括号只是弹出，并不输出。如果见到其他任何操作符号，那么就从栈中弹出栈元素，直到发现优先级更低的元素则不弹出，将读取到的操作符入栈(若优先级相同则出栈)。有一个例外，除非是在处理一个）的时候，否则我们绝不从栈中移走（。因此，当从栈弹出元素的工作完成后，再将操作符压入栈中。最后，如果读到输入的末尾，我们将栈元素弹出直到该栈变成空栈。将符号写道输出中。
• 函数调用: 函数的嵌套调用过程中，主调例程的所有局部变量和返回地址要被保存起来（入栈），在被调例程结束后进行恢复（出栈）。因此全部工作均可由一个栈来完成。当前环境是由栈顶描述的。因此，一条返回语句就可给出前面的环境。实际计算机中的栈，常常时从内存分区的高端向下增长。而在许多系统中是不检测栈溢出的，但是用尽栈空间的情况总是可能发生的。栈溢出的后果是严重的：程序崩溃，数据错误。在正常情况下不应该越出栈空间，发生这种情况通常是由失控递归的指向引起的（忘记基准情形），也有可能是某些表面上正确的程序，但是递归了N次（数量巨大），导致栈溢出。例如尾递归。
• 尾递归完全可由goto语句改造出来。例如可以goto到顶部。递归总能够被彻底除去（编译器是在转变成汇编语言时完成的）虽然非递归程序一般说来确实比等价的递归程序要快，但是代价时使得程序的清晰性变得不足

3.4 队列

数组实现

• 节点定义

#define CAPACITY 10
struct QueueRecord {
    int Capacity;
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
}

typedef struct QueueRecord *Queue;

Queue
CreateQueue(int MaxElements)
{
    if (MaxElements <= 0) {
        return NULL;
    }
    Queue q = NULL;
    q = (Queue)malloc(sizeofstruct QueueRecord(struct QueueRecord));
    if (q == NULL) {
        printf("queue malloc failed\n");
        return NULL;
    }
    memset(q, 0, sizeof(struct QueueRecord));
    q->Capacity = CAPACITY;
    q->Front = 1;
    q->Rear = 0;
    q->Size = 0;
    q->Array = (ElementType *)malloc(sizeof(ElementType) * CAPACITY);
    if (q->Array == NULL) {
        return NULL;
    }
    memset(q->Array, 0, sizeof(ElementType) * CAPACITY);
    return q;
}

void
DisposeQueue(Queue Q)
{
    if (Q == NULL) {
        return;
    }
    if (Q->Array != NULL) {
        free(Q->Array);
    }
    free(Q);
}

int
IsEmpty(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    return (Q->Size == 0);
}

int
IsFull(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    return (Q->Size == Q->Capicity);
}

int
Enqueue(Queue Q, Element X)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsFull(Q)) {
        printf("Queue Q is full\n");
        return -1;
    }
    
    if (++(Q->Rear) >= Q->Capicity) {
        Q->Rear -= Q->Capicity;
    }
    Q->Array[Q->Rear] = X;
    Q->Size++;
    return 0;
}

int
Dequeue(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsEmpty(Q)) {
        printf("Queue Q is empty\n");
        return -1;
    }
    
    if (++(Q->Front) >= Q->Capicity) {
        Q->Front -= Q->Capicity;
    }
    Q->Size--;
    return 0;
}

ElementType
FrontAndDequeue(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsEmpty(Q)) {
        printf("Queue Q is empty\n");
        return -1;
    }
    
    ElementType ret = Q->Array[Q->Front];
    if (++(Q->Front) >= Q->Capicity) {
        Q->Front -= Q->Capicity;
    }
    Q->Size--;
    return ret;    
}

typedef struct Queue {
    ElementType Element;
    struct Queue *Pre;
    struct Queue *Next;
} Queue_T;

typedef Queue_T *QueuePtr
typedef QueuePtr QueueHead
#define MaxSize 10
#define EMPTY -1

int
IsEmpty(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }
    return (Q->Next == Q);
}

int
IsFull(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }
    
    int queueCnt = 0;
    QueuePtr tmp = NULL;
    tmp = Q->Next;
    while (tmp != Q) {
        queueCnt++;
        tmp = tmp->Next;
    }
    
    return (queueCnt == MaxSize);
}

QueueHead
CreateQueue()
{
    QueueHead Q = NULL;
    Q = (QueuePtr)malloc(sizeof(struct Queue));
    if (Q == NULL) {
        return NULL;
    }
    memset(Q, 0, sizeof(struct Queue));
    Q->Next = Q;
    Q->Pre = Q;
    return Q;
}

int
DisposeQueue(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }   
    
    MakeEmpty(Q);
    free(Q);
    return 0;
}

int
MakeEmpty(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }   
    
    QueueHead tmp = NULL, tmpNext = NULL;
    tmp = Q->Next;
    while (tmp != Q) {
        if (tmp) {
            tmpNext = tmp->Next;
            free(tmp);
            tmp = tmpNext;
        }
    }
    return 0;
}

int
Enqueue(QueueHead Q, ElementType Element)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsFull(Q)) {
        return -1;
    }
    
    QueuePtr qAdd = NULL;
    qAdd = (QueuePtr)malloc(sizeof(struct Queue));
    if (qAdd == NULL) {
        return -1;
    }
    memset(qAdd, 0, sizeof(struct Queue));
    qAdd->Element = Element;
    qAdd->Pre = Q->Pre;
    qAdd->Next = Q;
    Q->Pre->Next = qAdd;
    Q->Pre = qAdd;
    return 0;
}

ElementType
Front(QueueHead Q)
{
    if (Q == NULL) {
        return EMPTY;
    }
    if (IsEmpty(Q)) {
        return EMPTY;
    }
    
    return Q->Next->Element;
}

int
Dequeue(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsEmpty(Q)) {
        return -1;
    }
    
    QueuePtr tmp = NULL;
    tmp = Q->Next;
    Q->Next = tmp->Next;
    tmp->Next->Pre = Q;
    if (tmp != NULL) {
        free(tmp);
    }
    return 0;
}

ElementType
FrontAndDequeue(QueueHead Q)
{   
    if (Q == NULL) {
        return EMPTY;
    }
    if (IsEmpty(Q)) {
        return EMPTY;
    }
    
    ElementType ret;
    QueuePtr tmp = NULL;
    tmp = Q->Next;
    ret = tmp->Element;
    Q->Next = tmp->Next;
    tmp->Next->Pre = Q;
    if (tmp != NULL) {
        free(tmp);
    }
    return ret;    
}