第5章：栈

本章目标

  1. 理解栈的定义及其基本运算

  2. 掌握顺序栈和链栈的各种操作实现

  3. 掌握利用栈解决问题

本章内容

栈

  • 是一种只允许在表的固定一端（表尾），进行插入或删除操作的线性表
  • 插入操作称为入栈（压栈）
  • 删除操作称为出栈（弹栈）
  • 当栈中没有元素时为空栈

栈的存储结构

  • 顺序存储结构
  • 链式存储结构

栈的顺序存储结构：

  • 又称“顺序栈
  • 限定在表尾进行插入和删除操作的顺序表
  • 用一组连续的空间存放自栈底到栈顶的数据元素
  • 使用一维数组实现

顺序栈

在容量为4的顺序栈中将1，2依次入栈，然后2出栈

顺序栈的基本操作：

  • 栈的初始化
  • 判断栈的状态（空或满）
  • 查询栈的元素个数
  • 入栈
  • 出栈
  • 查询栈顶对象

顺序栈的初始化

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
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH05Demo
{
    internal class MyStack<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] data;

        /// <summary>
        /// 栈顶索引
        /// </summary>
        private int top;

        public MyStack()
        {
            data = new T[10];
            this.top = -1;
        }
        public MyStack(int capacity)
        {
            data = new T[capacity];
            this.top = -1;
        }
    }
}

1
2
3
4
5
6
private void button1_Click(object sender, EventArgs e)
{
    MyStack<string> myStack1 = new MyStack<string>();

    MyStack<string> myStack2 = new MyStack<string>(20);
}

判断栈的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/// <summary>
/// 是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
    return this.top == -1;
}
/// <summary>
/// 是否满栈
/// </summary>
/// <returns></returns>
public bool IsFull()
{
    return this.top ==  this.data.Length - 1;
}

查询栈的元素个数

1
2
3
4
5
6
7
8
/// <summary>
/// 获取栈的元素个数
/// </summary>
/// <returns></returns>
public int Count()
{
    return this.top+1;
}

入栈

实现步骤：

  • 判断如果栈已满，返回false, 不允许入栈
  • 若栈不满，将栈顶指针 top+1
  • 数据存入top所指的空间中
  • 操作成功返回true
1
2
3
4
5
6
7
8
9
10
11
12
/// <summary>
/// 入栈
/// </summary>
/// <param name="item"></param>
public bool Push(T item)
{
    if (this.IsFull())return false;

    this.data[++this.top] = item;

    return true;
}
1
2
3
4
5
6
7
8
9
private void button2_Click(object sender, EventArgs e)
{
    MyStack<string> myStack = new MyStack<string>();

    //入栈
    myStack.Push("张三");
    myStack.Push("李四");
    myStack.Push("王五");
}

出栈

实现步骤：

  • 判断顺序栈状态，如果栈已空，不允许出栈
  • 若栈不空，取出栈顶指针top所指的内容
  • 栈顶指针top-1，指向下一个元素
  • 返回出栈顶数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/// <summary>
/// 出栈
/// </summary>
/// <returns></returns>
/// <exception cref="InvalidOperationException"></exception>
public T Pop()
{
    if (this.IsEmpty())
    {
        throw new InvalidOperationException("栈已空");
    }
    T item = this.data[this.top];

    this.data[this.top]=default(T);

    this.top--;

    return item;
}
1
2
3
4
5
6
7
8
9
10
11
12
private void button3_Click(object sender, EventArgs e)
{
    MyStack<string> myStack = new MyStack<string>();

    //入栈
    myStack.Push("张三");
    myStack.Push("李四");
    myStack.Push("王五");

    //出栈
    string name= myStack.Pop();
}

查询栈顶对象

1
2
3
4
5
6
7
8
9
10
11
12
13
/// <summary>
/// 获取栈顶元素但不移除
/// </summary>
/// <returns></returns>
/// <exception cref="InvalidOperationException"></exception>
public T Peek()
{
    if (this.IsEmpty())
    {
        throw new InvalidOperationException("栈已空");
    }
    return this.data[this.top];
}
1
2
3
4
5
6
7
8
9
10
11
12
private void button4_Click(object sender, EventArgs e)
{
    MyStack<string> myStack = new MyStack<string>();

    //入栈
    myStack.Push("张三");
    myStack.Push("李四");
    myStack.Push("王五");

    //获取栈顶数据
    string name=myStack.Peek();
}

完整代码

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
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH05Demo
{
    /// <summary>
    /// 顺序栈
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal class MyStack<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] data;

        /// <summary>
        /// 栈顶索引
        /// </summary>
        private int top;

        public MyStack()
        {
            data = new T[10];
            this.top = -1;
        }
        public MyStack(int capacity)
        {
            data = new T[capacity];
            this.top = -1;
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.top == -1;
        }

        /// <summary>
        /// 是否满栈
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            return this.top == this.data.Length - 1;
        }

        /// <summary>
        /// 获取栈的元素个数
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            return this.top+1;
        }

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="item"></param>
        public bool Push(T item)
        {
            if (this.IsFull())return false;

            this.data[++this.top] = item;

            return true;
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Pop()
        {
            if (this.IsEmpty())
            {
                throw new InvalidOperationException("栈已空");
            }
            T item = this.data[this.top];

            this.data[this.top]=default(T);

            this.top--;

            return item;
        }

        /// <summary>
        /// 获取栈顶元素但不移除
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Peek()
        {
            if (this.IsEmpty())
            {
                throw new InvalidOperationException("栈已空");
            }
            return this.data[this.top];
        }
    }
}

链栈

栈的链式存储结构：

  • 又称“链栈”
  • 不带表头结点的单链表
  • 插入和删除操作仅限制在表头位置上进行
  • 链表的头指针即栈顶指针
  • 无栈满问题，存在栈空问题

入栈

实现步骤：

  • 构造新结点保存数据element
  • 新结点做为栈顶结点
  • 修改top指向新的栈顶结点
  • 栈内数据个数加1
  • 操作成功返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/// <summary>
/// 入栈
/// </summary>
/// <param name="item"></param>
public void Push(T item)
{
    //新结点
    TNode<T> node = new TNode<T> { data=item };
    node.nextNode = this.top;

    //更新头节点
    this.top = node;

    //更新数量
    this.size++;
}
1
2
3
4
5
6
7
8
9
private void button6_Click(object sender, EventArgs e)
{
    MyStack2<string> myStack = new MyStack2<string>();

    //入栈
    myStack.Push("张三");
    myStack.Push("李四");
    myStack.Push("王五");
}

出栈

实现步骤：

  • 判断栈的状态，如果栈已空，不允许出栈
  • 若栈不空，取出top指向的栈顶结点的值
  • 修改top指向新的栈顶结点
  • 栈内数据个数减1
  • 返回出栈数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/// <summary>
/// 出栈
/// </summary>
/// <returns></returns>
/// <exception cref="InvalidOperationException"></exception>
public T Pop()
{
    if (this.IsEmpty())
    {
        throw new InvalidOperationException("栈已空");
    }

    //栈顶数据
    T item = this.top.data;

    //更新栈顶
    this.top = this.top.nextNode;

    this.size--;

    return item;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void button7_Click(object sender, EventArgs e)
{
    MyStack2<string> myStack = new MyStack2<string>();

    //入栈
    myStack.Push("张三");
    myStack.Push("李四");
    myStack.Push("王五");
    myStack.Push("赵六");
    myStack.Push("田七");

    //出栈
    string name= myStack.Pop();  //田七
}

完整代码

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CH05Demo
{
    /// <summary>
    /// 链栈
    /// </summary>
    internal class MyStack2<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        private TNode<T> top;

        /// <summary>
        /// 元素数量
        /// </summary>
        private int size;

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.size == 0;
        }

        /// <summary>
        /// 获取栈的元素个数
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            return this.size;
        }

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="item"></param>
        public void Push(T item)
        {
            //新结点
            TNode<T> node = new TNode<T> { data=item };
            node.nextNode = this.top;

            //更新头节点
            this.top = node;

            //更新数量
            this.size++;
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Pop()
        {
            if (this.IsEmpty())
            {
                throw new InvalidOperationException("栈已空");
            }

            //栈顶数据
            T item = this.top.data;

            //更新栈顶
            this.top = this.top.nextNode;

            this.size--;

            return item;
        }

        /// <summary>
        /// 获取栈顶元素但不移除
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Peek()
        {
            if (this.IsEmpty())
            {
                throw new InvalidOperationException("栈已空");
            }
            return this.top.data;

        }

        public MyStack2() {
            this.size = 0;
        }
    }

    class TNode<T>
    {
        public T data;

        public TNode<T> nextNode;
    }
}

顺序栈与链栈区别

顺序栈

  • 初始时，需要设定固定的存储长度
  • 当堆栈不满时，造成空间的浪费

链栈

  • 存储长度不需要预先设定
  • 在每个结点中，设置了一个指针域，从而产生了结构开销

本章总结

略

课后作业

略