Java數據結構中棧的用法

這期內容當中小編將會給大家帶來有關Java數據結構中棧的用法，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

棧是先進后出的特殊線性表，只允許在表的末端進行插入和刪除，后面將介紹兩種實現棧的方式，分別是基于數組的實現、基于鏈表的實現。

棧的抽象定義

class Mystack
{
public:
	Mystack() {}
	virtual void push(int &x) = 0;
	virtual bool pop(int &x) = 0;
	virtual bool Top(int &x) const = 0;
	virtual bool IsEmpty()const = 0;
	virtual bool IsFull()const = 0;
	virtual int getSize()const = 0;
};

順序棧-----------使用數組表示棧空間

定義：

#pragma once
#include "Mystack.h"
#include <iostream>
#include <assert.h>
using namespace std;
const int stackIncreament = 20;

class SeqStack : public Mystack
{
public:
	SeqStack(int sz = 50);                 //建立一個空棧
	~SeqStack() { delete[]elements; }      //析構函數
	//如果棧滿，則溢出程序處理，否則插入x
	void push(int &x);                 
	//如果棧空，則返回FALSE，否則使用x傳遞棧頂的值，top-1
	bool pop(int &x);
	//如果棧空，則返回FALSE，否則使用x傳遞棧頂的值
	bool Top(int &x);
	//判斷棧是否為空
	bool IsEmpty()const {
		return (top == -1) ? true : false;
	}
	//判斷棧是都為滿
	bool IsFull()const {
		return (top == maxSize - 1) ? true : false;
	}
	//獲取棧當前的size
	int getSize()const {
		return top + 1;
	}
	//將棧置空
	void MakeEmpty() {
		top = -1;
	}
	//重載 操作 <<
	friend ostream& operator<<(ostream& os, SeqStack& s);

private:
	int *elements;				//棧數組指針
	int top;					//棧頂指針
	int maxSize;				//棧的最大容量
	void overflowProcess();		//溢出處理程序
};

實現：

#include "SeqStack.h"

SeqStack::SeqStack(int sz):top(-1),maxSize(sz)
{
	elements = new int[maxSize];		//創建棧的數組空間
	assert(elements == NULL);            //斷言：動態分配是否成功
}
void SeqStack::push(int & x)
{
	//首先判斷棧是否已滿，滿則轉入溢出處理
	if(IsFull() == true){
		overflowProcess();
	}
	elements[++top] = x;    //將top+1，再插入值x
}
bool SeqStack::pop(int & x)
{
	//先判斷是否為空，為空則返回FALSE
	if (IsEmpty() == true) {
		return false;
	}
	x = elements[top--];     //使用x返回top所指，再講top-1
	return true;
}
bool SeqStack::Top(int & x)
{
	//空棧則為FALSE
	if (IsEmpty() == true) {
		return false;
	}
	//棧不為空，則返回棧頂元素的值
	x = elements[top];
	return true;
}
ostream& operator<<(ostream& os, SeqStack& s) {
	//輸出棧中元素
	os << "top = " << s.top << endl;
	for (int i = 0; i <= s.top; ++i) {
		os << i << ": " << s.elements[i] << endl;
	}
	return os;
}

void SeqStack::overflowProcess()
{
	//棧溢出時，擴充棧的存儲空間
	int *Newelement = new int[maxSize + stackIncreament];
	if (Newelement == NULL) {
		cout << "分配內存失敗";
		exit(1);
	}
	for (int i = 0; i <= top; ++i) {
		Newelement[i] = elements[i];
	}
	delete[] elements;
	elements = Newelement;
}

上述就是小編為大家分享的Java數據結構中棧的用法了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。