C++实现栈的操作(push和pop)

来源：jb51　　时间：2022/7/25 17:16:06　　对本文有异议

栈的操作(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;
}