堆和栈¶

栈的数据结构

typede int Value;
typedef struct Entry{
    Entry *next;
    Value value;
}Entry;

typedef struct Stack{
    Entry *head;/*添加和删除都在这个节点指针上*/
    int length;
    int capacity;
}Stack;

Stack create(unsigned int size);
void push(Stack,Value);
Value pop(Stack);

队列的数据结构

typede int Value;
typedef struct Entry{
    Entry *next;
    Value value;
}Entry;

typedef struct Queue{
    Entry *front;/*删除都在这个节点指针上*/
    Entry *rear;/*添加在这个节点指针上*/
    int length;
}Stack;

void enqueue(Queue,Value);
void dequeue(Queue);

这里的题目是有关栈和队列的问题。

循环队列中元素个数¶

如果用一个循环数组 q[0..m-1] 表示队列时,该队列只有一个队列头指针 front，不设队列尾指针 rear，求这个队列中从队列头到队列尾的元素个数（包含队列头、队列尾）

分析：

有 rear 指针时：

if (rear>front)  
    count = rear-front+1
else  
    count = rear-front+m+1

综合: count = （rear-front+m+1)%m

不用 rear 指针的话：数据结构中加一个 int count 来计数。

设计包含 min 函数的栈¶

定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。

主要是 min 函数实现。咋一看，用一个变量来存储最小值，或最小值的下标不就 ok 了？这在只 push 的时候有用，想想如果这个最小值 pop 出去了呢？我们怎么更新现在的最小值？

这里用一个辅助栈，空间复杂度是 O(n).

push 一个元素 a 时，该元素 a 与辅助栈顶 f[top] 元素比较: a > f[top],在辅助栈再次中 push 一遍 f[top] （可以把这个省去，节省空间，代价是 pop 的时候要跟最小栈元素比较，如果 pop 元素跟最小栈栈顶相等，可能最小值要变了） a < f(top),把 a push 到辅助栈中

这样辅助栈中的元素是从上到小递增的数列。且辅助栈中的栈顶元素总是栈中元素集合的最小值。

以上方法需要的空间复杂度是 O（n）

栈的 push、pop 序列¶

题目：输入两个整数序列。其中一个序列表示栈的 push 顺序，判断另一个序列有没有可能是对应的 pop 顺序。为了简单起见，我们假设 push 序列的任意两个整数都是不相等的。

比如输入的 push 序列是 [1、2、3、4、5] ，那么 [4、5、3、2、1] 就有可能是一个 pop 序列

因为可以有如下的 push 和 pop 序列：【push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop】, 这样得到的 pop 序列就是【4、5、3、2、1】。

但序列【4、3、5、1、2】就不可能是 push 序列【1、2、3、4、5】的 pop 序列。

这里只是要判断是不是 pop 序列，并没有要求所有的 pop 序列需要一个辅助栈（需要一个写好的栈结构辅助，如果是 C 语言，还要包装一个栈结构）

对序列 A 中的 A[0] 入栈，比较 B[0]
如果不相等，A[1] 入栈
直到 A[i] = B[0]
栈顶出栈，开始匹配 B[1]
如果 A[i-1]!=B[1],那就继续入栈 A[i+1]

6 .循环往复~ 7. 如果最后，栈为空，就是一个 pop 序列；如果栈不为空，或者 B 数组都没有遍历到尾部，就肯定不是 pop 序列了

颠倒栈¶

题目：用递归颠倒一个栈。例如输入栈 {1, 2, 3, 4, 5}，1 在栈顶。颠倒之后的栈为 {5, 4, 3, 2, 1}，5 处在栈顶。

思路一：所有元素 pop 出来，放到一个数组里，然后在从第一个元素开始入栈，空间复杂度需要 O(N) 思路二：递归方法。把栈看出 2 部分：1 和 {2,3,4,5} , 把栈 {2，3，4，5} 颠倒过来，然后把 1 放到底部，那整个栈就颠倒过来了。

void reverseStack(){    
    stack.pop();
    reverseStack();
    addTopToStackBottom();
}