栈、队列和数组

第三章： 栈、队列和数组

3.1栈

3.1.1栈的基本概念

$\quad$ （1）栈的定义

$\quad$ $\quad$ 只能在一端进行插入删除操作。

$\quad$ （2）栈的基本操作

$\quad$ $\quad$ InitStack(&S);

$\quad$ $\quad$ StackEmpty(S);

$\quad$ $\quad$ Push(&S,x);

$\quad$ $\quad$ Pop(&S,&x);

$\quad$ $\quad$ GetTop(S,&x);

$\quad$ $\quad$ DestroyStack(&S);

3.1.2栈的顺序存储结构

$\quad$ （1）顺序栈的实现

#define MaxSize 50
typedef struct {
    Elemtype data[MaxSize];
    int top;
}SqStack;

$\quad$ （2）顺序栈的基本运算

$\quad$ $\quad$ $\quad$ 初始化

void InitStack(SqStack &S)
{
    S.top = -1;
}

$\quad$ $\quad$ $\quad$ 栈判空

bool StackEmpty(SqStack S)
{
    if(S.top ==-1)
        return true;
    else
        return false;
}

$\quad$ $\quad$ $\quad$ 进栈

bool Push(SqStack &S,ElemType x)
{
    if(S.top = MaxSize -1)
        return false;
    S.data[++S.top] = x;
    return true;
}

$\quad$ $\quad$ $\quad$ 出栈

bool Pop(SqStack S,ElemType &x)
{ 
    if(S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}

$\quad$ （3）链栈的定义

typedef struct Linknode{
    Elemtype data;
    struct Linknode *next;
} *LiStack;

3.2队列

3.2.1 队列的基本概念

$\quad$ （1）队列的定义

$\quad$ 也是一种受限的线性表，只允许在一端进行插入，在另一端进行删除。

$\quad$ （2）队列的基本操作

$\quad$ $\quad$ InitQuene(&Q);

$\quad$ $\quad$ QueneEmpty(Q);

$\quad$ $\quad$ EnQuene(&Q,x);

$\quad$ $\quad$ DeQuene(&Q,&x);

$\quad$ $\quad$ GetHead(Q,&x);

3.2.2 队列的顺序存储结构

（1）队列的结构体定义

#define MaxSize 50
typedef struct {
    Elemtype data;
    int front,rear;
}SqQuene;

（2）InitQuene

void InitQueue(SqQueue& Q) {
    Q->front = Q->rear = 0; 
}

（3）QueneEmpty

int QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

（4）EnQuene

bool EnQueue(SqQueue& Q, Elemtype x) {
    if ((Q->rear + 1) % MaxSize == Q->front) {
        
        return false; 
    } else {
        Q->data[Q->rear] = x; 
        Q->rear = (Q->rear + 1) % MaxSize; 
        return true; 
    }
}

（5）DeQuene

bool DeQueue(SqQueue& Q, Elemtype& x) {
    if (Q->front == Q->rear) {
        
        return false;
    } else {
        *x = Q->data[Q->front]; 
        Q->front = (Q->front + 1) % MaxSize; 
        return true; 
    }
}

（6）GetHead

int GetHead(SqQueue Q, Elemtype& x) {
    if (Q.front == Q.rear) {
        
        return 0; 
    } else {
        x = Q.data[Q.front]; 
        return 1; 
    }
}

3.2.3队列的链式存储结构

（1）队列的结构体定义

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear;
}LinkQuene;

（2）InitQuene

void InitQueue(LinkQueue& Q) {
    Q->front = Q->rear = NULL;
}

（3）QueneEmpty

int QueueEmpty(LinkQueue Q) {
    return Q.front == NULL;
}

（4）EnQuene

void EnQueue(LinkQueue& Q, ElemType x) {
    LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->next = NULL;

    if (Q->rear == NULL) {
        Q->front = Q->rear = newNode;
    } else {
        Q->rear->next = newNode;
        Q->rear = newNode;
    }
}

（5）DeQuene

int DeQueue(LinkQueue& Q, ElemType& x) {
    if (Q->front == NULL) {
        return 0;
    } else {
        LinkNode* temp = Q->front;
        x = temp->data;
        Q->front = Q->front->next;

        if (Q->front == NULL) {
            Q->rear = NULL;
        }

        free(temp);
        return 1;
    }
}

（6）GetHead

int GetHead(LinkQueue Q, ElemType& x) {
    if (Q.front == NULL) {
        return 0;
    } else {
        x = Q.front->data;
        return 1;
    }
}

3.2.4 基本队列的变形

$\quad$ 循环队列、双端队列（两端都可进行插入和删除）。

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

$\quad$括号匹配示意图

表达式	栈	结果
(	(
(	( (
)	(
)		不匹配