上海交大ACM班C++算法与数据结构——数据结构之栈

上海交大ACM班C++算法与数据结构——数据结构之栈

1.栈的定义

• 后进先出LIFO，first in last out,（先进后出FILO,first in last out）的线性表（有关线性表可查看：上海交大ACM班C++算法与数据结构——数据结构之线性表）
• 基本操作：（由于栈只能在栈顶进行操作，所以基本操作相比普通线性表要少）
  - 建栈
  - 入栈
  - 出栈
  - 读栈（读栈顶元素）
  - 查看栈是否空
• 虚构类实现

		template <class elemType>
		class stack {
			public: 
				virtual bool isEmpty() const = 0; 
				virtual void push(const elemType &x) = 0; 
				virtual elemType pop() = 0;              
				virtual elemType top() const = 0;
				// 虚析构函数防止内存泄漏
				virtual ~stack() {}
		}; 

2.顺序栈

• 一个数组（由于在数组头部操作元素很麻烦，可能引起元素大量移动，所以将数组头部作为栈底，尾部作为栈顶）
• 操作时候要判断一下栈空栈满的情况
• 类定义

		template <class elemType>
		class seqStack: public stack<elemType>{
			private:
				elemType *elem;
				int top_p;
				int maxSize;
				void doubleSpace();
			public:
				seqStack(int initSize = 10)；
				// 析构函数
				~seqStack() { delete [] elem; }
				// 判断栈是否为空，若top_p的值为-1，返回true，否则返回false。
				bool isEmpty() const { return top_p == -1; }      
				void push(const elemType &x) ；
				// 出栈：返回栈顶元素，并把元素数量减1
				elemType pop() { return elem[top_p--]; }
				// top：与pop类似，只是不需要将top_p减1
				elemType top() const { return elem[top_p]; }
		}；

• 构造函数：按照用户估计的栈的规模申请一个动态数组。

		template <class elemType>
		seqStack<elemType>::seqStack(int initSize) {
			elem = new elemType[initSize];
			maxSize = initSize ;
			top_p = -1;  
		}

• push(x) 入栈：将top_p加1，将x放入top_p指出的位置中。但要注意数组满的情况。

		template <class elemType>
		void seqStack<elemType>::push(const elemType &x) { 
			if (top_p == maxSize - 1)
				doubleSpace();
			elem[++top_p] = x; 
		}

• 性能分析：

  • 除了进栈操作以外，所有运算实现的时间复杂度都是O(1)。
  • 进栈运算在最坏情况下的时间复杂度是O(N)。（需要doubleSpace）
  • 均摊分析法：最坏情况在N次进栈操作中至多出现一次，平均到每次进栈操作上也是O(1)的复杂度。

• 例题

  给出两个序列 pushed 和 poped 两个序列，其取值从 1 到n (1 ≤ n ≤ 10^5)。已知入栈序列是1 2 3 … n，如果出栈序列有可能是 poped，则输出Yes，否则输出No。每个测试点有多组数据。

  输入描述：

  第一行一个整数q，询问次数。

  接下来q个询问，对于每个询问：

  第一行一个整数n表示序列长度；

  第二行n个整数表示出栈序列。

  输出描述：

  对于每个询问输出单独一行答案。如可能，则输出Yes；反之，则输出No。

  示例 1：
  输入：
  2
  5
  5 4 3 2 1
  4
  2 4 1 3
  输出：
  Yes
  No

		#include <cstdio>
		#include <cstring>
		#include <iostream>
		#include <algorithm>
		#define N 100005 
		using namespace std;

		int a[N], b[N], s[N], top, n;

		int main() {
			int T;
			scanf("%d", &T);
			for (int i = 0; i <100000; i++)
				a[i] = i + 1;
			while (T--) {
				memset(b, 0, sizeof(b));
				memset(s, 0, sizeof(s));
				scanf("%d", &n);
				for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
				int j = 0;
				top = 0;
				for (int i = 0; i < n; ++i) {
					while (j < n && (!top || s[top - 1] != b[i])) 
						s[top++] = a[j++];
					if (s[top - 1] == b[i]) 
						--top;
				}
				if (!top) printf("Yes\n");
				else printf("No\n");
			}
			return 0;
		}

3.链接栈

• 一个单链表：头指针作为栈顶（链接栈不需要头结点：头结点是为了可以对第一个结点和后续结点进行相同操作而不用分类讨论才设置的，栈只在栈顶操作元素，所以不存在这个问题）
• 类定义

		 template <class elemType>
		class linkStack: public stack<elemType> {
			private:
				struct node {
					elemType  data;
					node *next;
					node(const elemType &x, node *N = NULL) { 
						data = x; 
						next = N;
					}
					node():next(NULL) {}
					~node() {}
				};

				node *top_p;

			public:
				// 构造函数：将top_p设为空指针
				linkStack() { top_p = NULL; }	   
				~linkStack();
				// isEmpty()：判top_p是否为空指针
				bool isEmpty() const { return   top_p == NULL; }
				// push(x)：在表头执行单链表的插入。
				void push(const elemType &x) { op_p = new node(x, top_p); }
				elemType pop();
				// top()：返回top_p指向的结点的值。
				elemType top() const { return top_p->data; }	    
		}; 

• 析构函数：注意需要释放空间。

		template <class elemType>
		linkStack<elemType>::~linkStack() {
			node *tmp;

			while (top_p != NULL) {
				tmp = top_p; 
				top_p = top_p ->next;
				delete tmp;
			}
		}

• pop()：出栈操作，在表头执行单链表的删除。

		template <class elemType>
		elemType linkStack<elemType>::pop() {
			node *tmp = top_p;
			elemType x = tmp->data;              

			top_p = top_p->next;                   
			delete tmp;                          
			return x;
		} 

• 性能分析:所有运算的时间复杂度都是O(1)。

4.用栈实现递归函数

• 例

		void A(){C();D();}
		void B(){D();}
		void C(){B();}
		void D(){}
		int main()
		{
			A();
			C();
		}

		>函数的调用顺序：ACBDDCBD

• 快排
  

		 // 每个node表示要对从left到right这一部分数据进行排序
		struct  node {
			int left;
			int right;
		};

		void quicksort( int a[],  int size) { 
			seqStack <node> st;
			int mid, start, finish;
			node s;

			if (size <= 1) return;

			// 排序整个数组
			s.left = 0; 
			s.right = size - 1;
			st.push(s);
			while (!st.isEmpty())  {
				s = st.pop(); 
				start = s.left;
				finish = s.right; 
				mid = divide(a, start, finish);
				if (mid - start > 1) { 
					s.left = start; 
					s.right = mid - 1; 
					st.push(s); 
				}
				if (finish - mid > 1) { 
					s.left = mid + 1; 
					s.right = finish;
					st.push(s)；
				}
			}
		}

• 练习题：括号配对检测

  假设一个表达式有英文字母（小写）、运算符+ — * /和左右小（圆）括号构成，以@作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回YES；否则返回NO。表达式长度小于255，左圆括号少于20个。

  输入描述：

  一行，输入的表达式。

  输出描述：

  一行，YES或NO

  示例 1：
  输入：
  2*(x+y)/(1-x)@
  输出：
  YES

		 #include <cstdio>
		#include <cstring>
		#include <iostream>
		#include <algorithm>

		using namespace std;

		char s[1010];

		int main() {
			int a = 0;
			scanf("%s", s);
			int len = strlen(s);
			for (int i = 0; i < len; i++) {
				if (s[i] =='(') {
					a++;
				}
				if (s[i] == ')') {
					a--;
					if (a < 0) {
						printf("NO");
						return 0;
					}
				}
			}
			if (a == 0)
				printf("YES");
			else
				printf("NO");
			return 0; 
		}