C++實現棧的操作(push和pop)
棧的操作(push和pop)
棧的組織形式
如上圖所示：棧也是有多個數據節點組成的，每個節點包含有數據域和指向下一個節點的指針域。並且每次的push、pop和判空都是操作的棧頂指針top。
棧中每個數據節點的定義
class data_node{
public:
data_node() :data(0), next(NULL){}//default constructer function
data_node(int value) :data(value), next(NULL){}//include arg constructer function
int data;
data_node *next;//pointer that point to next node
};
棧的類的定義
class my_stack{
public:
my_stack() :top(NULL){}
void push(data_node new_data);
void pop(data_node *pop_node);
bool empty();
data_node *top;
};
棧的push操作
void my_stack::push(data_node new_data)
{
data_node *pnode = NULL;
pnode = new data_node(new_data.data);
pnode->next = top;
top = pnode;
}
void my_stack::pop(data_node *pop_node)
{
if (empty())
{
printf("this stack is empty\n");
return;
}
pop_node->data = top->data;
data_node *pnode = top;
top = top->next;
delete pnode;
}
bool my_stack::empty()
{
return (top == NULL);
}
完整的代碼如下：
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
#include <string>
using namespace std;
class data_node{
public:
data_node() :data(0), next(NULL){}//default constructer function
data_node(int value) :data(value), next(NULL){}//include arg constructer function
int data;
data_node *next;//pointer that point to next node
};
class my_stack{
public:
my_stack() :top(NULL){}
void push(data_node new_data);
void pop(data_node *pop_node);
bool empty();
data_node *top;
};
void my_stack::push(data_node new_data)
{
data_node *pnode = NULL;
pnode = new data_node(new_data.data);
pnode->next = top;
top = pnode;
}
void my_stack::pop(data_node *pop_node)
{
if (empty())
{
printf("this stack is empty\n");
return;
}
pop_node->data = top->data;
data_node *pnode = top;
top = top->next;
delete pnode;
}
bool my_stack::empty()
{
return (top == NULL);
}
int main()
{
data_node pop_node(0);
my_stack stack;
stack.push(3);
stack.push(2);
stack.push(6);//3,2,6
stack.pop(&pop_node);
//printf("is empty? %d\n", stack.empty());
printf("%2d ", pop_node.data);
stack.pop(&pop_node);
//printf("is empty? %d\n", stack.empty());
printf("%2d ", pop_node.data);
stack.pop(&pop_node);
printf("%2d\n ", pop_node.data);
printf("is empty? %d\n", stack.empty());
return 0;
}
棧應用之進制轉換
MyStack.h
#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using namespace std;
template <typename T>
class MyStack
{
public:
MyStack(int size); //分配內存初始化空間，設定棧容量，棧頂
~MyStack(); //回收棧空間內存
bool stackEmpty(); //判定棧是否為空，為空返回true，非空返回false
bool stackFull(); //判定棧是否為滿，為滿返回true，不滿返回false
void clearStack(); //清空棧
int stackLength(); //已有元素的個數
bool push(T elem); //元素入棧，棧頂上升
bool pop(T &elem); //元素出棧，棧頂下降
void stackTraverse(bool isFromButtom); //遍歷棧中所有元素
private:
T *m_pBuffer; //棧空間指針
int m_iSize; //棧容量
int m_iTop; //棧頂，棧中元素個數
};
template <typename T>
MyStack<T>::MyStack(int size)
{
m_iSize = size;
m_pBuffer = new T[size];
m_iTop = 0;
}
template <typename T>
MyStack<T>::~MyStack()
{
delete[]m_pBuffer;
m_pBuffer = NULL;
}
template <typename T>
bool MyStack<T>::stackEmpty()
{
if (0 == m_iTop)
{
return true;
}
else
{
return false;
}
}
template <typename T>
bool MyStack<T>::stackFull()
{
if (m_iTop == m_iSize)
{
return true;
}
else
{
return false;
}
}
template <typename T>
void MyStack<T>::clearStack()
{
m_iTop = 0;
}
template <typename T>
int MyStack<T>::stackLength()
{
return m_iTop;
}
template <typename T>
bool MyStack<T>::push(T elem)
{
if(!stackFull())
{
m_pBuffer[m_iTop] = elem;
m_iTop++;
return true;
}
else
{
return false;
}
}
template <typename T>
bool MyStack<T>::pop(T &elem)
{
if (!stackEmpty())
{
m_iTop--;
elem = m_pBuffer[m_iTop];
return true;
}
else
{
return false;
}
}
template <typename T>
void MyStack<T>::stackTraverse(bool isFromButtom)
{
if (isFromButtom)
{
for (int i = 0; i < m_iTop; i++)
{
cout << m_pBuffer[i];
}
}
else
for (int i = m_iTop -1; i >= 0; i--)
{
cout << m_pBuffer[i];
}
cout << endl;
}
#endif MYSTACK_H
main.cpp
#include "MyStack.h"
#define BINARY 2
#define OCTONSRY 8
#define HEXADECTMAL 16
int main()
{
char num[] = "0123456789ABCDEF";
MyStack<char> *pStack = new MyStack<char>(50);
int N = 0;
cin >> N;
int mod = 0;
while (N != 0)
{
mod = N % HEXADECTMAL;
pStack->push(num[mod]);
N = N / HEXADECTMAL;
}
pStack->stackTraverse(false);
delete pStack;
pStack = NULL;
system("pause");
return 0;
}
以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。