棧的解析及C++實現

介紹

棧是一種線性結構，它有以下幾個特點：

1）棧中數據是按照“後進先出”方式進出棧的

2）向棧中添加/刪除數據時，只能從棧頂進行操作

棧通常包括三種操作：top、pop、push

top -- 返回棧頂元素

pop -- 返回並刪除棧頂元素

push -- 向棧中添加元素

常見錯誤：棧空時進行top或pop操作

解決方法：用戶在使用top或pop操作時，需確保棧是非空的

棧的示意圖

出棧

入棧

棧的C++實現

順序棧

順序棧結構實現的頭文件SeqStack.h

#ifndef SeqStack_byNim
#define SeqStack_byNim

#include<iostream>
using namespace std;

const int MAX_SIZE=100;

template <class T>
class SeqStack
{
 private:
  T *data;
  int topPointer;
 public:
  SeqStack();
  ~SeqStack();
 
  void push(T e);
  T pop();
  T top();
 
  bool empty();
};

template <class T>
SeqStack<T>::SeqStack()
{
 topPointer=-1;
 data=new T[MAX_SIZE];
}

template <class T>
SeqStack<T>::~SeqStack()
{
 topPointer=-1;
 delete []data;
}

template <class T>
void SeqStack<T>::push(T e) //入棧操作
{
 if(topPointer==MAX_SIZE-1) 
 {
  cout<<"OVERFLOW"<<endl;   return;
 }
 topPointer++;
 data[topPointer]=e;
}

template <class T>
T SeqStack<T>::pop() //出棧操作
{
 if(topPointer==-1)
 {
  throw "棧空";
 }
 return data[topPointer--];
}

template <class T>
T SeqStack<T>::top()
{
 if(topPointer==-1)
 {
  throw "棧空";
 }
 return data[topPointer];
}

template <class T>
bool SeqStack<T>::empty()
{
 if(topPointer==-1)
 {
  return true;
 }
 return false;
}

#endif

測試文件：SStackTest.cpp

#include<iostream>
#include "SeqStack.h"
using namespace std;

int main()
{
 int tmp = 0;
 SeqStack<int> *astack = new SeqStack<int>;
 
 cout<<"main"<<endl;
 
 //將10, 20, 30 依次推入棧中
 astack->push(10);
    astack->push(20);
    astack->push(30);
   
    // 將“棧頂元素”賦值給tmp，並刪除“棧頂元素”
    tmp = astack->pop();
    cout<<"tmp="<<tmp<<endl;
   
    // 只將“棧頂”賦值給tmp，不刪除該元素
    tmp = astack->top();
    cout<<"tmp="<<tmp<<endl;
   
    astack->push(40);
   
    while(!astack->empty())
    {
     tmp = astack->pop();
     cout<<"tmp="<<tmp<<endl;
 }
 return 0;
}

鏈棧

鏈棧結構實現的頭文件：LinkStack.h

#ifndef LinkStack_byNim
#define LinkStack_byNim

#include<iostream>
using namespace std;

template<class T>
struct Node
{
 T data; //數據域
 Node *next; //指針域
};

template<class T>
class LinkStack
{
 private:
  Node<T> *topPointer;
 public:
  LinkStack();
  ~LinkStack();
 
  void push(T e);
  T pop();
  T top();
 
  bool empty();
};

template<class T>
LinkStack<T>::LinkStack()
{
 topPointer=new Node<T>;
 topPointer->next=NULL;
} 

template<class T> 
LinkStack<T>::~LinkStack()
{
 delete topPointer;
}

template<class T>
void LinkStack<T>::push(T e)
{
 Node <T> *aNode;
 aNode=new Node<T>;
 aNode->data=e;
 aNode->next=topPointer;
 topPointer=aNode;
}

template<class T>
T LinkStack<T>::pop()
{
 if(topPointer==NULL)
  throw "下溢";
 Node <T> *p;
 p=topPointer;
 T rtndata = topPointer->data;
 topPointer=topPointer->next;
 delete p;
 return rtndata;
}

template<class T>
T LinkStack<T>::top()
{
 if(topPointer==NULL)
  throw "Empty";
 return topPointer->data;
}

template<class T>
bool LinkStack<T>::empty()
{
 if(topPointer==NULL)
  return true;
 return false;
}

#endif

測試文件：LStackTest.cpp

#include<iostream>
#include "LinkStack.h"
using namespace std;

int main()
{
 string tmp;
 LinkStack<string> *astack = new LinkStack<string>;
 
 cout<<"main"<<endl;
 
  //將"cat"、"dog"、"pig"依次推入棧中
 astack->push("cat");
    astack->push("dog");
    astack->push("pig");
   
    // 將“棧頂元素”賦值給tmp，並刪除“棧頂元素”
    tmp = astack->pop();
    cout<<"tmp="<<tmp<<endl;
   
    // 只將“棧頂”賦值給tmp，不刪除該元素
    tmp = astack->top();
    cout<<"tmp="<<tmp<<endl;
   
    astack->push("duck");
   
    while(!astack->empty())
    {
     tmp = astack->pop();
     cout<<"tmp="<<tmp<<endl;
 }
 return 0;
}

STL中自帶的“棧”

頭文件：#include <stack>

測試文件：StackTest.cpp

#include<iostream>
#include<stack>
using namespace std;

int main()
{
 int tmp = 0;
 stack<int> *astack = new stack<int>;
 
 cout<<"main"<<endl;
 
 //將10, 20, 30 依次推入棧中
 astack->push(10);
    astack->push(20);
    astack->push(30);
   
    // 刪除“棧頂元素”，pop操作不返回棧頂數據
    astack->pop();
    cout<<"tmp="<<tmp<<endl;
   
    // 只將“棧頂”賦值給tmp，不刪除該元素
    tmp = astack->top();
    cout<<"tmp="<<tmp<<endl;
   
    astack->push(40);
   
    while(!astack->empty())
    {
     tmp = astack->top();
     cout<<"tmp="<<tmp<<endl;
     astack->pop();
 }
 return 0;
}

注意：STL中自帶的stack的pop操作不返回棧頂元素，只進行刪除動作