3.1用數組構造棧
【注意以下幾點】：
1.基于數組的棧的三要素：1）棧的最大容量maxSize; 2)棧的目前容量=目前棧中元素的個數=棧頂top-1；3）動态數組存儲棧的元素 Type* list；
2.對于出棧、入棧的操作要對應先判斷棧空、棧滿；如果空、滿要有異常處理或錯誤提示。
3.注意入棧push操作，先入棧後top+1；出棧pop則相反，先top-1，再出棧。【注意因為，top指向數組中最後一個元素的下一個位置】。
4.拷貝構造函數和指派函數要注意，尤其指派的時候，避免自身指派、同時要注意大小不一緻的不能完成指派操作，要有相關提示。
template<typenameType>
class arrStack
{
public:
arrStack(intnSize=100);
~arrStack();
arrStack(constarrStack& copyStack);
arrStack&operator=(const arrStack& otherStack);
voidinitializeStack();
void destroyStack();
bool isStackEmpty();
bool isStackFull();
void push(constType& item);
void pop(Type&poppedItem);
private:
int maxSize;
int top;
Type* list;
};
template<typename Type>
arrStack<Type>::arrStack(int nSize=100)
{
if(nSize < 0)
{
nSize = 100;
list = newType[nSize];
top = 0;
maxSize = 100;
}
else
{
list = newType[nSize];
top = 0;
maxSize =nSize;
}
}
template<typename Type>
arrStack<Type>::~arrStack()
{
if(!list)
{
delete[]list; //注意數組的删除，為delete []list;
list = NULL;
}
}
template<typename Type>
arrStack<Type>::arrStack(const arrStack& copyStack)
{
maxSize =copyStack.maxSize;
top = copyStack.top;
list = newType[maxSize]; //注意需要自定義大小,容易出錯.
for( int i = 0; i <top; i++)
{
list[i] =copyStack.list[i];
}
}
template<typename Type>
arrStack<Type>& arrStack<Type>::operator=(constarrStack& otherStack)
{
if(this ==&otherStack)
{
cout <<"can't copy oneSelf!" << endl;
return *this;
}
else
{
if(maxSize !=otherStack.maxSize)
{
cout<< "The Size of two stack are not equal!" << endl;
return*this;
}
else
{
maxSize= otherStack.maxSize;
top =otherStack.top;
for( inti = 0; i < top; i++)
{
list[i]= otherStack.list[i];
}//endfor
return*this;
}
}//end else
}
template<typename Type>
void arrStack<Type>::initializeStack()
{
destroyStack();
}
template<typename Type>
void arrStack<Type>::destroyStack()
{
top = 0;
}
template<typename Type>
bool arrStack<Type>::isStackEmpty()
{
return (top == 0);
}
template<typename Type>
bool arrStack<Type>::isStackFull()
{
return (top ==maxSize);
}
template<typename Type>
void arrStack<Type>::push(const Type& item)
{
if(!isStackFull())
{
list[top] =item;
top++;
}
else
{
cout <<"The Stack was already Full!" << endl;
}
}
template<typename Type>
void arrStack<Type>::pop(Type& poppedItem)
{
if(!isStackEmpty())
{
top--;
poppedItem =list[top];
}
else
{
cout <<"The Stack was already Empty!" << endl;
}
} 3.2用連結清單構造棧
連結清單構造棧注意：
1） 判斷棧空的标記是top==NULL；由于棧的空間可以動态配置設定，是以可以認為鍊棧不會滿。
2） 棧的入棧Push操作要先判定棧是否已經滿，非滿才可以入棧。先入棧，再調整top指針；
3） 棧的出棧Pop操作要先判定棧是否已空，非空才可以出棧。先調整top指針，再出棧，并删除原結點。
4） 可以加count判定目前結點的個數。
template<typename Type>
struct nodeType
{
Type info;
nodeType* link;
};
template<typename Type>
class linkedStack
{
public:
linkedStack();
~linkedStack();
linkedStack(constlinkedStack<Type>&);
linkedStack&operator=(const linkedStack<Type>&);
voidinitializeStack();
void destroyStack();
bool isStackEmpty()const;
bool isStackFull()const;
void push(constType& item);
void pop(Type&poppedItem);
void nodeCount();
voidreversePrint(); //逆向列印的非遞歸實作...
private:
nodeType<Type>*top;
int count; //統計節點個數
};
template<typename Type>
linkedStack<Type>::linkedStack()
{
count = 0;
top = NULL;
}
template<typename Type>
linkedStack<Type>::~linkedStack()
{
while( top != NULL )
{
nodeType<Type>*tempNode = new nodeType<Type>;
tempNode = top;
top =top->link;
deletetempNode;
}//end if
}
template<typename Type>
linkedStack<Type>::linkedStack(constlinkedStack<Type>& copyStack)
{
if(copyStack.top !=NULL)
{
nodeType<Type>*current;
nodeType<Type>*first;
nodeType<Type>*newNode;
top = newnodeType<Type>;
top->info =copyStack.top->info; //此處的top不能直接用，記憶體報錯！
top->link =copyStack.top->link;
first =top; //first跟進目前連結清單...
current =copyStack.top->link; //current跟進copy連結清單...
while( current!= NULL)
{
newNode= new nodeType<Type>;
newNode->link= current->link;
newNode->info= current->info;
first->link= newNode;
first =newNode;
current= current->link;
}//end while
count =copyStack.count;
}//end if
else
{
top = NULL;
count = 0;
}
}
template<typename Type>
linkedStack<Type>&linkedStack<Type>::operator=(const linkedStack<Type>&otherStack)
{
//1避免自身指派
if(this ==&otherStack)
{
cout <<"Can't copy oneself!" << endl;
return *this;
}
//2其他
else
{
if(top != NULL)
{
destroyStack();
}
if(otherStack.top!= NULL)
{
nodeType<Type>*current;
nodeType<Type>*first;
nodeType<Type>*newNode;
top =new nodeType<Type>;
top->info= otherStack.top->info;
top->link= otherStack.top->link;
first =top; //first跟進目前連結清單...
current= otherStack.top->link; //current跟進copy連結清單...
while(current != NULL)
{
newNode= new nodeType<Type>;
newNode->link= current->link;
newNode->info= current->info;
first->link= newNode;
first= newNode;
current= current->link;
}//endwhile
count =otherStack.count;
}//end if
else
{
top =NULL;
count =0;
}
return *this;
}
}
template<typename Type>
void linkedStack<Type>::initializeStack()
{
destroyStack();
}
template<typename Type>
void linkedStack<Type>::destroyStack()
{
count = 0;
top = NULL;
}
template<typename Type>
bool linkedStack<Type>::isStackEmpty() const
{
return (count == 0);
}
template<typename Type>
bool linkedStack<Type>::isStackFull() const //空間非固定，動态申請!
{
return false;
}
template<typename Type>
void linkedStack<Type>::push(const Type& item)
{
if(!isStackFull())
{
nodeType<Type>*newNode = new nodeType<Type>;
newNode->info= item;
newNode->link= NULL;
if(top == NULL)
{
top = newNode;
}
else
{
newNode->link= top;
top =newNode;
}
count++;
cout <<item << " was pushed!" << endl;
}
}
template<typename Type>
void linkedStack<Type>::pop(Type& poppedItem)
{
if(!isStackEmpty())
{
nodeType<Type>*temp = new nodeType<Type>;
temp = top;
poppedItem =top->info;
top =top->link;
count--;
cout <<poppedItem << " was popped!" << endl;
delete temp;
}
}
template<typename Type>
void linkedStack<Type>::nodeCount()
{
cout <<"nodeCount = " << count << endl;
}
//上一節的遞歸實作逆向連結清單列印，這是非遞歸的實作。
template<typename Type>
void linkedStack<Type>::reversePrint() //逆向列印的非遞歸實作...
{
// 注釋部分可作為連結清單調用棧的非遞歸實作。
// nodeType<Type>*current = new nodeType<Type>;
// current = top;
// while(current != NULL)
// {
// pop(current->info);
// current =current->link;
// }
int poppedItem = 0;
while(!isStackEmpty())
{
pop(poppedItem);
} 作者：銘毅天下
原文：
https://blog.csdn.net/laoyang360/article/details/7871198![Excel資料清洗大師-Power Query，我整理資料2小時，同僚2分鐘搞定了[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)