栈的顺序存储结构实现

参考代码（使用数组实现）

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
  
#define OK 1  
#define ERROR 0  
#define TRUE 1  
#define FALSE 0  
  
#define MAXSIZE 100  
  
typedef int ElemType;  
typedef int Status;  
  
typedef struct  
{  
    ElemType data[MAXSIZE];  
    int top;  
}sqStack;  
  
//四个基础操作  
Status InitStack(sqStack *s);    //初始化操作，建立一个空栈  
Status ClearStack(sqStack *s);    //将栈清空  
Status StackEmpty(sqStack s);    //若栈存在，返回true，否则返回false  
int StackLength(sqStack s);        //返回栈S的元素个数  
  
Status GetTop(sqStack s, ElemType *e);    //若是栈存在且非空，用e返回S的栈顶元素  
Status Push(sqStack *s, ElemType e);    // 若是栈存在，则插入新的元素e到栈S中并成为栈顶元素  
Status Pop(sqStack *s, ElemType *e);    //若是栈存在且非空，删除栈顶元素，并用e返回其值  
Status DestroyStack(sqStack *s);        //若是栈存在，则销毁他  
  
int main()  
{  
    sqStack sk;  
    int i;  
    ElemType e;  
  
    //初始化空栈  
    printf("1.InitStack\n");  
    InitStack(&sk);  
    printf("2.Push 1-5\n");  
    for (i = 1; i <= 5; i++)  
        Push(&sk, i);  
    printf("3.Pop number for three times\n");  
    for (i = 1; i <= 3;i++)  
    {  
        Pop(&sk, &e);  
        printf("Pop %d: %d\n",i, e);  
    }  
    GetTop(sk, &e);  
    printf("4.Get Top:%d\n",e);  
    printf("5.Push 6-10\n");  
    for (i = 6; i <= 10; i++)  
        Push(&sk, i);  
    printf("6.Get stack length:%d\n", StackLength(sk));  
    prin...

课后习题

【2010年真题】某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（）。 
A．b a c d e         B．d b a c e         C．d b c a e         D．e c b a d

参考答案：C
答案解析：考查受限的双端队列的出队序列。 
A 可由左入，左入，右入，右入，右入得到 B 可由 左入，左入，右入，左入，右入得到。 
D 可由左入，左入，左入，右入，左入得到 所以不可能得到 C。 

【2009年真题】为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。 
A．栈         B．队列         C．树         D．图

参考答案：B
答案解析：考查栈和队列的特点及应用。 
C 和 D 直接排除，缓冲区的特点需要先进先出，若用栈，则先进入缓冲区的数据则要排队到最后才能打印，不符题意，所以只有队列符合题意。 

【2014年真题】循环队列放在一维数组 A[0…M-1]中，end1 指向队头元素，end2 指向队尾元素的后 一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素。初始 时为空。下列判断队空和队满的条件中，正确的是（） 
A．队空：end1 == end2； 队满：end1 == (end2+1)mod M 
B．队空：end1 == end2； 队满：end2 == (end1+1)mod (M-1) 
C．队空：end2 == (end1+1)mod M； 队满：end1 == (end2+1)mod M 
D．队空：end1 == (end2+1)mod M；队满：end2 == (end1+1)mod (M-1)

参考答案：A
答案解析：end1 指向队头元素，那么可知出队的操作是先从 A[end1]读数，然后 end1 再加 1。 end2 指向队尾元素的后一个位置，那么可知入队操作是先存数到 A[end2]，然后 end2 再加 1。若把 A[0]储存第一个元素，当队列初始时，入队操作是先把数据放到 A[0]，然后 end2 自增，即可知 end2 初值为 0；而 end1 指向的是队头元素，队头元素的在数组 A 中的下标为 0，所以得知 end1 初值也为 0，可知队空条件为 end1==end2；然后考虑队列满时，因为队列 最多能容纳 M-1 个元素，假设队列存储在下标为 0 到下标为 M-2 的 M-1 个区域，队头为 A[0]，队尾为 A[M-2]，此时队列满，考虑在这种情况下 end1 和 end2 的状态，end1 指向队 头元素，可知 end1=0，end2 指向队尾元素的后一个位置，可知 end2=M-2+1=M-1，所以可 知队满的条件为 end1==(end2+1)mod M，选 A。 
注意：考虑这类具体问题时，用一些特殊情况判断往往比直接思考问题能更快的得到答案，并可以画出简单的草图以方便解题。

【2019年真题】设栈 S 和队列 Q 的初始状态均为空，元素 a,b,c,d,e,f,g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b,d,c,f,e,a,g，则栈 S 的容量至少是（）。 
A．1         B．2         C．3         D．4 

参考答案：C
答案解析：考查栈的最大递归深度。 
时刻注意栈的特点是先进后出。下面是出入栈的详细过程： 

序号	说明	栈内	栈外	序号	说明	栈内	栈外
1	a 入栈	a		8	e入栈	ae	bdc
2	b 入栈	ab		9	f 入栈	aef	bdc
3	b 出栈	a	b	10	f 出栈	ae	bdcf
4	c 入栈	ac	b	11	e 出栈	a	bdcfe
5	d 入栈	acd	b	12	a 出栈		bdcfea
6	d 出栈	ac	bd	13	g 入栈	g	bdcfea
7	c 出栈	a	bdc	14	g 出栈		bdcfeag