设计一个栈类，实现的操作有初始化栈、入栈、出栈、判栈空。
#include<iostream>
using namespace std
template<class Type>
class Stack
{
public:
Stack()
void allocateMemoryWithMultiple(float multiple)
bool isEmputy()
void pushDataInStack(const Type&theData)
Type popDataOutOfStack()
private:
int count//栈里存储的数据个数
int maxSaveCount//最多存储数据的个数
Type *data//通用类型指针指向存储数据的内存首地址
}
template<class Type>
Stack<Type>::Stack()
{
count=0
maxSaveCount=8
data=new Type[maxSaveCount]//默认初始化分配可以存储8个数据大小的内存空间
}
template<class Type>
bool Stack<Type>::isEmputy()//判断栈是否为空
{
return count==0
}
template<class Type>
void Stack<Type>::allocateMemoryWithMultiple(float multiple)//以当前已分配内存大小和扩大、缩小倍数重新分配
{
int newMaxSaveCount=maxSaveCount * multiple
if(newMaxSaveCount<=count)newMaxSaveCount=count
Type *newData=new Type[newMaxSaveCount]
maxSaveCount=newMaxSaveCount
for(int i=0i<counti++)*(newData+i)=*(data+i)
delete []data
data=newData
}
template<class Type>
void Stack<Type>::pushDataInStack(const Type&theData)//入栈
{
if(count>=maxSaveCount)
{
allocateMemoryWithMultiple(2.0)//分配2倍空间大小
}
*(data+count)=theData
count++
}
template<class Type>
Type Stack<Type>::popDataOutOfStack()
{
Type value=0
if(isEmputy())
{
cout<<"栈中数据已经清空!"<<endl
return value
}
count--
value=*(data+count)
return value
}
int main()
{
Stack<int>sk
for(int i=1i<=100i++)sk.pushDataInStack(i)
for(int j=0j<50j++)sk.popDataOutOfStack()//推出后面50个数据
cout<<"依次压出的数据为："<<endl
while(!sk.isEmputy())
{
cout<<sk.popDataOutOfStack()<<"\t"
}
return 0
}
typedef struct stacknode{
char data
stacknode *next
}stacknode
typedef struct stacklink{
stacknode *top
}stacklink
1、数制转换
void conver(int turn,stacklink *s){
int x=0
int i=0
while(turn){
x=turn%2
turn=turn/2
stacknode *p=new stacknode
p->data=x
p->next=s->top
s->top=p
i++
}
printf("二进制结果为：")
for(i>0i--){
printf("%d",s->top->data)
s->top=s->top->next
}
printf("\n")
}
都挺简单的，不想写了....自己好好琢磨一下。
链栈的建立、判空、入栈、出栈、求长、访顶、清空和销毁
#include<iostream>using namespace std
typedef struct node
{
int data
struct node *next
}Node, *Stack
void initiateStack(Stack &s)
{
s = new Node
s->next = NULL
}
bool isEmptyStack(Stack &s)
{
if(NULL == s)
{
cout << "栈不存在." << endl
exit(0)
}
if(NULL == s->next)
return true
return false
}
void push(Stack &s, int element)
{
Node *p = new Node
p->data = element
p->next = s->next
s->next = p
}
int pop(Stack &s)
{
if(isEmptyStack(s))
{
exit(1)
}
Node *p = s->next
s->next = p->next
int element = p->data
delete p
return element
}
int getLength(Stack &s)
{
Node *p = s
int length = 0
while(NULL != p->next)
{
p = p->next
length++
}
return length
}
int getTop(Stack &s)
{
if(isEmptyStack(s))
exit(1)
return s->next->data
}
void clearStack(Stack &s)
{
while(!isEmptyStack(s))
pop(s)
}
void destoryStack(Stack &s)
{
while(!isEmptyStack(s))
pop(s)
delete s
s = NULL
}
void print(bool b)
{
if(b)
cout << "yes" << endl
else
cout << "no" << endl
}
int main()
{
Stack s
initiateStack(s)
int n = 100
int r = 8 // r进制
while(n) // 范式
{
push(s, n % r)
n /= r
}
while(!isEmptyStack(s))
cout << pop(s)
cout << endl << getLength(s) << endl
int i
for(i = 1 i <= 10 i++)
push(s, i)
cout << getTop(s) << endl
print(isEmptyStack(s))
clearStack(s)
print(isEmptyStack(s))
destoryStack(s)
print(isEmptyStack(s))
return 0
}
template <typename baseT>
struct base_node
{
baseT data
base_node * next, * pre
}
template <typename baseT>
class stack
{
private :
base_node<baseT>*header , *last
int __size
public :
typedef base_node<baseT>iterator
stack()
{
header = last = NULL
__size = 0
}
void push(baseT _elem)
{
__size++
base_node<baseT>*__tmp = new base_node<baseT>
__tmp->data = _elem
__tmp->pre = last
__tmp->next = NULL
if (header == NULL)
header = __tmp
else
last->next = __tmp
last = __tmp
}
void pop()
{
if (__size)
{
__size--
if (last->pre)
{
last->pre->next = NULL
base_node<baseT>*__tmp = last
last = last->pre
delete __tmp
}
else
{
delete last
header = last = NULL
}
}
}
inline baseT top()
{
return last->data
}
inline int size()
{
return __size
}
inline iterator begin()
{
return head
}
inline iterator end()
{
return end
}
}
分太少了。。哎。。
没有第三个操作，自己加吧
判断size是不是0就行了
里面有个迭代器是用来遍历
重载迭代器的++和--就能实现遍历了
using namespace std
template<class T>
class Stack
{
private:
T s[10]
int top
public:
bool push(T a)
T pop(int i)
bool stackempty()
Stack(){top=0}
}
template<class T>
bool Stack<T>::push(T a)
{
if(top<10)
{
s[top++]=a
return 1
}
else
return 0
}
template<class T>
T Stack<T>::pop(int i)
{
if(i==0)top--
return s[top--]
}
template<class T>
bool Stack<T>::stackempty()
{
if(s)
return 0
else
return 1
}
void main()
{
int a,nchar b
Stack<int>a1
cout<<"请输入栈元素个数:"
cin>>n
cout<<"请输入栈元素:"
for(int i=0i<ni++)
{
cin>>a
a1.push(a)
}
cout<<"出栈:"
for(int i=0i<ni++)
cout<<a1.pop(i)<<" "
cout<<endl
Stack<char>a2
cout<<"请输入栈元素个数:"
cin>>n
cout<<"请输入栈元素:"
for(int i=0i<ni++)
{
cin>>b
a2.push(b)
}
cout<<"出栈:"
for(int i=0i<ni++)
cout<<a2.pop(i)<<" "
cout<<endl
}
#include <cassert>
using namespace std
template<typename T>
class Stack
{
public:
Stack(int = 20) //栈如不指定大小，设为20元素
~Stack()
{
delete[]elements
}
void Push(const T&data) //压栈
T Pop()//弹出,top--
T GetElem(int i)//取数据,top不变
void MakeEmpty()//清空栈
{
top = -1
}
bool IsEmpty() const //判断栈空
{
return top == -1
}
bool IsFull()const//判栈满
{
return top == maxSize-1
}
void PrintStack() //输出站内所有元素
private:
int top//栈顶指针(下标)
T* elements //动态建立的栈
int maxSize//栈最大容纳的元素个数
}
template<typename T>
Stack<T>::Stack(int maxs)
{
maxSize = maxs
top = -1
elements = new T[maxSize] //建立占空间
assert(elements != 0)//分配不成功结束程序
}
template<typename T>
void Stack<T>::Push(const T&data)
{
assert(!IsFull()) //栈满则退出
elements[++top] = data //栈顶指针先加1，元素再进栈,top是指向栈顶的元素
}
template<typename T>
T Stack<T>::Pop()
{
assert(!IsEmpty())//栈已空则不能出栈,退出程序
return elements[top--] //返回栈顶元素,同时栈顶指针退1
}
template<typename T>
T Stack<T>::GetElem(int i)
{
assert(i <= top &&i >= 0) //超出栈有效数据则错，退出程序
return elements[i] //返回指定元素,top不变
}
template<typename T>
void Stack<T>::PrintStack()
{
for (int i = 0i <= topi++)
{
cout <<elements[i] <<'\t'
}
cout <<endl
}
int main()
{
int i, a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, b[10]
Stack<int>iStack(10)
for (i = 0i <10i++)
{
iStack.Push(a[i])
}
if (iStack.IsFull())
{
cout <<"栈满" <<endl
}
iStack.PrintStack()
for (i = 0i <10i++)
{
b[i] = iStack.Pop()
}
if (iStack.IsEmpty())
{
cout <<"栈空" <<endl
}
for (i = 0i <10i++)
{
cout <<b[i] <<'\t'//注意先后后出
}
cout <<endl
iStack.Pop()//下溢出
return 0
}
#include "stdlib.h"
#define MAXLEN 100
typedef char ElemType
typedef struct
{ ElemType data [MAXLEN]
int top
}SeqStack
void InitStack(SeqStack *S)
{
S->top=-1
}
int EmptyStack(SeqStack *S)
{
if(S->top==-1)
return 1
else
return 0
}
int Push(SeqStack *S,ElemType x)
{
if(S->top==MAXLEN-1)
{
printf("占栈满!")
return 0
}
else
{
S->top++
S->data[S->top]=x
return 1
}
}
int Pop(SeqStack *S,ElemType *x)
{
if(EmptyStack(S))
{
printf("栈空!")
return 0
}
else
{ *x=S->data[S->top]
S->top--
return 1
}
}
int GetTop(SeqStack *S,ElemType *x)
{
if(EmptyStack(S))
{
printf("栈空!")
return 0
}
else
{
*x=S->data[S->top]
return 1
}
}
void main()
{
SeqStack S
ElemType x
InitStack(&S)
printf("依次进栈元素为: \n")
printf("r元素进栈\n")
Push(&S,'r')
printf("a元素进栈\n")
Push(&S,'a')
printf("h元素进栈\n")
Push(&S,'h')
printf("c元素进栈\n")
Push(&S,'c')
GetTop(&S,&x)
printf("栈顶元素为: %c\n",x)
printf("出栈序列为: ")
while(!EmptyStack(&S))
{
Pop(&S,&x)
printf("%c",x)
}
printf("\n")
}
class stack
{
public:
int max//栈的大小
int sizeofstack//栈中元素的个数
int *stackbuffer//指向堆栈的指针（由于要求堆栈大小手动设置所以要动态分配内存）
stack(int size)//构造函数
int clear()//清空堆栈
int IsEmpty()//判断堆栈是否为空
int Length()//返回堆栈中元素个数
int Push(int a)//将数据压入栈
int Pop()//弹出栈顶元素
~stack() //析构函数
{
while(stackbuffer)
{
free(stackbuffer)//遍历堆栈释放每一个元素
stackbuffer++
}
}
}
stack::stack(int size)
{
stackbuffer = malloc(size * sizeof(int))//动态申请空间
sizeofstack = 0//初始化时堆栈元素个数为零
max = size//
}
int stack::clear()
{
sizeofstack = 0//将堆栈的个数设置为零即可
}
int stack::IsEmpty()//返回1表示堆栈为空，0为非空
{
if(sizeofstack == 0)
return 1
else
return 0
}
int stack::Length()
{
return sizeofstack
}
int stack::Push(int a)//
{
if(sizeofstack <max)//如果堆栈满了则不能向堆栈中放入元素
{
stackbuffer[sizeofstack] = a
sizeofstack ++
return 1
}
else
return 0
}
int stack::Pop()
{
if(sizeofstack >0)//如果堆栈为空则不能弹出元素
{
sizeofstack --
return stackbuffer[sizeofstack]
}
else
return 0
}
void main()
{
stack stack_int(5)
for(int i = 0i <5i++)
{
int input
cin>>input
if(!stack.push(input))//////////////////////
{
cout<<"输入错误"<<endle
return 0
｝
}
cout<<stack.sizeofstack<<endle
for(int i = 0i <3i++)
{
if(stack.sizeofstack >= 1)//////////////////
{
cout<<stack.Pop()<<endle
}
else
return
}
stack.clear()
}
不好意思，这个程序我没编译过，你自己试试，可能有错误，但问题应该不大，语法错误，自己试着改改，改不好给我留言
#define __SQ_STACK_H__
#include "utility.h"// 实用程序软件包
// 顺序栈类模板
template<class ElemType>
class SqStack
{
protected:
// 顺序栈的数据成员:
int count // 元素个数
int maxSize// 栈最大元素个数
ElemType *elems // 元素存储空间
// 辅助函数模板:
bool Full() const // 判断栈是否已满
void Init(int size) // 初始化栈
public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
SqStack(int size = DEFAULT_SIZE) // 构造函数模板
virtual ~SqStack() // 析构函数模板
int Length() const // 求栈长度
bool Empty() const // 判断栈是否为空
void Clear()// 将栈清空
void Traverse(void (*visit)(const ElemType &)) const// 遍历栈
StatusCode Push(const ElemType &e) // 入栈
StatusCode Top(ElemType &e) const // 返回栈顶元素
StatusCode Pop(ElemType &e)// 出栈
SqStack(const SqStack<ElemType>©) // 复制构造函数模板
SqStack<ElemType>&operator =(const SqStack<ElemType>©)// 重载赋值运算符
}
// 顺序栈类模板的实现部分
template <class ElemType>
bool SqStack<ElemType>::Full() const
// 操作结果：如栈已满，则返回true，否则返回false
{
return count == maxSize
}
template <class ElemType>
void SqStack<ElemType>::Init(int size)
// 操作结果：初始化栈为最大元素个数为size的空栈
{
maxSize = size // 最大元素个数
if (elems != NULL) delete []elems// 释放存储空间
elems = new ElemType[maxSize] // 分配存储空间
count = 0 // 空栈元素个数为0
}
template<class ElemType>
SqStack<ElemType>::SqStack(int size)
// 操作结果：构造一个最大元素个数为size的空栈
{
elems = NULL // 未分配存储空间前,elems为空
Init(size) // 初始化栈
}
template<class ElemType>
SqStack<ElemType>::~SqStack()
// 操作结果：销毁栈
{
delete []elems// 释放存储空间
}
template <class ElemType>
int SqStack<ElemType>::Length() const
// 操作结果：返回栈元素个数
{
return count
}
template<class ElemType>
bool SqStack<ElemType>::Empty() const
// 操作结果：如栈为空，则返回true，否则返回false
{
return count == 0
}
template<class ElemType>
void SqStack<ElemType>::Clear()
// 操作结果：清空栈
{
count = 0
}
template <class ElemType>
void SqStack<ElemType>::Traverse(void (*visit)(const ElemType &)) const
// 操作结果：从栈底到栈顶依次对栈的每个元素调用函数(*visit)
{
for (int curPosition = 1curPosition <= Length()curPosition++)
{ // 从栈底到栈顶对栈的每个元素调用函数(*visit)
(*visit)(elems[curPosition - 1])
}
}
template<class ElemType>
StatusCode SqStack<ElemType>::Push(const ElemType &e)
// 操作结果：将元素e追加到栈顶,如成功则返加SUCCESS,如栈已满将返回OVER_FLOW
{
if (Full())
{ // 栈已满
return OVER_FLOW
}
else
{ // 操作成功
elems[count++] = e// 将元素e追加到栈顶
return SUCCESS
}
}
template<class ElemType>
StatusCode SqStack<ElemType>::Top(ElemType &e) const
// 操作结果：如栈非空,用e返回栈顶元素,返回SUCCESS,否则返回UNDER_FLOW
{
if(Empty())
{ // 栈空
return UNDER_FLOW
}
else
{ // 栈非空,操作成功
e = elems[count - 1] // 用e返回栈顶元素
return SUCCESS
}
}
template<class ElemType>
StatusCode SqStack<ElemType>::Pop(ElemType &e)
// 操作结果：如栈非空,删除栈顶元素,并用e返回栈顶元素,返回SUCCESS,否则
// 返回UNDER_FLOW
{
if (Empty())
{ // 栈空
return UNDER_FLOW
}
else
{ // 操作成功
e = elems[count - 1] // 用e返回栈顶元素
count--
return SUCCESS
}
}
template<class ElemType>
SqStack<ElemType>::SqStack(const SqStack<ElemType>©)
// 操作结果：由栈copy构造新栈——复制构造函数模板
{
elems = NULL // 未分配存储空间前,elems为空
Init(copy.maxSize) // 初始化新栈
count = copy.count // 栈元素个数
for (int curPosition = 1curPosition <= Length()curPosition++)
{ // 从栈底到栈顶对栈copy的每个元素进行复制
elems[curPosition - 1] = copy.elems[curPosition - 1]
}
}
template<class ElemType>
SqStack<ElemType>&SqStack<ElemType>::operator = (const SqStack<ElemType>©)
// 操作结果：将栈copy赋值给当前栈——重载赋值运算符
{
if (© != this)
{
Init(copy.maxSize)// 初始化当前栈
count = copy.count// 复制栈元素个数
for (int curPosition = 1curPosition <= Length()curPosition++)
{ // 从栈底到栈顶对栈copy的每个元素进行复制
elems[curPosition - 1] = copy.elems[curPosition - 1]
}
}
return *this
}
#endif
