3.1 栈

3.1.1 栈的定义

栈作为一种限定性线性表，是只允许在同一端进行插入和删除操作的线性表。

栈顶：通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。

栈底：同时表的另一端被称为栈底 (Bottom)。

空栈：当栈中没有元素。

满栈：无法申请到栈区可用空间。

上溢：栈已满仍要入栈。

下溢：栈已空仍要出栈。

栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。具有先进后出（FILO）或后进先出（LIFO）的特点。

栈的示意图

3.1.2 栈的顺序实现

3.1.2.1 结构定义

用一组连续的存储单元依次存放自栈底到栈顶的数据元素。设一个位置指针top（栈顶指针）动态指示栈顶元素在顺序栈中的位置，当top=-1时，表示空栈。

1
2
3
4
5
6
7
typedef int datatype;  
# define MAXSIZE 100
typedef struct{    
    datatype  data[MAXSIZE];
    int top; 
    } seqstack; 
seqstack *s;
3.1.2.2 基本操作

（1）判断栈空

1
2
3
int EMPTY(seqstack *s) {
    return (!s–>top>=0);
}

（2）置空栈

1
2
3
void SETNULL(seqstack *s) {
    s–>top=-1;
}

（3）判断栈满

1
2
3
int FULL(seqstack  *s) {
    return (s–>top==MAXSIZE-1);
}

（4）进栈

1
2
3
4
5
6
7
8
9
seqstack * PUSH(seqstack  *s，datatype x) {
    if (FULL(s)){ 
        printf(“stack overflow”); 
        return NULL; 
    }
    s–>top++; 
    s–>data[s–>top]=x;  
    return s;
}

（5）出栈

1
2
3
4
5
6
7
8
datatype POP(seqstack *s) {
    if (EMPTY(s)) { 
        printf(“stack underflow”);
        return NULL;
    }
    s–>top--; 
    return(s–>data[s–>top+1]);
}

（6）取栈顶

1
2
3
4
5
6
7
datatype TOP(seqstack  *s) {
    if (EMPTY(s)) { 
        printf(“stack is empty”);
        return NULL;
    }
    return (s–>data[s–>top]);
}
3.1.2.3 两栈共享技术

栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。

为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使 其存储空间互相补充，这就是多栈共享技术。

在顺序栈的共享技术中最常用的是两个栈的共享技术即双端栈：它主要利用了“栈底位置不变，而栈顶位置动态变化”的特性。

首先为两个栈申请一个共享的一维数组空间S[M]， 将两个栈的栈底分别放在一维数组的两端，分别是 0，M-1。由于两个栈顶动态变化，这样 可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。

由此可见，两栈共享要比两个栈分别申请M/2的空间利用率要高。

两栈共享的数据结构定义如下：

1
2
3
4
5
#define M 100 
typedef struct { 
    StackElementType Stack[M];   
    StackElementType  top[2]; /*top[0]和 top[1]分别为两个栈顶指示器*/
}DqStack;

两个栈共享空间的示意如下图所示:

双端栈

若栈1的底在v[1]，栈2的底在V[N]，则栈满的条件是top[1]+1==top[2]。

（1）初始化操作：

1
2
3
4
void InitStack(DqStack *S) {
    S->top[0]=-1; 
    S->top[1]=M; 
}

（2）进栈操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Push(DqStack *S, StackElementType x, int i) {
    /*把数据元素 x 压入 i 号堆栈*/  
    if(S->top[0]+1==S->top[1]) /*栈已满*/
           return(FALSE);  
    switch(i)  {  
        case 0:  
            S->top[0]++;
            S->Stack[S->top[0]]=x; 
            break;  
        case 1:   
            S->top[1]--;
            S->Stack[S->top[1]]=x;
            break;    
        default:
            /*参数错误*/             
            return(FALSE)   
    }  return(TRUE); 
}

（3）出栈操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Pop(DqStack *S, StackElementType *x, int i) {
    /* 从 i 号堆栈中弹出栈顶元素并送到 x 中 */  
    switch(i)  {
        case 0:
            if(S->top[0]==-1)
                return(FALSE);
            *x=S->Stack[S->top[0]];
            S->top[0]--;
            break;
        case 1:
            if(S->top[1]==M)
                return(FALSE);    
            *x=S->Stack[S->top[1]];
            S->top[1]++;
            break;
        default:
            return(FALSE);
    }
    return(TRUE);
}

3.1.3 栈的链式实现

链栈即采用链表作为存储结构实现的栈。为便于操作，这里采用带头结点的单链表实现栈。

由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针，如下图所示：

链栈

在上图中，top 为栈顶指针，始终指向当前栈顶元素前面的头结点,它唯一地确定一个链栈。若 top->next=NULL，则代表栈空，该链栈为空栈。

链栈中的结点是动态产生的，无需考虑上溢问题。

采用链栈时，栈的各种基本操作的实现与单链表的操作类似，对于链栈，在使用完毕时，应该释放其空间。

3.1.3.1 结构定义
1
2
3
4
5
6
typedef  int datatype;
typedef struct node{    
    datatype  data;
    struct node * next;
    }linkstack;
linkstack * top;
3.1.3.2 基本操作

（1）进栈

1
2
3
4
5
6
7
linkstack *PUSHLSTACK(linkstack *top, datatype x) { 
    linkstack *p;
    p＝(linkstack *)malloc(sizeof(linkstack));
      p->data＝x; 
     p->next＝top;
     return p;  //返回新栈顶指针
}

（2）出栈

1
2
3
4
5
6
7
8
9
10
11
linkstack *POPLSTACK(linkstack *top, datatype *datap) { 
    linkstack *p;
    if (top==NULL) { 
        printf(“under flow”);
    }
    datap＝top->data; /*栈顶结点数据存入*datap */
     p=top;
     top＝ top->next;
     free(p);
      return top;  //返回新栈顶指针
 }

3.2 队列

3.2.1 队列的概念

队列(Queue)也是一种运算受限的线性表。只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。具有先进先出（FIFO）的特点。

3.2.2 顺序队列

队列的一种顺序存储称为顺序队列。与顺序栈类似，在队列的顺序存储结构中，用一组 地址连续的存储单元依次存放从队头到队尾的元素，如一维数组data[MAXSIZE]。 由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针 front 和 rear。

  • front：指示队头元素在数组中的位置
  • rear：指示真实队尾元素相邻的下一个位置
3.2.2.1 结构定义
1
2
3
4
5
6
7
#define MAXSIZE 100
typedef  struct{
    datatype data[MAXSIZE];
    int front;
    int rear;
}sequeue;
sequeue * sq;
3.2.2.2 假溢出

初始化队列时，令 front = rear =0；入队时，直接将新元素送入尾指针 rear 所指的单元， 然后尾指针增1；出队时，直接取出队头指针 front 所指的元素，然后头指针增1。

显然，在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。当 rear==MAXSIZE 时，认为队满。

但此时不一定是真的队满，因为随着部分元 素的出队，数组前面会出现一些空单元，如下图(d)所示。由于只能在队尾入队，致使被删除元素的空间永远无法重新利用。

把这种现象称为假溢出，真正队满的条件是 rear-front=MAXSIZE。

假溢出

3.2.3 链式队列

3.2.3.1 结构定义
1
2
3
4
5
6
7
8
9
typedef struct queuenode{
    datatype  data;
    struct queuenode  *next;
}QueueNode;

typedef struct{
    QueueNode  *front;
    QueueNode  *rear;
}LinkQueue;
3.2.3.2 基本操作

（1）置空

1
2
3
4
void InitQueue(LinkQueue *Q) {
    Q.front=Q.rear=(queuenode*)malloc(sizeof(queuenode )); 
    Q.front->next=Q.rear->next=NULL;
}

（2）判断队空

1
2
3
int QueueEmpty(LinkQueue *Q) {
    return (Q.front->next= =NULL &&Q.rear->next= =NULL);
}

（3）入队

1
2
3
4
5
6
7
8
void EnQueue(LinkQueue *Q, datatype x){    
    QueueNode *p;
    p=(QueueNode * )malloc(sizeof(QueueNode));
    p–>data=x;
    p–>next=NULL;
    Q->rear–>next=p;
    Q->rear=p;
}

（4）出队

1
2
3
4
5
6
7
8
9
10
11
12
13
DeQueue(linkqueue *Q) {
    linkqueue  *p;
       datatype x;
    if (EMPTY(Q))    
        return NULL;
       p = Q->front->next;      
    Q->front->next = p–>next;
    if (p->next==NULL) 
        Q->rear = Q->front;  
    x = p->data;
    free(p);
    return x;
}

3.2.4 循环队列

为了解决假溢出问题，引入了循环队列的概念。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界( MaxSize-1 )时，其加1操作的结果是指向向量的下界0。

3.2.4.1 判断栈满

入队时：尾指针向前追赶头指针，出队时：头指针向前追赶尾指针，故队空和队满时头尾指针均相等，无法通过sq->front == sq->rear来判断队列“空”还是“满”。
解决此问题的方法至少有两种：

  • 另设一个布尔变量以区别队列的空和满；

  • 少用一个元素空间为代价，入队前，测试尾指针 sq-> rear+1==sq->front ，若相等则认为队满。

3.2.4.2 基本操作

队空判断：sq->front == sq-> rear

队满判断：sq-> front ==(sq-> rear + 1) % maxSize

入队：sq-> rear = (sq-> rear + 1) % maxSize

出队：sq-> front = (sq-> front + 1) % maxSize

求队长：(sq-> rear - sq-> front+maxSize)%maxSize

（1）入队

  • 检查队列是否已满，若队满，则进行溢出错误处理。

  • 将队尾指针后移一个位置（即加1），指向下一单元。

  • 将新元素赋给队尾指针所指单元。

1
2
3
4
5
6
7
Status EnQueue (SqQueue *Q, ElemType  e){    
    if ( (Q->rear+1)%MAXQSIZE == Q->front )  
        return(ERROR);   //队满上溢
    Q->rear=(Q->rear+1)%MAXQSIZE;
    Q->data[Q->rear]=e;
    return(True);   
}

（2）出队

  • 检查队列是否为空，若队空，则进行下溢错误处理。

  • 将队首指针后移一个位置（即加1）。

  • 取队首元素的值。

1
2
3
4
5
6
Status DeQueue (SqQueue *Q) { 
    if (Q->rear== Q->front)  
        return(NULL);  //队空下溢
    Q->front=(Q->front+1)%MAXQSIZE;
    return(Q->data[Q->front]);
}

（3）置空队

1
Q->front=Q->rear= MAXQSIZE-1;

（4）取队头

1
2
3
4
5
datatype  GetHead(SqQueue *Q ) { 
    if (Q->front==Q->rear)  
        return(NULL);  //队空
    return (Q->data[(Q->front+1)%MAXQSIZE] );
}

（5）判断队空

1
2
3
4
5
6
int QueueEmpty(SqQueue *Q ){
    if (Q->front==Q->rear) 
        return (True);
      else 
        return (False);  
}

3.3 栈和队列的应用

3.3.1 递归函数

递归函数又称为自调用函数，它的特点：在函数内部可以直接或间接地调用函数自己。

C语言描述如下：

1
2
3
4
5
6
int  FACT(int n) { 
    if (n==1) 
        return (1);
     else
        return (n*FACT(n-1));
}

3.3.2 算术表达式求值

波兰表达式与逆波兰表达式

3.3.3 括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#define maxsize 100
typedef int datatype;

typedef struct{
    datatype data[maxsize];
    datatype top;
}seqstack;
seqstack *s;

void build();
void push();
void pop();
int check(char ss[]);

void main(){
    char ss[maxsize];
    build();
    printf("请输入要测试的算数表达式:");
    scanf("%s",ss);
    if(check(ss)==-1)
        printf("算数表达式不匹配!");
    else
        printf("算数表达式匹配!");
}

void build(){
    s=(seqstack*)malloc(sizeof(seqstack));
    s->top=-1;
}
int check(char ss[]){
    int i=0;
    while(ss[i] != '\0'){
        i++;
        if(ss[i] == '(')
            push();
        else if(ss[i] == ')')
            pop();
    }
    return s->top;
}

void push(){
    s->top++;
}
void pop(){
    s->top--;
}

3.3.4 回文串判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxsize 100

typedef struct {
    char data[maxsize];
    int top;
} stack;

typedef struct {
    char data[maxsize];
    int front;
    int rear;
} queue;

int isempty_queue(queue * stq){
    return stq->front == stq->rear;
}

int isfull_queue(queue *stq){
    return stq->rear >= maxsize -1 ;
}

queue * init_queue(){
    queue * tmp = (queue*) malloc(sizeof(queue));
    tmp->front = tmp->rear = 0;
    return tmp;
}

char dequeue(queue * stq){
    if( isempty_queue(stq) ) {
        printf("队列为空，无法出队\n");
        exit(0);
    }
    return stq->data[stq->front++];
}

void inqueue(queue *stq, char value) {
    if( isfull_queue(stq) ) {
        printf("队列已满，无法入队\n");
        exit(0);
    }
    stq->data[stq->rear++] = value;
}

stack * init_stack(){
    stack * tmp = (stack *) malloc( sizeof(stack) );
    tmp->top = 0;
    return tmp;
}

int isempty_stack(stack *stk) {
    return stk->top == 0 ? 1 : 0;
}

int isfull_stack(stack *stk) {
    return stk->top >= maxsize -1 ? 1: 0;
}

char pop(stack *stk) {
    if( isempty_stack(stk) ) {
        printf("堆栈为空，无法出栈\n");
        exit(0);
    }
    return stk->data[--stk->top];
}

void push(stack *stk, char value) {
    if( isfull_stack(stk) ) {
        printf("堆栈已满，无法入栈\n");
        exit(0);
    }
    stk->data[stk->top++] = value;
}

void compare(stack * stk, queue *stq, char str[], int len) {
    int i;
    int flag = 0;
    char temp_stack;
    char temp_queue;

    for(i = 0; i < len; i++){
        push(stk, str[i]);
        inqueue(stq, str[i]);
    }
    
    for(i = 0; i < len; i++){
        temp_stack = pop(stk);
        temp_queue = dequeue(stq);

        if(temp_stack != temp_queue) {
            printf("不是回文串\n");
            flag = 1;
            break;
        }
    }

    if( !flag )
        printf("是回文串\n");
}

int main(){
    queue * stq = init_queue();
    stack * stk = init_stack();

    char c[maxsize],s;
    int i=0;
    printf("请输入字符序列，以@结束\n");
    scanf("%c",&s);
    while(s!='@'){
        c[i]=s;
        scanf("%c",&s);
        i++;
    }
    c[i]='\0';
    compare(stk, stq, c, strlen(c)-1);

    return 0;
}

3.4 例题

3.4.1 例1

栈和队列是特殊的线性表，其特殊性体现在？为什么要引入循环队列？

和普通线性表相比，对插入、删除运算加以限制。一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，为了解决这种问题，就要引入循环队列。

3.4.2 例2

设一个栈的入栈序列为A、B、C、D，则可能的出栈序列有哪些？

共计14种，分别是：ABCD、ACBD、ACDB、ABDC、ADCB、BACD、BADC、BCAD、BCDA、BDCA、CBAD、CBDA、CDBA、DCBA。

3.4.3 例3

有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（C第一个出栈且D第二个出栈）的次序有哪几种？

共计3种，分别是：CDEBA、CDBEA、CDBAE。

3.4.4 例4

判定一个顺序栈ST（元素个数最多为StackSize）为空/满的条件是【 】。

空：ST->top=0，满：ST->top=MAXSIZE-1。

3.4.5 例5

判定一个循环队列Q（存放元素位置：0至QueueSize-1）队满的条件是【 】。

sq-> front ==(sq-> rear + 1) % maxSize。

3.4.6 例6

若用一个大小为6的数组来实现环形队列，且当前rear和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是【 】和【 】。

2 ; 4