一、栈和队列的基本概念

　1.栈是一种线性表无疑。一般提供两种操作：入栈（PUSH） 和出栈（ POP）。分别对应着数据插入和数据删除。

　　队列的话，也是一种线性表。和栈不同的是，栈只能在栈顶操作（PUSH&POP），而队列被限制为从一端入，从另一端出。

　　这里的栈和队列指的都是最一般的情况。

　2.栈是先进后出的（First In Last Out, FILO），队列是先进先出的（First In First Out, FIFO）。

　从真题来看，这部分题考概念的比较简单。

二、栈和队列的顺序存储结构

　　1、顺序栈

1 //定义2 typedef struct3 {4     int data[max_size];//比如 int data[100];5     int top; //栈顶6 }SqStack;

　　考试的时候，简单的可以这么写

1 int myStack[max_size];//例如int myStack[1000];2 int top = -1;3 4 //Push key5 myStack[++top] = key;6 //POP7 key = myStack[top--];

　　2、顺序队

1 typedef struct2 {3         int data[max_size];4         int front;5         int rear;6 }SqQueue;

　　3、循环队列

　　front和rear循环。

　　rear不能超过front一圈。

　　这部分内容比较绕的就是循环队列，还有就是队头队尾的位置判断，还有对队列为空和为满的判断。

三、栈和队列的链式存储结构

　　1、栈 链式实现

1 typedef struct LNode 2 { 3     int data; 4     struct LNode *next; 5 }LNode, *LinkStack; 6  7 //PUSH 8 newLNode->data = key; 9 newLNode->next = headLNode->next;10 headLNode->next = newLNode;11 12 //POP13 temp = headLNode->next;14 key = temp->data;15 headLNode->next = temp->next;16 free(temp);

　　2、队列 链式实现

1 typedef struct QNode 2 { 3     int data; 4     int QNode *next; 5 }QNode; 6  7 typedef struct 8 { 9     QNode *front;10     QNode *rear;11 }LinkQueue;12 13 //入队14 lqu->rear->next = p;15 lqu->rear = p;16 //出队17 p = lqu->front;18 lqu->front = p->next;19 key = p->data;20 free(p);

四、栈和队列的应用

　　栈的话，很常规的一个东西就是表达式计算。

　　队列的话，CPU资源竞争的问题、主机和打印机之间的协调等等。

五、特殊矩阵的压缩存储

　　1、对称阵A压缩到SA[n(n+1)/2];

　　2、三角矩阵A压缩到SA[n(n+1)/2];

　　3、对角矩阵