本文已經過時, 最新文章請點擊 : 《【資料結構 – 重構】堆疊與雙邊堆疊》
栈和队列同样属于线性表, 但却是一种比较特殊的线性表. 因为它们对于输入和输出会有一定的限制, 所以是限定性线性表
栈里面有两个名词是需要了解的 :
- 栈顶 (
Top
) : 表中允许输入与输出的一端 - 栈底 (
Bottom
) : 栈顶对应的表中的另外一端
如果对于线性表的理解比较深刻的话, 栈写起来会非常简单. 因为对应起非限定性线性表, 栈只允许在顶部进行插入以及删除操作, 栈顶下面到栈底的元素都是在栈顶不动之前不允许动的
下面一张 SVG 图表示了 Stack 中的进栈与出栈操作 :
因为我们是以数组的形式存储栈, 所以上面用了类似于数组的方式表示. 实际上, 栈以向上的方式叠加更为直观
另外需要指出的是, 由于使用的是 C++, 所以不管是图中还是文中的 top
都为数组指针
1. 进栈
首先需要判断栈是否为满, 如果栈满还要进栈, 会造成溢出. 如果栈不满, 则在最后一个元素后面添加这个元素, 并且让 top
指针指向这个元素即可
2. 出栈
首先需要判断栈是否为空, 如果栈不空, 那么直接让 top
指针指向的元素 *top
出栈即可, 然后让 top
指针指向出栈元素的前一个元素即可
这次的代码经过重构并且加上了注释, 不过注释是英文的. 之前 top
用的非数组指针
这次的重构也让我认识到了之前的代码的注释问题, 之后如果有时间, 我将会对之前的所有代码进行重构. 该有注释的地方我会加上注释, 并且我将会考虑对于注释写一篇专门的文章
下面给出源代码, 有错误欢迎指出
分成三个文件, 其中一个是 Class 源文件, 分为 .hpp 文件和 .cpp 文件, 另外一个是 main 函数文件
Stack.hpp
:
#ifndef STACK_STACK_HPP
#define STACK_STACK_HPP
#include <iostream>
#include <cstdlib>
namespace SequentialStack {
using std::cin;
using std::cout;
using std::endl;
class Stack {
private :
bool isEmpty();
bool isFull();
protected :
int *arr;
int *top; //The pointer of arr
int maxSize; //The max size of stack, designated by users
public :
Stack(int maxSize);
~Stack();
long long int getTop(); //Get the top element from the stack
void push(int data);
void pop();
void clearStack();
void showStack();
};
}
Stack.cpp
:
#include "Stack.hpp"
using namespace SequentialStack;
Stack::Stack(int maxSize) {
this->top = nullptr;
this->arr = new int[maxSize];
this->maxSize = maxSize;
}
Stack::~Stack() {
this->top = nullptr;
delete []this->arr;
delete this->top;
}
bool Stack::isEmpty() {
if(!this->top) {
return true;
}
return false;
}
bool Stack::isFull() {
if(this->arr + this->maxSize - 1 == this->top) {
return true;
}
return false;
}
long long int Stack::getTop() {
if(this->isEmpty()) {
return INT64_MIN;
}
return (long long int)*this->top;
}
void Stack::push(int data) {
if(this->isFull()) {
cout << "The stack is full!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
return;
}
/* If top pointer is nullptr, let it point to the first position of arr. */
if(this->isEmpty()) {
this->top = this->arr;
*this->top = data;
return;
}
this->top++;
*this->top = data;
}
void Stack::pop() {
if(isEmpty()) {
cout << "The stack is empty!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
return;
}
cout << "The top element : " << *this->top << " has been popped!" << endl;
this->top--;
/* If all element has been popped, set top pointer as nullptr. */
if(this->top < this->arr) {
this->top = nullptr;
}
cout << "Press any key to continue!" << endl;
getchar();
getchar();
}
void Stack::clearStack() {
this->top = nullptr;
}
void Stack::showStack() {
if(this->isEmpty()) {
return;
}
cout << "Index : \t";
int count = 0; //size of the arr
int *p = this->arr; //traversal pointer
while(p != this->top + 1) {
count++;
cout << count << "\t";
p++;
}
p = nullptr;
delete p;
cout << endl << "Element : \t";
for(int *i = this->arr; i <= this->top; i++) {
cout << *i << "\t";
}
cout << endl;
}
main.cpp
:
#include "Stack.hpp"
using namespace SequentialStack;
void menu();
int main(int argc, char *argv[]) {
int maxSize; //The max size of stack, input by users
Stack *stack;
long long int top; //The top element of stack
int data; //Element need be pushed, input by users
cout << "Please enter the max size of stack : ";
cin >> maxSize;
stack = new Stack(maxSize);
int choice;
do {
system("clear");
stack->showStack();
menu();
cin >> choice;
switch(choice) {
case 1 :
top = stack->getTop();
if(top == INT64_MIN) {
cout << "The stack is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The top element is : " << top << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 2 :
cout << "Please enter the element you want to push : ";
cin >> data;
stack->push(data);
break;
case 3 :
stack->pop();
break;
case 4 :
stack->clearStack();
break;
case 5 :
delete stack;
exit(0); //Exit code : 0
default :
break;
}
}while(choice != 5);
}
void menu() {
cout << "-----------------------------------------------------------" << endl;
cout << "1. Get the top element of the stack." << endl;
cout << "2. Push." << endl;
cout << "3. Pop." << endl;
cout << "4. Clear the stack." << endl;
cout << "5. Exit." << endl;
cout << "-----------------------------------------------------------" << endl;
cout << "Please enter your choice : ";
}
自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《数据结构 : 顺序栈》https://jonny.vip/2018/01/27/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e9%a1%ba%e5%ba%8f%e6%a0%88/
Leave a Reply