数据结构-栈的详细整理

傷城~ 2021-07-24 17:48 346阅读 0赞

### 1.栈 ###

1.栈的介绍  
栈（stack）是一种后进先出或者先进后出的数据结构。可以把栈理解为一个箱子，箱子的容量仅供一本书放入或拿出。每次可以把一本书放在箱子的最上方，也可以把最上方的书拿出。用数组st\[\]来模拟栈，常见操作包含清空（clear）,获取栈内元素（size），判断栈是否为空（empty），进栈（push），出栈（pop），获取栈顶元素（top）等。  
2.用数组模拟  
(1) 清空（clear）

void clear()
    { 
       TOP=-1;
    }

(2) 获取栈内元素个数（size）  
栈顶指针TOP始终指向栈顶元素，而数组下标从0开始，因此栈内元素的个数为TOP+1.

int size()
    { 
      return TOP+1;
    }

(3) 判空（empty）  
当且仅当TOP==-1时栈空，返回true,否则，返回false。

bool empty()
    { 
       if(TOP==-1) return true;
       else return false;
    }

(4) 进栈（push）  
push（x）操作将元素x置于栈顶，而此时栈顶指针TOP指向栈顶元素，因此需要先把TOP加1，然后再把x  
存入TOP指向的位置。

void push(int x)
    { 
        st[++TOP]=x;
    }

(5) 出栈（pop）  
pop（）操作将栈顶元素出栈，而事实上可以将栈顶指针TOP减1来实现这个效果。

int pop()
    {   
        TOP--;
    }

(6) 取栈顶元素（top）  
由于栈顶指针TOP始终指向栈顶操作，因此可以st\[TOP\]即为栈顶元素。

int top()
    { 
        return st[TOP];
    }

提示：出栈和取出栈顶元素的操作必须在栈非空的情形下才能使用，在使用pop()函数和top()函数之前必须先使用empty()函数判断栈是否为空。  
这里给出栈的模板：

// TOP表示栈顶
    int stk[N], TOP = 0;
    
    // 向栈顶插入一个数
    stk[ ++ TOP] = x;
    
    // 从栈顶弹出一个数
    TOP -- ;
    
    // 栈顶的值
    stk[TOP];
    
    // 判断栈是否为空
    if (TOP > 0)
    { 
    
    }

题目练习  
**实现一个栈，栈初始为空，支持四种操作：**

(1) “push x” – 向栈顶插入一个数x；

(2) “pop” – 从栈顶弹出一个数；

(3) “empty” – 判断栈是否为空；

(4) “query” – 查询栈顶元素。

现在要对栈进行M个操作，其中的每个操作3和操作4都要输出相应的结果。

输入格式  
第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令为”push x”，”pop”，”empty”，”query”中的一种。

输出格式  
对于每个”empty”和”query”操作都要输出一个查询结果，每个结果占一行。

其中，”empty”操作的查询结果为“YES”或“NO”，”query”操作的查询结果为一个整数，表示栈顶元素的值。

数据范围  
1≤M≤100000,  
1≤x≤109  
所有操作保证合法。

**输入样例：**  
10  
push 5  
query  
push 6  
pop  
query  
pop  
empty  
push 4  
query  
empty  
**输出样例：**  
5  
5  
YES  
4  
NO  
**代码**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 1e5 + 10;
    int st[maxn];
    int main()
    { 
    	int M,TOP=0;
    	cin >> M;
    	while (M--)
    	{ 
    		string str;
    		int x;
    		cin >> str;
    		if (str == "push")
    		{ 
    			cin >> x;
    			st[++TOP] = x;
    		}
    		else if(str == "query")
    		{ 
    			cout << st[TOP] << endl;
    		}
    		else if (str == "pop")
    		{ 
    			TOP--;
    		}
    		else if (str == "empty")
    		{ 
    			if (TOP > 0)
    			{ 
    				cout << "NO" << endl;
    			}
    			else
    			{ 
    				cout << "YES" << endl;
    			}
    		}
    	}
    	return 0;
    }

**STL中stack常用函数解析**  
(1) push()  
push(x)将x入栈，时间复杂度为O(1).  
(2) top()  
top()获得栈顶元素，时间复杂度为O(1).  
(3) pop()  
pop()用以弹出栈顶元素，时间复杂度为O(1).  
示例如下

#include<iostream>
    #include<stack>
    using namespace std;
    int main()
    { 
    	stack<int>st;
    	for (int i = 1; i <= 5; i++)
    	{ 
    		st.push(i); //将 1 2 3 4 5 一次入栈
    	}
    	for (int i = 1; i <= 3; i++)
    	{ 
    		st.pop(); //连续三次将栈顶元素出栈，即将5 4 3 依次出栈
    	}
    	cout << st.top() << endl;  //输出2
    	return 0; 
    }

(4) empty()  
empty()可以检测stack内是否为空，为空返回true,否则返回false，时间复杂度为O(1)。  
(5) size()  
size()返回stack内元素的个数，时间复杂度为O(1)。  
示例如下

#include<iostream>
    #include<stack>
    using namespace std;
    int main()
    { 
    	stack<int>st;
    	if (st.empty() == 1)
    	{ 
    		cout << "YES" << endl;//刚开始栈内没有元素，因此为空。
    	}
    	for (int i = 1; i <= 5; i++)
    	{ 
    		st.push(i);
    	}
    	cout << st.size() << endl; //栈内有5个元素，因此输出5
    }