堆栈(stack)是一组类型相同数据的组合(如数组)。具有先进后出的特性,所有的操作都在栈顶进行。
“heap和stack区别:1、heap是堆,stack是栈;2、stack的空间由操作系统自动分配和释放,heap的空间是手动申请和释放的;3、stack空间有限,heap的空间是很大的自由区。”
stack相对速度快。
// // Ch04_01 // #include <iostream> #include <iomanip> #define MAXSTACK 100 //定义堆栈的最大容量 using namespace std; int stack[MAXSTACK]; //声明用于堆栈操作的数组 int top=-1; //堆栈的顶端 //判断是否为空堆栈 int isEmpty() { if(top==-1) return 1; else return 0; } //将指定的数据压入堆栈 int push(int data) { if(top>=MAXSTACK) { cout<<"堆栈已满,无法再压入"<<endl; return 0; } else { stack[++top]=data; //将数据压入堆栈 return 1; } } //从堆栈弹出数据 int pop() { if(isEmpty()) //判断堆栈是否为空,如果是则返回-1 return -1; else return stack[top--]; //将数据弹出后,再将堆栈指针往下移 } //主程序 int main(void) { int value; int i; cout<<"请按序输入10个数据:"<<endl; for(i=0;i<10;i++) { cin>>value; push(value); } cout<<"===================="<<endl; while(!isEmpty()) //将数据陆续从顶端弹出 cout<<"堆栈弹出的顺序为:"<<setw(2)<<pop()<<endl; cout<<"===================="<<endl; system("pause"); return 0; }
// // Ch04_02 // #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; void Swap(int*,int*); void push(int statck[],int MAX,int val); int pop(int stack[]); int top=-1; int main(void) { int card[52],stack[52]={0}; int i,j,k=0, ascVal; char suit[4][10]={"草花","方块","红桃","黑桃"}; int style; srand((unsigned)time(NULL)); for (i=0;i<52;i++) card[i]=i+1; cout<<"[洗牌中...请稍后!]"<<endl; while(k<30) { for(i=0;i<51;i++) for(j=i+1;j<52;j++) if(rand()%52==2) Swap(&card[i],&card[j]);//洗牌 k++; } i=0; while(i!=52) { push(stack,52,card[i]);//将52张牌压入堆栈 i++; } cout<<"[逆时针发牌]"<<endl; cout<<"[显示各家拿到的牌]"<<endl; cout<<"\t\t东家\t 北家\t 西家\t 南家"<<endl; cout<<"========================================================="<<endl; while (top >=0) { style = stack[top]/13; //计算扑克牌的花色 switch(style) //扑克牌花色对应的图标 { case 0: //梅花 ascVal=0; break; case 1: //方块 ascVal=1; break; case 2: //红心 ascVal=2; break; case 3: //黑桃 ascVal=3; break; } cout<<"["<<suit[ascVal]<<setw(3)<<stack[top]%13+1<<"]\t"; if(top%4==0) cout<<endl; top--; } system("pause"); return 0; } void push(int stack[],int MAX,int val) { if(top>=MAX-1) cout<<"[堆栈已经满了]"<<endl; else { top++; stack[top]=val; } } int pop(int stack[]) { if(top<0) cout<<"[堆栈已经空了]"<<endl; else top--; return stack[top]; } void Swap(int* a,int* b) { int temp; temp=*a; *a=*b; *b=temp; }
// // Ch04_03 // #include <iostream> #include <cstdlib> #include <iomanip> using namespace std; class Node //声明堆栈链表节点 { public: int data; //声明存放堆栈数据的变量 class Node *next; //堆栈中用来指向下一个节点的指针 }; typedef class Node Stack_Node; //定义堆栈中节点的新类型 typedef Stack_Node *Linked_Stack; //定义链表堆栈的新类型 Linked_Stack top=NULL; //指向堆栈顶端的指针 //判断是否为空堆栈 int isEmpty() { if(top==NULL) return 1; else return 0; } //将指定的数据压入堆栈 void push(int data) { Linked_Stack new_add_node; //新加入节点的指针 //分配内存给新节点 new_add_node=new Stack_Node; new_add_node->data=data; //将传入的值赋值给节点的数据变量 new_add_node->next=top; //将新节点指向堆栈的顶端 top=new_add_node; //新节点成为堆栈的顶端 } //从堆栈弹出数据 int pop() { Linked_Stack ptr; //指向堆栈顶端的指针 int temp; if(isEmpty()) //判断堆栈是否为空,如果是则返回-1 { cout<<"===目前为空堆栈==="<<endl; return -1; } else { ptr=top; //指向堆栈的顶端 top=top->next; //将堆栈顶端的指针指向下一个节点 temp=ptr->data; //取出堆栈的数据 free(ptr); //将节点占用的内存释放 return temp; //将从堆栈取出的数据返回给主程序 } } //主程序 int main(void) { int value; int i; cout<<"请按序输入10个数据:"<<endl; for(i=0;i<10;i++) { cin>>value; push(value); } cout<<"===================="<<endl; while(!isEmpty()) //将数据陆续从顶端弹出 cout<<"堆栈弹出的顺序为:"<<setw(2)<<pop()<<endl; cout<<"===================="<<endl; system("pause"); return 0; }
// // Ch04_04 // #include <iostream> #include <cstdlib> using namespace std; template <class Type> // 定义链表中的节点 struct Node { Type data; // 记录数据 Node* next;// 记录下一笔节点的地址 }; template <class Type> class LinkedList // 链表类型 { private: Node<Type>* first; // 指到第一个节点的指针 public: LinkedList() // 构造函数 { first = NULL; } void addNode(Type data); // 加入节点 void display(); // 显示所有的节点 }; template<class Type> void LinkedList<Type>::addNode(Type data) { Node<Type>* newNode = new Node<Type>; // 新增一个节点 newNode->data = data; // 记录数据 newNode->next = first; // 指向前一个节点 first = newNode; // 指向新的节点 } template<class Type> void LinkedList<Type>::display() { Node<Type>* currentNode = first; // 从第一个节点开始显示 while( currentNode != NULL ) { cout << currentNode->data << " -> "; currentNode = currentNode->next; } } int main() { LinkedList<double> dblList; // 建立一个存储double类型数据的链表 double num; // 记录输入的数据 char ch; // 记录用户的选择 do{ cout << endl <<"请输入一个数字 : "; cin >> num; dblList.addNode( num ); cout << "继续输入(y / n)?"; cin >> ch; }while( ch != 'n' ); cout << endl; dblList.display(); // 显示所有的数据 cout << endl << endl; system("pause"); return 0; }
// // Ch04_05 // #include <iostream> #include <cstdlib> using namespace std; // 设定类样版的类型参数Type的默认值为整数int,非类型参数的类型为整数int,默认值为5 template <class Type = int, int size = 5> // 声明类样板 class Stack { private: Type st[size]; // 声明一数组作为堆栈的存储空间 int top; // 堆栈数据顶端的索引 public: Stack() { top = -1; } void push(Type data); // 将数据压入堆栈 Type pop(); // 将数据从堆栈中弹出 }; template < class Type, int size > void Stack< Type, size > :: push ( Type data ) { st[ ++top ] = data; } template < class Type, int size > Type Stack<Type, size> :: pop() { return st[ top-- ]; } int main() { Stack<> stk_1; // 声明一个堆栈对象, 并使用其默认值 Stack<char*, 4> stk_2; // 声明堆栈对象, 其类型为字符串, 大小为4 stk_1.push( 11 ); stk_1.push( 22 ); stk_1.push( 33 ); cout << "stack_1 [1] = " << stk_1.pop() << endl; cout << "stack_1 [2] = " << stk_1.pop() << endl; cout << "stack_1 [3] = " << stk_1.pop() << endl; cout << endl; stk_2.push( "第一名" ); stk_2.push( "第二名" ); stk_2.push( "第三名" ); cout << "stack_2 [1] = " << stk_2.pop() << endl; cout << "stack_2 [2] = " << stk_2.pop() << endl; cout << "stack_2 [3] = " << stk_2.pop() << endl; cout << endl; system("pause"); return 0; }
// // Ch04_06 // #include <iostream> #define EAST MAZE[x][y+1] //定义东方的相对位置 #define WEST MAZE[x][y-1] //定义西方的相对位置 #define SOUTH MAZE[x+1][y] //定义南方的相对位置 #define NORTH MAZE[x-1][y] //定义北方的相对位置 using namespace std; const int ExitX = 8; //定义出口的X坐标在第8行 const int ExitY = 10; //定义出口的Y坐标在第10列 struct list { int x,y; struct list* next; }; typedef struct list node; typedef node* link; int MAZE[10][12] = { 1,1,1,1,1,1,1,1,1,1,1,1, //声明迷宫数组 1,0,0,0,1,1,1,1,1,1,1,1, 1,1,1,0,1,1,0,0,0,0,1,1, 1,1,1,0,1,1,0,1,1,0,1,1, 1,1,1,0,0,0,0,1,1,0,1,1, 1,1,1,0,1,1,0,1,1,0,1,1, 1,1,1,0,1,1,0,1,1,0,1,1, 1,1,1,1,1,1,0,1,1,0,1,1, 1,1,0,0,0,0,0,0,1,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1}; link push(link stack,int x,int y); link pop(link stack,int* x,int* y); int chkExit(int ,int ,int,int); int main(void) { int i,j; link path = NULL; int x=1; //入口的X坐标 int y=1; //入口的Y坐标 cout<<"[迷宫的路径(0的部分)]"<<endl; //打印出迷宫的路径图 for(i=0;i<10;i++) { for(j=0;j<12;j++) cout<<MAZE[i][j]<<" "; cout<<endl; } while(x<=ExitX&&y<=ExitY) { MAZE[x][y]=2; if(NORTH==0) { x -= 1; path=push(path,x,y); } else if(SOUTH==0) { x+=1; path=push(path,x,y); } else if(WEST==0) { y-=1; path=push(path,x,y); } else if(EAST==0) { y+=1; path=push(path,x,y); } else if(chkExit(x,y,ExitX,ExitY)==1) //检查是否走到出口了 break; else { MAZE[x][y]=2; path=pop(path,&x,&y); } } cout<<"[老鼠走过的路径(2的部分)]"<<endl; //打印出老鼠成功走出迷宫的路径图 for(i=0;i<10;i++) { for(j=0;j<12;j++) cout<<MAZE[i][j]<<" "; cout<<endl; } system("pause"); return 0; } link push(link stack,int x,int y) { link newnode; newnode = new node; if(!newnode) { cout<<"Error!内存分配失败!"<<endl; return NULL; } newnode->x=x; newnode->y=y; newnode->next=stack; stack=newnode; return stack; } link pop(link stack,int* x,int* y) { link top; if(stack!=NULL) { top=stack; stack=stack->next; *x=top->x; *y=top->y; delete top; return stack; } else *x=-1; return stack; } int chkExit(int x,int y,int ex,int ey) { if(x==ex&&y==ey) { if(NORTH==1||SOUTH==1||WEST==1||EAST==2) return 1; if(NORTH==1||SOUTH==1||WEST==2||EAST==1) return 1; if(NORTH==1||SOUTH==2||WEST==1||EAST==1) return 1; if(NORTH==2||SOUTH==1||WEST==1||EAST==1) return 1; } return 0; }
// // Ch04_07 // #include <iostream> #include <iomanip> #include <cmath> #define EIGHT 8 //定义堆栈的最大容量 #define TRUE 1 #define FALSE 0 using namespace std; int queen[EIGHT]; //存放8个皇后的行位置 int number=0; //计算总共有几组解 //决定皇后存放的位置 //输出所需要的结果 int attack(int ,int); void print_table() { int x=0,y=0; number+=1; cout<<endl; cout<<"八皇后问题的第"<<setw(2)<<number<<"组解"<<endl<<"\t"; for(x=0;x<EIGHT;x++) { for(y=0;y<EIGHT;y++) if(x==queen[y]) cout<<"<q>"; else cout<<"<->"; cout<<endl<<"\t"; } system("pause"); } void decide_position(int value) { int i=0; while(i<EIGHT) { //是否受到攻击的判断语句 if(attack(i,value)!=1) { queen[value]=i; if(value==7) print_table(); else decide_position(value+1); } i++; } } //测试在(row, col)上的皇后是否遭受攻击 //若遭受攻击则返回值为1,否则返回0 int attack(int row,int col) { int i=0,atk=FALSE; int offset_row=0,offset_col=0; while((atk!=1)&&i<col) { offset_col=abs(i-col); offset_row=abs(queen[i]-row); //判断两皇后是否在同一行或在同一对角线 if((queen[i]==row)||(offset_row==offset_col)) atk=TRUE; i++; } return atk; } //主程序 int main(void) { decide_position(0); return 0; }
/* // Ch04_08 [示范]:将数学表达式由中序表示法转为后序表示法 */ #include <iostream> #include <cstdlib> #include <iomanip> using namespace std; #define MAX 50 char infix_q[MAX]; //用来存放中序表示法的队列 //运算符优先级的比较,若输入运算符的优先级小于堆栈中运算符的优先级, //则返回值为1,否则为0 int compare(char stack_o, char infix_o) { //在中序表示法队列和暂存堆栈中,运算符的优先级表, //其优先级值为INDEX/2 char infix_priority[9] ; char stack_priority[8] ; int index_s=0, index_i=0; infix_priority[0]='q';infix_priority[1]=')'; infix_priority[2]='+';infix_priority[3]='-'; infix_priority[4]='*';infix_priority[5]='/'; infix_priority[6]='^';infix_priority[7]=' '; infix_priority[8]='('; stack_priority[0]='q';stack_priority[1]='('; stack_priority[2]='+';stack_priority[3]='-'; stack_priority[4]='*';stack_priority[5]='/'; stack_priority[6]='^';stack_priority[7]=' '; while (stack_priority[index_s] != stack_o) index_s++; while (infix_priority[index_i] != infix_o) index_i++; return ((int)(index_s/2) >= (int)(index_i/2) ? 1 : 0); } //中序转前序的方法 void infix_to_postfix() { int rear=0, top=0, flag=0,i=0; char stack_t[MAX]; for (i=0; i<MAX; i++) stack_t[i]='\0'; gets(infix_q); i=0; while(infix_q[i]!='\0') { i++; rear++; } infix_q[rear] = 'q'; //在队列加入q为结束符号 cout<<"\t"<<"后序表示法 : "; stack_t[top] = 'q'; //在堆栈加入q为结束符号 for (flag = 0; flag <= rear; flag++)\ { switch (infix_q[flag]) { //输入为)时,则输出堆栈内的运算符,直到堆栈内为( case ')': while(stack_t[top]!='(') cout<<setw(1)<<stack_t[top--]; top--; break; //输入为q,则将堆栈内还未输出的运算符输出 case 'q': while(stack_t[top]!='q') cout<<setw(1)<<stack_t[top--]; break; //输入为运算符,若其优先级小于TOP在堆栈中所指运算符的优先级, //则将堆栈所指运算符输出,若优先级大于等于TOP在堆栈中所指运算符 //的优先级,则将输入的运算符压入堆栈。 case '(': case '^': case '*': case '/': case '+': case '-': while (compare(stack_t[top], infix_q[flag])==1) cout<<setw(1)<<stack_t[top--]; stack_t[++top] = infix_q[flag]; break; //输入为操作数,则直接输出 default : cout<<setw(1)<<infix_q[flag]; break; } } } //主函数声明 int main (void) { int i=0; for (i=0; i<MAX; i++) infix_q[i]='\0'; cout<<"\t=========================================="<<endl; cout<<"\t本程序会将其转成后序法表达式"<<endl; cout<<"\t请输入中序法表达式"<<endl; cout<<"\t例如:(9+3)*8+7*6-8/4 "<<endl; cout<<"\t可以使用的运算符包括:^,*,+,-,/,(,)等 "<<endl; cout<<"\t=========================================="<<endl; cout<<"\t请开始输入中序法表达式: "; infix_to_postfix(); cout<<endl; cout<<"\t=========================================="<<endl; system("pause"); return 0; }
/* // Ch04_09 [示范]:实现队列数据的进队和出队 */ #include <iostream> using namespace std; const int MAX=20;//定义队列的大小 int main(void) { int front,rear,val,queue[MAX]={0}; char ch; front=rear=-1; while(rear<MAX-1&&ch!='E') { cout<<"[I]存入一个数值 [G]取出一个数值 [E]结束: "; cin>>ch; switch(ch) { case 'I': cout<<"[请输入数值]: "; cin>>val; rear++; queue[rear]=val; break; case 'G': if(rear>front) { front++; cout<<"[取出数值为]: ["<<queue[front]<<"]"; cout<<endl; queue[front]=0; } else { cout<<"[队列已经空了]"<<endl; exit(0); } break; default: cout<<endl; break; } } if(rear==MAX-1) cout<<"[队列已经满了]"<<endl; cout<<"[目前队列中的数据]:"; if (front>=rear) { cout<<"没有"<<endl; cout<<"[队列已经空了]"<<endl; } else { while (rear>front) { front++; cout<<"["<<queue[front]<<"]\t"; } cout<<endl; } system("pause"); return 0; }
/* // Ch04_10 [示范]:以链表来实现队列 */ #include <iostream> #include <cstdlib> #include <iomanip> using namespace std; class Node { public: int data; class Node *next; }; typedef class Node QueueNode; typedef QueueNode *QueueByLinkedList; QueueByLinkedList front=NULL; QueueByLinkedList rear=NULL; //方法enqueue:数据的加入队列 void enqueue(int value) { QueueByLinkedList node; //建立节点 node=new QueueNode; node->data=value; node->next=NULL; //检查是否为空队列 if (rear==NULL) front=node; //新建立的节点成为第1个节点 else rear->next=node; //将节点加入到队列的末尾 rear=node; //将队列的末尾指针指向新加入的节点 } //方法dequeue:从队列取出数据 int dequeue() { int value; //检查队列是否为空队列 if (!(front==NULL)) { if(front==rear) rear=NULL; value=front->data; //从队列取出数据 front=front->next; //将队列的前端指针指向下一个 return value; } else return -1; } int main(void) { int temp; cout<<" 以链表来实现队列"<<endl; cout<<"===================================="<<endl; cout<<"在队列前端加入第1个数据,此数据值为1"<<endl; enqueue(1); cout<<"在队列前端加入第2个数据,此数据值为3"<<endl; enqueue(3); cout<<"在队列前端加入第3个数据,此数据值为5"<<endl; enqueue(5); cout<<"在队列前端加入第4个数据,此数据值为7"<<endl; enqueue(7); cout<<"在队列前端加入第5个数据,此数据值为9"<<endl; enqueue(9); cout<<"===================================="<<endl; while (1) { if (!(front==NULL)) { temp=dequeue(); cout<<"从队列前端按序取出的元素数据值为:"<<setw(1)<<temp<<endl; } else break; } cout<<endl; system("pause"); return 0; }
/* // Ch04_11 [示范]:实现环状队列数据的进队和出队 */ #include <iostream> using namespace std; int main(void) { int front,rear,val=0,queue[5]={0}; front=rear=-1; while(rear<5&&val!=-1) { cout<<"请输入一个值以存入队列,欲取出值请输入-2。(结束输入-1):"; cin>>val; if(val==-2) { if(front==rear) { cout<<"[队列已经空了]"<<endl; break; } front++; if (front==5) front=0; cout<<"取出队列值 ["<<queue[front]<<"]"<<endl; queue[front]=0; } else if(val!=-1 && rear<5) { if(rear+1==front || rear==4 && front<=0) { cout<<"[队列已经满了]"<<endl; break; } rear++; if(rear==5) rear=0; queue[rear]=val; } } cout<<"\n队列剩余数据:"<<endl; if (front==rear) cout<<"队列已空!!"<<endl; else { while(front!=rear) { front++; if (front==5) front=0; cout<<"["<<queue[front]<<"]"; queue[front]=0; } } cout<<endl; system("pause"); return 0; }
/* // Ch04_12 [示范]:实现双向队列 */ #include <iostream> #include <cstdlib> #include <iomanip> using namespace std; class Node { public: int data; class Node *next; }; typedef class Node QueueNode; typedef QueueNode *QueueByLinkedList; QueueByLinkedList front=NULL; QueueByLinkedList rear=NULL; //方法enqueue: 数据加入队列 void enqueue(int value) { QueueByLinkedList node; //建立节点 node=new QueueNode; node->data=value; node->next=NULL; //检查是否为空队列 if (rear==NULL) front=node;//新建立的节点成为第1个节点 else rear->next=node;//将节点加入到队列的末尾 rear=node;//将队列的队尾指针指向新加入的节点 } //方法dequeue:从队列取出数据 int dequeue(int action) { int value; QueueByLinkedList tempNode,startNode; //从队首取出数据 if (!(front==NULL) && action==1) { if(front==rear) rear=NULL; value=front->data;//将队列数据从队首取出 front=front->next;//将队列的队首指针指向下一个 return value; } //从队尾取出数据 else if(!(rear==NULL) && action==2) { startNode=front;//先记下队首的指标值 value=rear->data;//取出当前队尾的数据 //寻找最末尾节点的前一个节点 tempNode=front; while (front->next!=rear && front->next!=NULL) { front=front->next; tempNode=front; } front=startNode;//记录从队尾取出数据后的队列队首指针 rear=tempNode;//记录从队尾取出数据后的队列队尾指针 //下一行程序是指当队列中仅剩下最后一个节点时, //取出数据后便将front和rear指向NULL if ((front->next==NULL) || (rear->next==NULL)) { front=NULL; rear=NULL; } return value; } else return -1; } int main(void) { int temp; cout<<"以链表来实现双向队列"<<endl; cout<<"===================================="<<endl; cout<<"在双向队列队首加入第1笔数据,此数据值为1"<<endl; enqueue(1); cout<<"在双向队列队首加入第2笔数据,此数据值为3"<<endl; enqueue(3); cout<<"在双向队列队首加入第3笔数据,此数据值为5"<<endl; enqueue(5); cout<<"在双向队列队首加入第4笔数据,此数据值为7"<<endl; enqueue(7); cout<<"在双向队列队首加入第5笔数据,此数据值为9"<<endl; enqueue(9); cout<<"===================================="<<endl; temp=dequeue(1); cout<<"从双向队列队首按序取出的元素数据值为:"<<setw(1)<<temp<<endl; temp=dequeue(2); cout<<"从双向队列队尾按序取出的元素数据值为:"<<setw(1)<<temp<<endl; temp=dequeue(1); cout<<"从双向队列队首按序取出的元素数据值为:"<<setw(1)<<temp<<endl; temp=dequeue(2); cout<<"从双向队列队尾按序取出的元素数据值为:"<<setw(1)<<temp<<endl; temp=dequeue(1); cout<<"从双向队列队首按序取出的元素数据值为:"<<setw(1)<<temp<<endl; cout<<endl; system("pause"); return 0; }