栈(Stack)
栈就是一种只允许在表尾进行插入和删除操作的线性表
is a linear data structure which operates in a LIFO(last in first out) or FILO(first in last out) pattern
如何理解栈的概念
① 举一个生活中的例子：我在一个储物箱中，堆了一堆衣服，我的一件球衣在最下面，而我要拿这件衣服，就意味着我必须将上面的衣服全部拿出来才可以，但是由于箱子只有一个口，我也只能从上面拿东西，心里还默默想着，当初就不该将球衣早早的放进去，导致结果就是先进后出！
栈的术语说明
栈顶：允许进行插入和进行删除操作的一段成为栈顶
栈底：表的另一端称为栈底 （第一个元素进入的位置）
压栈：在栈顶位置插入元素的操作叫做压栈，或入栈、进栈
出栈：删除栈顶元素的操作叫做出栈，也叫作弹栈，或者退栈
空栈：不含元素的空表
栈溢出：当栈满的时候，如果再有元素压栈，则发生上溢，当栈空的时候，再出栈则发生下溢
栈的常见分类：
（1）基于数组的栈——以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向
（2）基于单链表的栈——以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的新节点将一直出现在链表的头部
使用标准库的栈时, 应包含相关头文件，在栈中应包含头文件： #include< stack > 。定义：stack< int > s;
一、基于数组的栈的实现
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 | /* stack */ #include <iostream> using namespace std; int top=-1; int arr[5]={0}; bool isEmpty() { if(top==-1)return true; else return false; } bool isFull() { if(top==4)return true; else return false; } void push(int value) { if(isFull()) { cout<<"stack overFlow"<<endl; } else { top++; arr[top]=value; } } int pop(){ if(isEmpty()) { cout<<"stack underflow"<<endl; return 0; } else { int popValue=arr[top]; arr[top]=0; top--; return popValue; } } int count(){ return top+1; } int peek(int pos){ if(isEmpty()) { cout<<"stack underflow"<<endl; return 0; } else { return arr[pos]; } } void change(int pos,int value) { arr[pos]=value; cout<<"item changed at location"<<pos<<endl; } void display() { cout<<"all values in the stack are "<<endl; for (int i = top; i >=0; i--) { cout<<arr[i]<<' '; } cout<<endl; } int main() { int option,position,value; do{ cout<<"what operation do you want to perform? select option number."<<endl; cout<<"0. exit"<<endl; cout<<"1.push"<<endl; cout<<"2.pop"<<endl; cout<<"3.isEmpty"<<endl; cout<<"4.isFull"<<endl; cout<<"5.peek"<<endl; cout<<"6.cout"<<endl; cout<<"7.change"<<endl; cout<<"8.display"<<endl; cin>>option; switch(option) { case 0: break; case 1: cout<<"enter an item to push in the stack"<<endl; cin>>value; push(value); break; case 2: cout<<"pop function called \n poped value: "<<pop()<<endl; break; case 3: if(isEmpty())cout<<"stack is empty"<<endl; else cout<<"stack is not empty"<<endl; break; case 4: if(isFull())cout<<"stack is Full"<<endl; else cout<<"stack is not Full"<<endl; break; case 5: cout<<"enter position of item you want to peek: "<<endl; cin>>position; cout<<"peek function called value at position "<<position<<"is "<<peek(position)<<endl; break; case 6: cout<<"count function called,Number of Item in the stack are:"<<count()<<endl; break; case 7: cout<<"change function called"; cout<<"enter position of Item you want to change:"; cin>>position; cout<<endl; cout<<"enter value of Item you want to change: "; cin>>value; change(position,value); break; case 8: cout<<"display function called: "<<endl; display(); break; default: cout<<"enter proper option Number"<<endl; } }while(option!=0); return 0; } |
二、基于链表的栈实现
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 | /**************************************************************** * C++ Stack implement using linkedlist * date: 2023-3-3 * author : Alex Li * version : 1.2 * ****************************************************************/ #include<iostream> using namespace std; //结点定义 struct Node{ int data;//数据域 Node *next;//指针域 }; Node *St=NULL;//定义指针，指向栈顶 //判断栈是否为空 bool IsEmpty(Node *S){ if (S == NULL)return true; else return false; } //入栈 void Push(Node *S, int x){ Node *NewNode;//新结点 NewNode = new Node;//新结点申请内存 NewNode->data = x;//新结点数据域赋值 NewNode->next = NULL;//新结点指针域赋值 if (IsEmpty(S)){//如果链栈为空 S= NewNode;//链栈顶指针指向新结点 } else{//如果链栈非空 NewNode->next = S;//新结点前插入链栈 S= NewNode;//更新栈顶指针 } St=S; } //出栈 void Pop(Node *S){ int x; if (IsEmpty(S)) { cout << "栈空,无法出栈" << endl; return; //什么都不做 } Node *p = S;//定义探测指针p并指向栈顶结点 if (p->next == NULL){//如果链栈仅含一个结点 x = p->data;//获取栈顶结点值 S = NULL;//置链栈为空 delete p;//删除原栈顶结点 } else{//如果链栈中至少含有两个结点 x = p->data;//获取栈顶结点值 S = S->next;//栈顶指针后移 delete p;//删除原栈顶结点 } cout<<"the value of pop element is: "<<x<<endl; St=S; } //输出链栈 void Display(Node *S){ if (IsEmpty(S))//如果链栈为空 { cout << "栈空,无结点输出" << endl; return;//什么都不做 } Node *p = S;//定义探测指针p并指向栈顶结点 while (p != NULL) { cout << p->data << "=>";//输出栈顶结点值 p = p->next;//p后移 } cout << "NULL" << endl; } //主程序 int main(){ Push(St, 1);//入栈 Push(St, 2);//入栈 Display(St); Pop(St);//出栈 Display(St); Push(St, 3); //入栈 Display(St); } |
pop: to put or take something quickly 迅速地拿；快速地放
peek: to look at something for a shorttime 匆匆一瞥
表达式求值
题目描述
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。
输入格式
一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 + 和乘法运算符 *，且没有括号，所有参与运算的数字均为 0 到 231−1 之间的整数。
输入数据保证这一行只有 0123456789+* 这 12 种字符。
输出格式
一个整数，表示这个表达式的值。
注意：当答案长度多于 4 位时，请只输出最后 4 位，前导 0 不输出。
输入输出样例
输入 #1
1+1*3+4
输出 #1
8
输入 #2
1+1234567890*1
输出 #2
7891
输入 #3
1+1000000003*1
输出 #3
4
说明/提示
对于 30%的数据，0≤0≤ 表达式中加法运算符和乘法运算符的总数 ≤100。
对于 80% 的数据，0≤0≤ 表达式中加法运算符和乘法运算符的总数 ≤1000。
对于 100% 的数据，0≤0≤ 表达式中加法运算符和乘法运算符的总数 ≤100000。
[NOIP2013-2 普及组] [P1981][1660]
题目：计算表达式的值[acwing3302]
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
- 数据保证给定的表达式合法。
- 题目保证符号
-只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2)之类表达式均不会出现。 - 题目保证表达式中所有数字均为正整数。
- 题目保证表达式在中间计算过程以及结果中，均不超过 2^31−1。
- 题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
输入格式
共一行，为给定表达式。
输出格式
共一行，为表达式的结果。
数据范围
表达式的长度不超过 10^5。
输入样例：
(12/3+2)*(13-2*3)输出样例：
42