# 栈

## 栈的基本概念

### 定义

  只允许在一端进行插入或删除操作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一段进行插入和删除操作。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/栈.jpg)

  栈顶（Top）：线性表允许进行插入和删除的一端。

  栈底（Bottom）：固定的，不允许进行插入和删除的另一端。

  空栈：不含任何元素。

  如上图：a1为栈底元素，an为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1，a2，... ,an 而出栈次序为an，...，a2，a1。栈的明显的操作特征为后进先出（Last In First Out，LIFO）,故又称 后进先出的线性表。

### 栈的基本操作

  1）InitStack（\&S）：初始化空栈S

  2）StackEmpty（S）：判断一个栈是否为空

  3）Push（\&S，x）：进栈，若栈未满，则将x加入使之成为新栈顶

  4）Pop（\&S，\&x）：出栈，若栈非空，则将栈顶元素，并用x返回

  5）GetTop(S，\&x)：读栈顶元素，若栈顶元素非空，则用x返回栈顶元素

  6）DestroyStack(\&S)：销毁栈，并释放栈S占用的存储空间

## 栈的顺序存储结构

### 顺序栈的实现

  采用顺序存储的栈称为**顺序栈**，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。

  栈的顺序存储类型可以用以下表示：

```cpp
#define MAXSIZE 100            //栈中元素的最大个数
typedef struct {
    ElemType data[MAXSIZE];    //存放栈中元素
    int top;                //栈顶指针
} SqStack;
```

  栈顶指针：S.top，初始时设置S.top = -1；栈顶元素：S.data\[S.top]；

  进栈操作：栈不满时，栈指针加1，再送值到栈顶元素

  出栈操作：栈非空时，先去栈顶元素值，再将栈顶指针减1

  栈空条件：S.top == -1

  栈满条件：S.top == MAXSIZE - 1

  栈长：S.top + 1

### 顺序栈的基本运算

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/进栈.jpg)

#### 初始化

```cpp
void InitStack(SqStack& S){
    S.top = -1;                //初始化栈顶指针
}
```

#### 判栈空

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

#### 进栈

```cpp
bool Push(SqStack& S, ElemType x){
    if( S.top == MAXSIZE - 1 ){    //栈满，报错
        return false;        
    }
    S.top ++ ;                    //栈顶指针加1
    S.data[S.top] = x;            //入栈
    return true;
}
```

#### 出栈

```cpp
bool Pop(SqStack& S, ElemType& x){
    if( S.top == -1 ){            //栈空，报错
        return false;
    }
    x = S.data[S.top];
    S.top --;
    return true;
}
```

#### 读栈顶元素

```cpp
bool GetTop(SqStack& S,ElemType& x){
    if( S.top == -1 ){            //栈空，报错
        return false;
    }
    x = S.data[S.top];
    return true;
}
```

  注意：若栈顶指针初始化为S.top = 0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为S.data\[S.top++]，出栈操作为x = S.data\[--S.top]。因为栈顶指针若初始化为 0 时，则栈顶指针始终指向顺序栈将要入栈的位置，也就是栈顶指针的下标就是入栈元素的下标。

### 共享栈

  利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/共享栈.png)

  两个栈的栈顶指针都指向栈顶元素，top1 = -1 时，stack1 为空，top2 = MAXSIZE - 1 时，stack2 为空；仅当两个栈顶指针相邻（top1 - top2 == 1)时，判断栈满。当stack1进栈时top1先加1再赋值，stack2进栈时top2先减1再赋值；出栈正好相反。

  共享栈是为了更有效地利用存储空间，两个栈的空间正好互相调节，只有在整个存储空间被占满时才发生上溢。存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

## 栈的链式存储结构

  采用链式存储的栈称为**链栈**，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，top指向栈顶元素，

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/链栈.jpg)

  链栈的存储类型可描述为：

```cpp
typedef struct LinkNode{
    ElemType data;
    struct LinkNode* next;
}LinkNode, *LinkStack;
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xiuxin.gitbook.io/datastructre/zhan-he-dui-lie/zhan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.