栈

数组实现

1.顺序栈的基本运算

描述

栈的顺序存储结构与操作

题目描述：请你定义一个顺序栈，可以对顺序栈进行“将某个元素入栈”、“弹出栈顶元素”、“取栈顶元素（不删除）”、“判断栈是否为空”、“清空栈”等操作。键盘输入一些命令，可以执行上述操作。本题中，顺序栈元素为int数字，顺序栈的最大长度为10。

#include <iostream> using namespace std; class Seqlist { public: Seqlist() { top = -1; } ~Seqlist(){} void Push(int x); int Pop(); int Gettop() { if (top != -1) return data[top]; } int Empty() { if (top == -1) return 1; else return 0; } void Least() { top = -1; } private: int data[10]; int top; }; //入栈，需补全代码 void Seqlist::Push(int x) { //TODO if (top < 9) { top++; data[top] = x; } return; } //出栈，需补全代码 int Seqlist::Pop() { //TODO if (top != -1) { return data[top--]; } else { return -1; } } int main() { char c; cin >> c; Seqlist S; while (c != 'E') { if (c == 'P') { int x; cin >> x; S.Push(x); } if (c == 'D') { int a = S.Pop(); if (a != -1) cout << a << endl; else cout << "None"; } if (c == 'G') { int a = S.Gettop(); cout << a << endl; } if (c == 'T') { S.Least(); } if (c == 'Y') { int a = S.Empty(); if (a == 1) cout << "Yes" << endl; else cout << "No" << endl; } cin >> c; } return 0; }

链表实现

1.链栈的基本运算

描述

题目描述：

请你定义一个链栈，可以对链栈进行 “将某个元素入栈”、“弹出栈顶元素”、“取栈顶元素（不删除）”、“判断栈是否为空”、 “清空栈”等操作。键盘输入一些命令，可以执行上述操作。本题中，栈的元素为字符。

#include<iostream> using namespace std; class Node { public: char data; Node* next; }; class LinkStack { public: LinkStack() { top = NULL; } ~LinkStack(); void Push(char x); char Pop(); void Delete(); //获得栈顶元素 char GetTop() { //ToDo return top->data; } //判断是否为空 int Empty() { //ToDo if (top == NULL) { return 1; } else { return 0; } } private: Node* top; }; LinkStack::~LinkStack() { //ToDo } //入栈操作 void LinkStack::Push(char x) { //ToDo Node* s = new Node; s->data = x; s->next = top; top = s; } //出栈操作 char LinkStack::Pop() { //ToDo char x = NULL; if (top != NULL) { Node* pmiddle = top; top = top->next; x = pmiddle->data; delete pmiddle; return x; } return x; } void LinkStack::Delete() { //ToDo Node* pmiddle = top; while (top != NULL) { top = top->next; delete pmiddle; pmiddle = top; } } int main() { LinkStack Seq; char str, x; while (1){ cin >> str; //ToDo if (str == 'P'){ cin >> x; Seq.Push(x); } if (str == 'D'){ x = Seq.Pop(); if (x == NULL) { cout << "None" << endl; } else { cout << x << endl; } } if (str == 'G'){ x = Seq.GetTop(); cout << x << endl; } if (str == 'T'){ Seq.Delete(); } if (str == 'Y'){ int a = Seq.Empty(); if (a == 1) cout << "Yes" << endl; else cout << "No" << endl; } if (str == 'E'){ break; } } return 0; }

2.十进制转八进制数

描述

将十进制转成八进制

题目描述：请你定义一个顺序栈，可以对顺序栈进行“将某个元素入栈”、“弹出栈顶元素”、“判断栈是否为空”操作，利用该顺序栈完成十进制数转成八进制数操作。

最后输出的是八进制序列，就是说把十进制转换成八进制的位数一个个入栈。

#include <iostream> using namespace std; class SeqStack { public: SeqStack() { top=-1; } ~SeqStack(){} void Push(int x); int Pop(); int GetTop() { if(top!=-1) return data[top]; } int Empty() { if(top==-1) return 1; else return 0; } void Least() { top=-1; } private: int data[10]; int top; }; void SeqStack::Push(int x) { if(top==9){ cout << "None"<<endl; } else data[++top]=x; } int SeqStack::Pop() { if(top==-1){ cout << "None"<<endl; return -1; }else { int x=data[top--]; return x; } } int main() { SeqStack s; int N; cin>>N; try{ //ToDo:利用栈s完成十进制数转成八进制，将八进制结果入栈 while(N){ s.Push(N%8); N=N/8; } }catch(char s[]){} //ToDo:完成出栈并输出，即输出八进制数序列 while(!s.Empty()){ cout << s.Pop(); } cout << endl; return 0; }