0%

数据结构-栈和队列（一）栈

发表于 更新于 分类于
本文字数： 6.9k 阅读时长 ≈ 6 分钟

数据结构

栈和队列（一）栈

思维导图

1 栈的基本概念

1、概念

栈（Stack）是只允许在一端进行插入或删除操作的线性表

  • “先入后出”（FILO）原则

  • 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。只允许进行插入和删除操作，允许插入和删除的一端，为变化的一端，称为栈顶（Top）,另一端为固定的一端，称为栈底（Bottom）。

  • 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

2、基本操作

线性表基本操作

InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作：

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

栈的基本操作

InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。

DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。

Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。

Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

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

其他常用操作：

StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。

3、卡特兰数

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
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<windows.h>
#define MaxSize 10
using namespace std;

typedef struct{
    int data[MaxSize];  //静态数组存放栈中元素
    int top;  //栈顶指针
}SqStack;

/**
 * @description: 初始化栈
 * @param {SqStack} &S
 * @return {*}
 */
void initStack(SqStack &S) {
    S.top = -1;  //初始化栈顶指针
}

/**
 * @description: 判断栈是否空
 * @param {SqStack} S
 * @return {*}
 */
bool isEmpty(SqStack S) {
    return S.top == -1;
}

/**
 * @description: 判断栈是否满
 * @param {SqStack} S
 * @return {*}
 */
bool isFull(SqStack S) {
    return S.top == MaxSize - 1;
}

/**
 * @description: 入栈
 * @param {SqStack} &S
 * @param {int} e
 * @return {*}
 */
bool Push(SqStack &S, int e) {
    if (isFull(S))
        return false;
    S.top++;  //指针加一
    S.data[S.top] = e;  //入栈
    return true;    
}

/**
 * @description: 出栈
 * @param {SqStack} &S
 * @param {int} &e
 * @return {*}
 */
bool Pop(SqStack &S, int &e) {
    if(isEmpty(S))
        return false;
    e = S.data[S.top];
    S.top--;  
    return true;  
}

/**
 * @description: 取栈顶元素
 * @param {SqStack} S
 * @return {*}
 */
int GetTop(SqStack S) {
    if(isEmpty(S)) 
        return false;
    return S.data[S.top];
}

/**
 * @description: 输出栈
 * @param {SqStack} S
 * @return {*}
 */
void printStack(SqStack S) {
    if(isEmpty(S))
        return;
    for(int i = S.top; i >= 0; i--)
        cout << "stack[" << i  << "] = " << S.data[i] <<endl;
}
int main() {
    SqStack S; //初始化
    initStack(S); 
    bool loop = true;
    while (loop)
    {
        system("pause");
        system("cls");
        cout << "欢迎进行栈的操作，请按指定序号操作，考研顺利！" << endl;
        cout << "---------------------菜单---------------------" << endl;
        cout << "1、入栈" << endl;
        cout << "2、出栈" << endl;
        cout << "3、输出栈" << endl;
        cout << "4、查看栈顶元素" << endl;
        cout << "0、退出" << endl;
        int num;
        cout << "请选择序号：" ;
        cin >> num;
        switch (num)
        {
        case 1:
            if (isFull(S)) {
                cout << "栈满" << endl;
            } else {
                int e;
                cout << "请输入数据：" ;
                cin >> e;
                Push(S, e);
            }

                break;
        case 2:
            if (isEmpty(S))
            {
                cout << "栈空" << endl;
            }
            else
            {
                int e = -1;
                Pop(S, e);
                cout << "出栈的数据为：" << e << endl;
            }
            break;
        case 3:
            if(isEmpty(S))
                cout << "栈空" << endl;
            else
                printStack(S);
            break;
        case 4:
            if (isEmpty(S))
            {
                cout << "栈空" << endl;
            }else {
                cout << "栈顶的数据为： " << GetTop(S) << endl;
            }
            break;
        case 0:
            loop = false;
            break;
        case 6:

            break;
        default:
            break;
        }
        
    }
    return 0;
}

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
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

typedef struct LinkNode {
    int data;
    int length;
    LinkNode *next;
}*LinkStack;

/**
 * @description: 初始化栈
 * @param {LinkStack} &S
 * @return {*}
 */
bool initStack(LinkStack &S)
{
//    LinkStack *L; //初始化栈顶指针
   S = (LinkNode *)malloc(sizeof(LinkNode));
   if(S == NULL) 
     return false;
   S->next = NULL;
   S->length = 0;
   return true;
}

/**
 * @description: 判断栈是否空
 * @param {LinkStack} S
 * @return {*}
 */
bool isEmpty(LinkStack S)
{
    return S->next == NULL;
}


/**
 * @description: 入栈 -- 头插法
 * @param {LinkStack} &S
 * @param {int} e
 * @return {*}
 */
bool Push(LinkStack &S, int e)
{
    LinkNode *t;
    t = (LinkNode *)malloc(sizeof(LinkNode));
    t->data = e;
    if(isEmpty(S))
        t->length = 1;
    else
        t->length = S->next->length + 1;    
    t->next = S->next;
    S->next = t;   
    return true;
}

/**
 * @description: 出栈
 * @param {LinkStack} &S
 * @param {int} &e
 * @return {*}
 */
bool Pop(LinkStack &S, int &e)
{
    if (isEmpty(S))
        return false;
    LinkNode *p = S->next;    
    e = p->data;
    S->next = p->next;
    free(p);    
    return true;
}

/**
 * @description: 取栈顶元素
 * @param {LinkStack} S
 * @return {*}
 */
int GetTop(LinkStack S)
{
    if (isEmpty(S))
        return false;
    return S->next->data;
}

/**
 * @description: 输出栈
 * @param {LinkStack} S
 * @return {*}
 */
void printStack(LinkStack S)
{
    if (isEmpty(S))
        return;
    LinkNode *t = S->next;    
    while(t != NULL) {
        cout << "stack [" << t->length << "] = " << t->data << endl;
        t = t->next;
    }    
    
}

/**
 * @description: 获取链长
 * @param {LinkStack} S
 * @return {*}
 */
int GetLength(LinkStack S) {
    if(isEmpty(S))
        return 0;
    else
        return S->next->length;    
}
int main()
{
    LinkStack S; //初始化
    initStack(S);
    bool loop = true;
    while (loop)
    {
        cout << "\n" << endl;
        system("pause");
        system("cls");
        cout << "欢迎进行栈的操作，请按指定序号操作，考研顺利！" << endl;
        cout << "---------------------菜单---------------------" << endl;
        cout << "1、入栈" << endl;
        cout << "2、出栈" << endl;
        cout << "3、输出栈" << endl;
        cout << "4、查看栈顶元素" << endl;
        cout << "5、查看链长" << endl;
        cout << "0、退出" << endl;
        int num;
        cout << "请选择序号：";
        cin >> num;
        switch (num)
        {
        case 1:
        
            int e;
            cout << "请输入数据：";
            cin >> e;
            Push(S, e);
            break;
        case 2:
            if (isEmpty(S))
            {
                cout << "栈空" << endl;
            }
            else
            {
                int e = -1;
                Pop(S, e);
                cout << "出栈的数据为：" << e << endl;
            }
            break;
        case 3:
            if (isEmpty(S))
                cout << "栈空" << endl;
            else
                printStack(S);
            break;
        case 4:
            if (isEmpty(S))
            {
                cout << "栈空" << endl;
            }
            else
            {
                cout << "栈顶的数据为： " << GetTop(S) << endl;
            }
            break;
        case 5:
            cout << "链长为：" << GetLength(S) << endl;
            break;    
        case 0:
            loop = false;
            break;
        default:
            break;
        }
    }
    return 0;
}

程序效果

北以晨光 wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！
------ 本文结束感谢您的阅读 ------
相关文章